Иван Братко - Программирование на языке Пролог для искусственного интеллекта
вглубину( Путь, Верш, Решение)
Как видно из рис. 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]
Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель
вширину( Пути, Решения)
истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Решение.
11.3.1. Списковое представление множества кандидатов
В нашей первой реализации этой идеи мы будем использовать следующее представление для множества путей-кандидатов. Само множество будет списком путей, а каждый путь - списком вершин, перечисленных в обратном порядке, т.е. головой списка будет самая последняя из порожденных вершин, а последним элементом списка будет стартовая вершина. Поиск начинается с одноэлементного множества кандидатов
[ [СтартВерш] ]
решить( Старт, Решение) :-
вширину( [ [Старт] ], Решение).
вширину( [ [Верш | Путь] | _ ], [Верш | Путь] ) :-
цель( Верш).
вширину( [ [В | Путь] | Пути], Решение ) :-
bagof( [B1, В | Путь ],
( после( В, В1), not принадлежит( В1, [В | Путь])),
НовПути),
% НовПути - ациклические продолжения пути [В | Путь]
конк( Пути, НовПути, Пути1), !,
вширину( Путь1, Решение);
вширину( Пути, Решение).
% Случай, когда у В нет преемника
Рис. 11.10. Реализации поиска в ширину.
Общие принципы поиска в ширину таковы:
Для того, чтобы выполнить поиск в ширину при заданном множестве путей-кандидатов, нужно:
• если голова первого пути — это целевая вершина, то взять этот путь в качестве решения, иначе
• удалить первый путь из множества кандидатов и породить множество всех возможных продолжений этого пути на один шаг; множество продолжений добавить в конец множества кандидатов, а затем выполнить поиск в ширину с полученным новым множеством.
решить( Старт, Решение) :-
вширь( [ [Старт] | Z ]-Z, Решение).
вширь( [ [Верш | Путь] | _ ]-_, [Верш | Путь] ) :-
цель( Верш).
вширь( [ [В | Путь] | Пути]-Z, Решение ) :-
bagof( [B1, В | Путь ],
( после( В, В1),
not принадлежит( В1, [В | Путь]) ),
Нов ),
конк( Нов, ZZ, Z), !,
вширь( Пути-ZZ, Решение);
Пути == Z, % Множество кандидатов не пусто
вширь( Пути-Z, Решение).
Рис. 11.11. Программа поиска в ширину более эффективная, чем программа рис. 11.10. Усовершенствование основано на разностном представлении списка путей-кандидатов.
В случае примера рис.11.9 этот процесс будет развиваться следующим образом:
(1) Начинаем с начального множества кандидатов:
[ [а] ]
(2) Порождаем продолжения пути [а]:
[ [b, а], [с, а] ]
(Обратите внимание, что пути записаны в обратном порядке.)
