Программирование на языке Пролог для искусственного интеллекта

Братко Иван

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

Как видно из рис. 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( Верш, Решение, МаксГлуб)

Не разрешается вести поиск на глубине большей, чем

МаксГлуб

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

вглубину2

и к проверке, что этот предел не стал отрицательным. В результате получаем программу, показанную на рис. 11.8.

Упражнения

11.1. Напишите процедуру поиска в глубину (с обнаружением циклов)

вглубину1( ПутьКандидат, Решение)

отыскивающую решающий путь

Решение

как продолжение пути

ПутьКандидат

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

Решение

.

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

11.3. Проведите эксперимент по применению программы поиска в глубину к задаче планирования в "мире кубиков" (рис. 11.1).

11.4. Напишите процедуру

отобр( Ситуация)

для отображения состояния задачи "перестановки кубиков". Пусть

Ситуация

 — это список столбиков, а столбик, в свою очередь, — список кубиков. Цель

отобр( [ [a], [e, d], [с, b] ] )

должна отпечатать соответствующую ситуацию, например так:

e с

a d b

==============

11.3. Поиск в ширину

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

Рис. 11.9. Простое пространство состояний: а — стартовая вершина, f и j — целевые вершины. Применение стратегии поиска в ширину дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более короткое решение

[a, c, f]

найдено раньше, чем более длинное

[а, b, e, j]

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

вширину( Пути, Решения)