Чтение онлайн

Прежде чем погрузиться в программирование, давайте более внимательно посмотрим на важность постановки задачи и представление процесса путем изучения обычно используемого подхода к решению задачи под названием представление пространства состояний.

В представлении пространства состояний, задача представляется в виде множества состояний.

И я буду использовать примеры для иллюстрации того, что я имею в виду под состояниями.

Пространство состояний, это множество всех возможных состояний, в которых задача может находиться.

В частности, есть множество начальных состояний, то есть там, где начинается задача, и набор конечных состояний, в том числе всех возможных решений задачи.

Два состояния связаны, если существует действительная операция, которая может превратить одно состояние в другое.

Давайте рассмотрим несколько примеров, чтобы получить более полное понимание представления пространства состояний.

Это простой пример, и задача заключается в том, чтобы включить смартфон.

Здесь есть два состояния "сон" и "работа" и они соединены операцией нажатия на кнопку питания.

Первоначально, смартфон находится в «спящем» состоянии.

Для перехода к состоянию "работать", пользователь нажимает на кнопку питания.

И смартфон переключается из состояния "сна" в состояние "работать".

Пользователь может переключиться на «спящее» состояние смартфона снова, нажав на кнопку питания.

В этом примере, вероятно, нельзя сказать много о полезности представления пространства состояний.

Давайте теперь рассмотрим более интересный пример – игру крестики-нолики.

В этой игре, два игрока ставят "крестик" или "кружок" в таблице 3x3.

И тот, кто получает 3 крестика или нолика в ряд первым либо горизонтально, либо вертикально, либо по диагонали будет победителем.

Здесь показывается, как два компьютера играют в крестики-нолики друг с другом.

Поскольку компьютеры не делают ошибок, мы можем написать программу, чтобы гарантировать, что они не проиграют в этой игре.

Это своего рода задача, изучаемая в области искусственного интеллекта.

На этой диаграмме видно, что игра начинается с пустой сетки 3x3, мы назовем это начальным состоянием.

Пусть игрок, который ставит крестик, начнет первым.

Есть 9 возможных мест, где 1-й игрок может разместить крестик, но из-за симметрии, график показывает только три варианта, в том числе средний из которых является уникальным, а два других представляет 4 случая.

2-й шаг мог бы быть сделан игроком, который ставит кружок.

Здесь все возможные ходы для 2-го игрока после удаления симметричных случаев.

Если мы будем продолжать, чтобы пройти все возможные ходы, в результате график даст нам пространство состояний.

Угадайте, сколько возможных состояний есть? Если вы достаточно терпеливы, чтобы проследить все возможности, вы увидите, что есть более чем 250000 возможных последовательностей. Вместо того чтобы идти через все случаи, давайте дальше расширять только один конкретный случай.

Здесь все возможные размещения 2-го крестика после этого конкретного выбранного состояния, и все возможные места размещения 2-го кружка.

3-я шаг со стороны игрока с крестиком приведет к первому возможному состоянию выигрыша.

Кроме того, 3-й шаг для кружка приведет ко второму возможному состоянию выигрыша.

Также есть состояние ничьей.

Эти результаты состояния победы вместе с состоянием ничьей образуют множество конечных состояний.

Есть много больше конечных состояний, которые не показаны здесь.

И после прочтения этой книги, вы должны уметь писать программы для такого рода игр или даже более сложных задач.

Давайте рассмотрим другой пример, чтобы проиллюстрировать, как выбор соответствующего представления может упростить поиск решений более сложной задачи.

Как и в игре крестики-нолики, задача здесь начинается с матрицы 3х3, но в этой задаче, клетки занимают квадратные яблоки.

Давайте назовем это задачей квадратных яблок.

Люди на самом деле могут вырастить квадратные яблоки или даже квадратные арбузы.

Предположим, что в исходном состоянии этой задачи существует червь в средней ячейке.

Вопрос в том, может ли червь съесть все яблоки, выполнив следующие два правила.

Во-первых, после того, как червь закончил целое яблоко в текущей ячейке, он может двигаться только в другую ячейку, которую разделяет общая сторона, так что эти стрелки показывают 4 возможных хода и 2-е правило состоит в том, что вы не можете переместиться в ту ячейку, которую посещали прежде.

То есть, червь может двигаться только в ячейку, где есть еще несъеденное яблоко внутри.

Рисунок показывает, что червь начинает с середины. После того, как заканчивается среднее яблоко, он может двигаться в одну из четырех клеток на стороне, но не в углу. Таким образом, червь может двигаться вправо, двигаться вниз, двигаться влево и двигаться вверх.

Я хочу, чтобы вы подумали, есть ли решение этой задачи.

То есть, может ли червь съесть все 9 яблок.

Это должно быть совершенно очевидно.