Чтобы выяснить, имеется ли путь из стартовой вершины в целевую вершину, воспользуемся предикатом:
путь(X, X).
путь(X, Y): – после(X, Z),путь(Z, Y).
Иными словами, путь из вершины X в вершину Y существует, если имеется вершина Z, следующая после Х, и известен путь из вершины Z в вершину Y. Факт путь(Х, Х) обеспечивает выход из рекурсии. Для того чтобы выяснить имеется ли путь, ведущий из вершины “а” в целевую вершину “g1”, необходимо задать вопрос:
? – путь(a, g1).
Данный вариант программы также не возвращает в качестве результата решающий путь, а возвращает ответ “да” или “нет”. Чтобы запомнить решающий путь введем в рассмотрение список закрытых вершин ЗКР, т.е. вершин, которые уже пройдены. Определим предикат, выполняющий поиск в глубину:
Здесь предикат в_глубину переопределяется через предикат путь. Третьим аргументом предиката путь является список ЗКР. При первом вызове в него помещается стартовая вершина. Четвертый аргумент предиката путь – список вершин, расположенных на обратном пути из целевой вершины в стартовую вершину. Поэтому значение переменной Реш_путь, представляющей решающий путь, получается путем инвертирования списка Путь.
Предикат путь определяется рекурсивно. При этом в списке ЗКР последовательно накапливаются вершины, лежащие на искомом пути:
путь(Х, Х, ЗКР, Путь): – Путь=ЗКР. % выход из рекурсии путь(Х, Y, ЗКР, Путь): – после(X, Z), путь(Z, Y, [Z|ЗКР], Путь).
При каждом рекурсивном вызове очередная вершина Z, следующая после Х, вносится в начало списка ЗКР. Если вершина Z совпадает с целевой вер-
b-d-h,
Язык Пролог
351
шиной Y, то рекурсивные вызовы прерываются и переменная Путь получает значение списка ЗКР. Если вершина Z является тупиковой, то цель после(Z, _ ) терпит неудачу, и пролог-система выполняет возврат к предыдущей вершине, в которой имеется альтернативный путь для продолжения поиска. В ходе возврата все подстановки, которые были сделаны в список ЗКР на тупиковом направлении, стираются. Чтобы проиллюстрировать это, внесем изменения в определение предиката путь:
путь(X, Y, ЗКР, Путь): – write(ЗКР), nl, после(X, Z), …
Тогда при запросе
? – в_глубину(a, g1, P).
для графа, изображенного на рисунке 6.10, получим следующие ответы:
[a] [b, a]
[d, b, a] [h, d, b, a] [e, b, a] [i, e, b, a]
P=[a, b, e, g1]
В этом случае пролог-система отображает промежуточные состояния списка ЗКР. После захода в вершину “h” и выяснения того, что цель после(h,_) недостижима, возникает возврат к альтернативному варианту продолжения списка. Подстановки, которые были сделаны в список ЗКР на пути стираются, и список ЗКР получает новое значение [e, b, a].
Рассмотренный вариант программы поиска в глубину имеет существенный недостаток: если на графе состояний имеются циклы, то программа может зациклиться. Чтобы устранить этот недостаток, необходимо добавлять очередную вершину Z в список ЗКР только в том случае, если ее
там нет. Рекурсивное правило для предиката путь перепишется следующим образом:
путь(X, Y, ЗКР, Путь): – после(X, Z), not элемент(Z, ЗКР),
путь(Z, Y, [Z|ЗКР], Путь).
Рассмотрим задачу манипулирования кубиками (рисунок 6.11)1). Имеются три стола “p”, “q”, “r” и три кубика “a”, “b”, “c”. Дано начальное положение кубиков, изображенное на рисунке 6.11 слева. Необходимо найти последовательность команд по перемещению кубиков, обеспечивающую их конечное расположение, изображенное на рисунке 6.11 справа.
1) Данную программу разработал Дж. Криз (J. Kriz)
352
Глава 6
Рисунок 6.11 – Задача манипулирования кубиками
Данная задача легко решается в пространстве состояний. При этом участок графа состояний, соответствующий переходу из состояния S в состояние S1, будем представлять в виде предиката
t(S, S1, переместить(Что, Откуда, Куда)),
где переместить(Что, Откуда, Куда) – терм, соответствующий команде перемещения кубика. Например, возможный переход из начального состояния, изображенного на рисунке 6.11, можно описать следующим образом:
Начальное состояние представлено предикатом s(p([a, b]), q([ ]), r([c])). Аргументы предиката – термы, отражающие расположение кубиков на столах. Так, p([a, b]) означает, что на столе “p” находятся кубики “a” и “b”, причем кубик “a” находится сверху кубика “b“. Новое состояние S1, в которое необходимо перейти, описывается предикатом s(p([b]), q([a]), r([c])). Переход в это состояние обеспечивается командой переместить(a, откуда(p), куда(q)), то есть необходимо переставить кубик “a” со стола “p” на стол “q”.
Введем следующие правила, определяющие возможные перемещения кубиков:
Первое правило позволяет перемещать кубик (D=q), либо на стол “r” (D=r). При этом кубик
Р1 со стола “p“ на стол “q” Р1 устанавливается сверху
Язык Пролог
353
кубиков, которые находились либо на столе “q” (Q1=[P1|Q]), либо на столе “r” (R1=[P1|R]). Второе правило обеспечивает перемещение кубиков со стола “q” на стол “r”.
Решение задачи можно найти с помощью следующего предиката поиска в глубину:
t(S, S1, T), not элемент(S1, ЗКР), путь(S1, [S1|ЗКР], Ts).
Здесь в переменной Решение будет накапливаться последовательность команд по перемещению кубиков. Список ЗКР, как и прежде, служит для исключения повторного прохождения через одни и те же состояния. Предикат цель(S) определяет целевое состояние. Для рисунка 6.11 целевое состояние задается фактом:
Рассмотренный вариант программы будет успешно осуществлять поиск в конечных пространствах состояний. Если пространство состояний задачи бесконечно, то направление поиска вдоль одной бесконечной ветви графа может оказаться ошибочным. Чтобы исключить рассмотренную ситуацию, в программу вводят ограничение глубины поиска. Разрешается вести поиск на глубине не большей, чем значение переменной Глубина:
При очередном выборе ветви поиска, значение переменной Глубина уменьшается на единицу. В этом случае поиск идет сначала в глубину, а затем в ширину.
в_ширину( ):
354
Глава 6
6.11.2.2. Поиск в ширину. Программирование метода поиска в ширину сложнее, чем поиска в глубину. Обусловлено это тем, что необходимо запоминать несколько возможных направлений поиска. Напишем программу поиска в ширину в соответствии с алгоритмом, рассмотренным в главе 2.
Введем в рассмотрение предикат в_ширину(ОТК,ЗКР,Решение), где ОТК – список открытых вершин; ЗКР – список закрытых вершин; Решение
–список обследованных вершин, соответствующий списку ЗКР в момент достижения целевой вершины. Указанные списки состоят из подсписков, каждый из которых содержит два элемента. Первый элемент подсписка – это имя некоторой вершины графа состояний, а второй – имя ее родительной вершины. Список Решение формируется таким образом, что его первый подсписок в качестве первого элемента содержит целевую вершину. Просмотрев список Решение от целевой вершины до стартовой вершины, можно восстановить решающий путь. Будем использовать для этого пре-
дикат решающий_путь(Решение, Цель, Старт, Temp, Реш_путь), где Цель –
целевая вершина; Старт – начальная вершина; Temp – вспомогательная переменная, предназначенная для накопления результатов поиска; Реш_путь
–список, фиксирующий найденный путь от стартовой до целевой вершины.
При определении предиката в_ширину(ОТК,ЗКР,Решение) для раскрытия очередной вершины и генерации возможных продолжений пути будем использовать встроенный предикат bagof. Цель
bagof(X, C, L)
формирует список L всех объектов Х, удовлетворяющих условию С. Например,
В начале поиска список ЗКР пустой, а список ОТК содержит подсписок, включающий начальную вершину. На каждом шаге рекурсии выделяется первый подсписок [О1|О2] списка ОТК. Выясняется, является ли вершина О1 целевой (цель(О1)). Если О1 целевая вершина, то подсписок [О1|О2] добавляется в начало списка ЗКР, и рекурсия прерывается. Переменная Решение получает значение списка [[О1|О2] | ЗКР], элементами которого являются подсписки, представляющие пройденные отрезки графа состояний.
Если О1 не целевая вершина, то находятся все продолжения пути после вершины О1. Для этого применяется предикат bagof, который обеспечивает поиск всех отрезков графа состояний [Z|O1] таких, что вершина Z не входит в список ЗКР и в остаток списка ОТК (Ост_ОТК). Все найденные дочерние вершины накапливаются в списке L в виде подсписков и помещаются в конец списка Ост_ОТК, образуя список Нов_ОТК. Затем обработанный первый подсписок [О1|О2] списка ОТК перемещается в начало списка ЗКР, и предикат в_ширину вызывается при новых значениях аргументов.
Если вершина О1 является тупиковой, то предикат после(О1,Z) завершается неудачей. В этом случае никакие новые вершины не добавляются в конец списка ОТК, и обеспечивается альтернативный вызов предиката
в_ширину:
в_ширину(Ост_ОТК, ЗКР, Решение).
В рассмотренном определении предиката в_ширину используется предикат элемент1(Вершина,Список). Данный предикат позволяет установить, входит ли Вершина в один из подсписков, образующих Cписок:
Предикат найти(Элемент,Список1,Список2) выполняет поиск заданного элемента в списке Список1, состоящем из подсписков. Результатом поиска является список Список2, представляющий хвостовую часть списка Список1, в первый подсписок которого входит искомый элемент:
Чтобы лучше уяснить работу описанных выше предикатов, введем вопрос:
? – в_ширину( [[a | a]], [ ], Решение),
решающий_путь(Решение, g1, a, [ ], Реш_путь).
Начальное значение списка ОТК = [[a | a]]. Список ЗКР пустой. Цель заключается в том, чтобы найти решающий путь из начальной вершины "a" в конечную вершину “g1” (рисунок 6.10). В результате обработки вопроса получим значения переменных:
Значение переменной Решение соответствует состоянию списка ЗКР в момент завершения поиска. Головным элементом каждого из подсписков является вершина, которая раскрывалась в процессе поиска (за исключением целевой вершины). Хвостовой элемент каждого из подсписков есть родительная вершина для головного элемента. Перемещаясь по указанным подспискам в направлении от целевой вершины до начальной, используя ссылки на родительские вершины, восстанавливаем значения переменной
Реш_путь.
6.11.2.3. Эвристический поиск. В эвристических алгоритмах список открытых вершин ОТК сортируется с учетом возрастания оценочной функции. Рассмотрим А– алгоритм с оценочной функцией вида (2.1).
Пусть граф состояний описывается с помощью фактов, задаваемых предикатом после(P,D,C,H), где Р – родительская вершина; D – дочерняя вершина; С – стоимость участка пути между вершинами Р и D; Н – оценка стоимости кратчайшего пути из вершины D в целевую вершину. Тогда граф состояний, изображенный на рисунке 2.9, можно описать с помощью следующего набора фактов:
после(s, d, 1, 10). после(s, c, 3, 7).
Язык Пролог
357
после(s, b, 5, 4). после(s, a, 7, 1). после(a, g, 10, 0). после(b, a, 1, 1). после(c, b, 1, 4,). после(c, a, 2, 1). после(d, c, 1, 7).
Определим на Прологе предикат а_поиск, соответствующий процедуре эвристического поиска A_search (см. § 2.2.2.3):
a_поиск(ОТК, ЗКР, Решение),
где ОТК, ЗКР – списки открытых и закрытых вершин; Решение – список, соответствующий искомому пути из начальной вершины в целевую вершину. Каждая из вершин графа состояний представляется в этих списках в виде подсписков [D, P, F, G], где D – вершина на графе состояний; P – ссылка на родительную вершину; F – значение оценочной функции (2.1); G
– оценка стоимости пути от начальной вершины до вершины D. Определение предиката а_поиск близко к определению предиката
в_ширину. Отличие заключается в том, что в случае эвристического поиска вершины из списка ЗКР могут перемещаться обратно в список ОТК. Происходит это из-за того, что в ходе поиска может быть обнаружен путь меньшей стоимости к вершине, которая уже была раскрыта. Это приводит к необходимости удаления такой вершины из списка ЗКР и вставки ее в список ОТК (с учетом значения оценочной функции). Кроме этого, если в процессе раскрытия очередной вершины обнаруживается, что ее дочерние вершины уже имеются в списке ОТК, но с бóльшими значениями оценочной функции, то такие вершины также удаляются из списка ОТК, и вместо них в список ОТК вставляются вершины с меньшими значениями оценочной функции. Приведем определение предиката а_поиск:
В этом определении с помощью предиката bagof находятся все дочерние вершины для вершины D, находящейся на первом месте в списке
358
Глава 6
ОТК и имеющей наименьшее значение оценочной функции F. Для поиска дочерних вершин используется условие:
следующая(D,Z,FZ,GZ,G): –
после(D,Z,C,H), GZ is G+C, FZ is GZ+H.
Здесь переменные FZ и GZ соответствуют оценочным функциям fˆ(n) и gˆ(n) для вершины Z. Переменная G соответствует оценке gˆ(n) для вершины D. При вызове предиката переменные D и G конкретизированы, а переменные Z, FZ, GZ вычисляются, формируя подсписки [Z,D,FZ,GZ], которые накапливаются в списке дочерних вершин DB. Если вершина D может быть раскрыта (т. е. имеет дочерние вершины), то вызов bagof завершается успешно, и вершина D перемещается в список ЗКР. Это выполняется с помощью вызова:
вставить( [D,P,F,G], ЗКР, Н_ЗКР).
Дочерние вершины для вершины D, размещаемые в списке DB, вносятся в остаток списка ОТК (Ост_ОТК), если они отсутствуют в списках Ост_ОТК и Н_ЗКР. Если дочерняя вершина уже имеется в списке Ост_ОТК, а значение её оценочной функции выше, чем у вершины из списка DB, то она заменяется на вершину из списка DB. Кроме того, если дочерняя вершина имеется в списке Н_ЗКР, то в список Ост_ОТК вносится соответствующая вершина из списка DB. Все указанные действия выполняются с помощью вызова предиката
поместить(Ост_ОТК, DB, Н_ЗКР,Нов_ОТК, Нов_ЗКР).
В результате выполнения предиката формируются новые списки Нов_ОТК и Нов_ЗКР. После этого предикат а_поиск вызывается рекурсивно для новых значений списков ОТК и ЗКР. Если у вершины D не имеется дочерних вершин, то вызов bagof завершается неудачей, и предикат а_поиск вызывается рекурсивно при старых значениях списков ОТК и ЗКР. Рекурсия прерывается, когда первая вершина в списке ОТК будет целевой. При этом она вносится в начало списка ЗКР, формируя значение перемен-
ной Решение.
Предикат поместить определяется следующим образом:
Предикат удалить(Х,Список,Нов_список) выполняет удаление подсписка Х, представляющего вершину графа состояний, из списка Список. Результатом является новый список Нов_Список. Удаление выполняется, если оценочная функция для удаляемого элемента Х меньше значения оценочной функции элемента из списка Список.
Предикат осуществляет включение подсписка Х, представляющего вершину графа состояний, в Список, формируя новый список Нов_Список. При этом включение выполняется с учетом значения оценочной функции. Результирующий список упорядочен по возрастанию оценочной функции:
Предикат элемент(Х,Список) в рассматриваемом случае определяется следующим образом:
элемент([Z | X], [[Z | _ ] | T] ).
элемент(Н, [Y | T] ):– элемент(Н, Т).
Рассмотрим выполнение эвристического поиска на примере графа состояний, изображенного на рисунке 2.9. При этом будем выводить на печать состояния списков ОТК и ЗКР при каждом вызове предиката а_поиск. Введем целевое утверждение
? – а_поиск( [[s, s, 14, 0]], [ ], Решение).
Здесь список ОТК содержит начальную вершину, представленную подсписком [s, s, 14, 0]. Список ЗКР пустой. В ходе поиска будут получены следующие значения списков ОТК и ЗКР:
