Стратегия поиска в глубину

Основные стратегии поиска решающего пути - поиск в глубину и поиск в ширину. Идея алгоритма поиска в глубину заключается в следующем. Чтобы найти путь Solution из заданной вершины B в некоторую целевую вершину, необходимо:

- если B - целевая вершина, то положить Solution = [B], или

- если для исходной вершины B существует вершина - преемник B1, такая, что можно провести путь Solution1 из B1 в целевую вершину, то положить

Solution = [B|Solution1].

На Прологе это правило имеет вид:

solve(B,[B]):- goal(B).

solve(B,[B|Solution1]):- after(B,B1), solve(B1,Solution1).

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

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Обрабатывая цели Пролог - система сама просматривает альтернативы именно в глубину.

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

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

in_depth(Path,Node,Solution).

Здесь:

- Node - вершина (состояние), из которой необходимо найти путь до цели;

- Path - список вершин (путь) между стартовой вершиной и Node;

- Solution - путь, продолженный до целевой вершины.

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

(1) чтобы не рассматривать тех преемников вершины Node, которые уже встречались (обнаружение циклов);

(2) чтобы облегчить построение решающего пути Solution.

Программа поиска в глубину без зацикливания имеет вид:

solve(Node,Solution):-in_depth([],Node,Solution).

in_depth(Path,Node,[Node|Path]):- goal(Node).

in_depth(Path,Node,Solution):- after(Node,Node1), not(member(Node1,Path)),

in_depth([Node|Path],Node1,Solution).

Предложенная процедура, снабженная механизмом обнаружения циклов, будет успешно находить пути в конечных пространствах состояний, т. е. в пространствах с конечным числом вершин. Если же пространство состояний бесконечно, то алгоритм поиска в глубину может "потерять" цель, двигаясь вдоль бесконечной ветви графа. Чтобы предотвратить бесцельное блуждание, добавим в процедуру поиска в глубину ограничение на глубину поиска. Тогда эта процедура будет иметь следующие аргументы:

in_depth2(Node,Solution,MaxDepth).

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

В результате получаем следующую программу:

in_depth2(Node,[Node],_):- goal(Node).

in_depth2(Node,[Node|Solution],MaxDepth):-

MaxDepth > 0, after(Node,Node1),

Max1=MaxDepth - 1, in_depth2(Node1,Solution,Max1).

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

Пример 2. Решение задачи манипулирования кубиками методом поиска в глубину.

tgoal([[a,b,c],[],[]]). % целевые ситуации

tgoal([[],[a,b,c],[]]). tgoal([[],[],[a,b,c]]).

after(Stolbs,[Stolb1,[Up1|Stolb2]|Rest]):-

delete([Up1|Stolb1],Stolbs,Stolbs1), delete(Stolb2,Stolbs1,Rest).

delete(X,[X|L],L).