Программа решения задачи о N ферзях реализует стратегию поиска в глубину. Под термином «в глубину» имеется в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую «глубокую» из них. Самая глубокая вершина – это вершина, расположенная дальше других от стартовой вершины. На следующем рисунке показан пример, который иллюстрирует работу алгоритма поиска в глубину. Этот порядок в точности соответствует результату трассировки процесса вычислений при поиске решения.
Порядок обхода вершин указан пунктирными стрелками, a – начальная вершина, j и f – целевые вершины.
Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что обрабатывая цели, Пролог сам просматривает альтернативы именно в глубину.
На Прологе переход от одной проблемной ситуации к другой может быть представлен при помощи предиката after (X, Y, C), который истинен тогда, когда в пространстве состояний существует разрешенный ход из вершины X в вершину Y, стоимость которого равна C. Предикат after может быть задан в программе явным образом в виде фактов, однако такой принцип оказывается непрактичным, если пространство состояний является достаточно сложным. Поэтому отношение следования after обычно определяется неявно, при помощи правил вычисления вершин, следующих за некоторой заданной вершиной.
Другой проблемой при описании пространства состояний является способ представления самих вершин, то есть самих состояний.
В качестве первого примера решения таких задач рассмотрим задачу о ханойских башнях. Есть три стержня и набор дисков разного диаметра. В начале игры все диски надеты на левый стержень. Цель игры заключается в переносе всех дисков на правый стержень по одному стержню за раз, при этом нельзя ставить диск большего диаметра на диск меньшего диаметра. Для этой игры есть простая стратегия:
1. Один диск перемещается непосредственно;
2. N дисков переносятся в 3 этапа:
· Перенести N-1 диск на средний стержень;
· Перенести последний диск на правый стержень;
· Перенести N-1 диск со среднего на правый стержень.
В программе на языке Пролог есть 3 предиката:
· hanoi – запускающий предикат, указывает сколько дисков надо переместить;
· move – описывает правила перемещения дисков с одного стержня на другой;
· inform – указывает на действие с конкретным диском.
Пример 78: решение задачи о ханойских башнях.
domains
loc=right;middle;left
% описывает состояние стержней
predicates
hanoi(integert)
% определяет размерность задачи
move(integer,loc,loc,loc)
% определяет переход из одной вершины пространства состояния в другую, то есть описывает правила перекладывания дисков
inform(loc,loc)
% распечатывает действия с дисками
clauses
hanoi(N):-move(N,left,middle,right).
move(1,A,_,C):-inform(A,C),!.
move(N,A,B,C):-N1=N-1, move(N1,A,C,B),
inform(A,C), move(N1,B,A,C).
inform(Loc1,Loc2):-nl, write(“Move a disk from “,Loc1,” to “, Loc2).
goal
hanoi(3).
В качестве второго примера решения таких задач рассмотрим задачу нахождения плана переупорядочивания кубиков, представленную на следующем рисунке.
На каждом шаге разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы получить требумое состояние, необходимо получить последовательность ходов, реализующую данную трансформацию. В качестве примера будет рассмотрен общий случай данной задачи, когда имеется произвольное число кубиков в столбиках. Число столбиков ограничено некоторым максимальным значением.
Проблемную ситуацию можно представить как список столбиков. Каждый столбик, в свою очередь, представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. «Пустые» столбики изображаются как пустые списки. Таким образом, исходную ситуацию на рисунке можно записать как терм [[c, a, b], [], []].
Целевая ситуация- это любая конфигурация кубиков, содержащая столбик, составленный из имеющихся кубиков в указанном порядке. Таких ситуаций три:
[[a, b, c], [], []];
[[], [a, b, c], []];
[[], [], [a, b, c]].
Пример 79: решение задачи о перемещении кубиков.
domains
list=symbol*
% описывает состояние одного столбика кубиков
sit=list*
% описывает состояние всех столбиков
sits=sit*
% описывает путь из начальной вершины в целевую вершину
predicates
after(sit,sit)
% определяет переход из одной вершины пространства состояния в другую, то есть описывает все возможные правила перекладывания кубиков
solve (sit, sit, sits, sits)
% определяет путь для решения задачи
member (list, sit)
% первый предикат ищет список в списке списков
member1(sit, sits)
% второй предикат ищет список списков в списке списков списков
(Вставить другую программу переупорядочения кубиков).
В данном примере реализован усовершенствованный алгоритм поиска в глубину, в котором добавлен алгоритм обнаружения циклов. Предикат solve включает очередную вершину в решающий путь только в том случае, если она еще не встречалась раньше.
