Пример задачи
Если вы до сих пор помните, в нашей первой лекции мы говорили об использовании пространства состояний для решения задач.
В целом, в представлении пространства состояний, задача представляется в виде множества состояний.
В частности, есть множество начальных состояний, то есть, там, где начинается задача,
и набор конечных состояний, в том числе всех возможных решений задачи.
Два состояния связаны, если существует операция, которая может превратить одно состояние в другое.
Один из примеров, которые мы использовали для иллюстрации представления пространства состояний, это игра в крестики-нолики.
Таким образом, игра начинается с начального состояния и может закончиться набором конечных состояний.
Два промежуточных состояний связаны, если существует операция между двумя состояниями.
Чтобы найти выигрышный путь (или, по крайней мере, ничью), нужно искать путь через пространство состояний с помощью представления дерева, как на графике, который вы видите здесь.
Широко используемая стратегия для поиска решения в пространстве состояний называется откатом.
Откат – это общая стратегия решения задачи для систематического поиска решения проблемы среди всех возможных вариантов.
И стеки часто используются в реализации алгоритмов отката.
Легче всего проиллюстрировать, как откат работает с использованием примеров.
Классическим примером использования отката в поиске решения является проблема n-ферзей.
Для тех, кто играл раньше в шахматы, вы знаете, что ферзь является самой сильной фигурой в шахматах.
Он может перемещаться на любое количество шагов по вертикали, горизонтали и даже по диагонали.
В шахматной игре, каждый игрок имеет только одного ферзя, но в задаче n-ферзей, есть в общей сложности n ферзей, то есть, для обычной 8x8 шахматной доски, там будет 8 ферзей.
В общем, n может быть любым числом.
Цель задачи n-ферзей является размещение n ферзей на шахматной доске NxN так, чтобы никакие два ферзя не смогли напасть друг на друга.
Давайте использовать n равный 5 в качестве примера.
Вот шахматная доска 5x5.
Поскольку ферзь может двигаться горизонтально, он может атаковать любых других ферзей, которые находятся на той же строке.
Так что, если ферзь находится на 0-й строке и в 0-в столбце, как показано здесь, ни один другой ферзь не может быть размещен на 0-й строке.
Точно так же, поскольку ферзь может двигаться по вертикали и по диагонали, ни один другой ферзь не может быть размещен в 0-м столбце и на основной диагонали.
Таким образом, после размещения первого ферзя на 0-й строке, все эти позиции с крестом были исключены.
На 2-й строке, первая доступная позиция в 3-м столбце или столбце с индексом 2.
Размещение этого второго ферзя устранит все остальные позиции в этой строке и все другие позиции в столбце с индексом 2.
Что касается диагонали, здесь есть две диагонали, как здесь показано на схеме.
По аналогии разместим остальных ферзей, и у нас есть наше первое решение задачи 5-ферзей.
Вы можете проверить, чтобы убедиться, что в этом решении, никакие два ферзя не могут напасть друг на друга по горизонтали, вертикали или диагонали.
Прежде чем двигаться дальше, вы можете сначала подумать о том, существуют ли другие варианты решения задачи 5-ферзей.
Теперь, когда вы понимаете, что представляет собой задача n-ферзей, давайте подумаем о том, как мы можем решить эту задачу.
Я буду использовать здесь пример, чтобы проиллюстрировать стратегию, которую мы собираемся использовать, чтобы решить задачу n-ферзей.
Мы разместим ферзей с первой строки по последнюю строку, и будем двигаться от самого левого столбца до самого правого столбца в каждой строке.
Давайте поместим первого ферзя в 0,0 положение, и мы будем использовать стек для хранения промежуточных решений.
Значение, сохраненное в стеке, является меткой столбца, в данном случае, 0.
Нам не нужно хранить метку строки, потому что мы можем использовать позицию элемента стека для обозначения метки строки.
После того, как у нас есть ферзь на определенной строке, мы не должны пытаться поставить другого ферзя в той же строке, потому что они могут напасть друг на друга в горизонтальном направлении.
Теперь мы можем двигаться дальше, чтобы попытаться поместить второго ферзя на 2-й строке.
Мы начнем с 1-го столбца, и это не является правильным шагом.
Далее мы постараемся двигать ферзя вправо или на 2-й столбец.
Опять же, тут есть конфликт, потому что первый ферзь может атаковать по диагонали.
2-й ферзь перемещается в следующий столбец снова, и это будет признано безопасной позицией, и это положение, то есть столбец с индексом 2, как метка записывается в стек.
Теперь мы можем попытаться поместить третьего ферзя в 3-й строке, начиная с 1-го столбца.
Конфликт возникает с первым ферзем, так что он перемещается в следующий столбец.
Это также не хорошо, потому что конфликт возникает со 2-м ферзем.
Следующий столбец тоже не хорош, потому что это находится в противоречии как с 1-м, так и со 2-м ферзем.
Точно так же, 4-й столбец также исключен из-за 2-го ферзя.
Так что мы остались в последнем столбце, и к счастью, нет конфликтов с остальными ферзями.
И позиция 4 теперь может быть записана в стек.
Размещение 4 ферзя может быть получена с использованием той же стратегии, и метка 1 записывается в стек.
Точно так же, правильное размещение получается и для последнего ферзя, и метка 3 помещается в стек.
Так что это первое решение, которое мы получили в задаче 5-ферзей.
Что делать, если мы хотим получить все остальные решения?
Где мы должны возвратиться к предыдущему шагу, и определить, где продолжать искать другое решение.
Поскольку нынешние позиции всех ферзей записываются в стек, мы можем удалить верхний элемент из стека, чтобы узнать местоположение предыдущего движения.
Установлено, что 5-й ферзь был помещен в столбец с меткой 3, так что вместо того, чтобы начинать с самого левого столбца, как то, что мы делали раньше, мы можем начать проверять следующий столбец с этой позиции.
Установлено, что эта позиция в конфликте с обеими, первым и третьим ферзем.
В этом случае, если мы будем двигаться дальше вправо, ферзь будет перемещен за пределы доски, что не позволительно.
Это означает, что не будет другого решения с текущим размещением предыдущих 4 ферзей.
Так что мы должны вернуться к предыдущей строке, и начать поиск решения.
Чтобы узнать текущее размещение ферзя на 4-й строке, верхний элемент в стеке удаляется и дает метку 1 или второй столбец.
Так он может двигаться вправо от этой позиции, а не из первого столбца.
К сожалению, все остальные позиции в строке находятся в противоречии с предыдущими ферзями.
Когда ферзь перемещается за пределы доски, мы знаем, что новое решение не может быть найдено с текущим размещением предыдущих 3 ферзей.
Таким образом, мы должны двигаться на одну строку вверх, вынимая верхний элемент из стека и пробуя еще раз.
В случае, если ферзь уже в последнем столбце, следующая позиция будет двигать его за пределы доски.
Таким образом, мы должны двигаться на одну строку вверх снова.
Мы обнаружили, что второй ферзь в настоящее время в столбце с меткой 2.
Перемещение его в следующий столбец не найдет никакого конфликта с каким-либо другим ферзем, так он может стать частью нового решения, и его метка 3 помещается в стек.
Таким образом, второе решение будет следующим.
