Prolog

Поиск в глубину часто работает хорошо, как в рассмотренном примере, однако наша простая процедура решить может попасть в затруднительное положение, причем многими способами. Случится ли это или нет - зависит от структуры пространства состояний. Для того, чтобы затруднить работу процедуры решить в примере рис. 11.4, достаточно внести в задачу совсем небольшое изменение: добавить дугу, ведущую из h  в  d,  чтобы получился цикл (рис. 11.5). В этом случае поиск будет выглядеть так: начиная с вершины  а,   спускаемся вплоть до  h,   придерживаясь самой левой ветви графа. На этот раз, в отличие от рис. 11.4, у вершины  h   будет преемник  d.  Поэтому произойдет не возврат из  h,  а переход к  d.  Затем мы найдем преемника вершины   d,  т.е. вершину  h,  и т.д., в результате программа зациклится между  h   и  d.

Рис. 11. 5.  Начинаясь в а, поиск вглубину заканчивается

бесконечным циклом между  d  и  h:   a, b, d, h, d, h, d ... .

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

        вглубину( Путь, Верш, Решение)

Как видно из рис. 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - путь (список вершин) между стартовой вершиной и Верш; Решение - Путь, продолженный до целевой вершины.

Рис. 11. 6.  Отношение вглубину( Путь, В, Решение).

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

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

(2)        чтобы облегчить построение решающего пути Решение. Соответствующая программа поиска в глубину показана на рис. 11.7.

        решить( Верш, Решение) :-

                вглубину( [ ], Верш, Решение).

        вглубину( Путь, Верш, [Верш | Путь] ) :-

                цель( Верш).

        вглубину( Путь, Верш, Реш) :-

                после( Верш, Верш1),

                not принадлежит( Верш1, Путь),                                         % Цикл ?

                вглубину( [Верш | Путь], Верш1, Реш).

Рис. 11. 7.  Программа поиска в глубину без зацикливания.

Теперь наметим один вариант этой программы. Аргументы Путь и Верш процедуры вглубину можно объединить в один список [Верш | Путь]. Тогда, вместо вершины-кандидата Верш, претендующей на то, что она находится на пути, ведущем к цели, мы будем иметь путь-кандидат П = [Верш | Путь], который претендует на то, что его можно продолжить вплоть до целевой вершины. Программирование соответствующего предиката

        вглубину( П, Решение)

оставим читателю в качестве упражнения.

Наша процедура поиска в глубину, снабженная механизмом обнаружения циклов, будет успешно находить решающие пути в пространствах состояний, подобных показанному на рис. 11.5. Существуют, однако, такие пространства состоянии, в которых наша процедура не дойдет до цели. Дело в том, что многие пространства состояний бесконечны. В таком пространстве алгоритм поиска в глубину может "потерять" цель, двигаясь вдоль бесконечной ветви графа. Программа будет бесконечно долго обследовать эту бесконечную область пространства, так и не приблизившись к цели. Пространство состояний задачи о восьми ферзях, определенное так, как это сделано в настоящем разделе, на первый взгляд содержит ловушку именно такого рода. Но оказывается, что оно все-таки конечно, поскольку Y-координаты выбираются из ограниченного множества, и поэтому на доску можно поставить "безопасным образом" не более восьми ферзей.

        вглубину2( Верш, [Верш], _ ) :-

                цель( Верш).

        вглубину2( Верш, [Верш | Реш], МаксГлуб) :-

                МаксГлуб > 0,

                после( Верш, Верш1),

                Maкс1 is МаксГлуб - 1,

                вглубину2( Верш1, Реш, Maкс1).

Рис. 11. 8.  Программа поиска в глубину с ограничением по глубине.

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

в базовую процедуру поиска в глубину еще одно усовершенствование, а именно, ввести

ограничение на глубину поиска

. Процедура поиска в глубину будет тогда иметь следующие аргументы:

        вглубину2( Верш, Решение, МаксГлуб)