Часть 7.

Выталкивание (или удаление) последнего элемента (верхушки) из стека.

Просмотр последнего элемента (верхушки) без его удаления.

Проверка наличия данного элемента в стеке.

Добавление списка элементов в стек.

Операции 5 и 6 можно определить на основании первых четырех операций. Теперь опишем эти операции на языке PROLOG, используя в качестве строительных блоков списки.

1. empty_stack ( [ ] ). Этот предикат можно использовать либо для проверки пус­тоты стека, либо для создания нового пустого стека.

2 - 4. stack (Top, Stack, [Top | Stack] ). Этот предикат выполняет операции выталкивания, добавления и считывания последнего элемента стека в зависимости от связанных переменных, передаваемых ему в качестве параметров. Например, если первые два аргумента представляют собой связанные переменные, то в третьем аргументе формируется новый стек. Аналогично, если третий элемент связан со стеком, можно получить значение верхушки стека. Тогда второй аргумент будет связан с новым стеком, из которого удален последний элемент. И, наконец, если передать стек в качестве третьего аргумента, то через первый элемент можно по­лучить значение его верхушки.

5. member_stack(Element, Stack) :- member(Element, Stack). Это выражение позволяет определить, содержится ли данный элемент в стеке. Естест­венно, этот же результат можно получить с помощью рекурсивного вызова, про­сматривая следующий элемент стека, а затем, если этот элемент не соответствует значению аргумента Element, выталкивая его из стека. Эту процедуру необходи­мо выполнять до тех пор, пока предикат проверки пустоты стека не примет значе­ние "истина".

6.add_list_to_stack(List, Stack, Result) :- append(List, Stack, Result). Значение первого аргумента List добавляется к значению второго аргумента Stack для получения нового стека Result. Эту же операцию можно выполнить, выталкивая элементы из стека List и добавляя каждый сле­дующий элемент во временный стек до тех пор, пока стек List не окажется пус­тым. Затем нужно выталкивать по очереди элементы из временного стека и добав­лять их в стек Stack до опорожнения временного стека. Предикат append под­робно описан в разделе 14.8.

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

reverse_print_stack(S) :- empty_stack(S). reverse_print_stack(S) :-

stack(E, Rest, S) ,

reverse_print_stack(Rest) ,

write(E), nl.

Глава 14. Введение в PROLOG 623

14.2.2. Очередь

Очередь (queue) - это структура данных FIFO (First-In-First-Out) - "первым вошел, первым вышел". Ее зачастую рассматривают как список, в котором элементы удаляются из одного конца, а добавляются в другой. Очередь использовалась для определения поиска в ширину в главах 3 и 4. Для реализации очереди требуются следующие операции.

empty_queue ([ ] ). Этот предикат либо выполняет проверку очереди на пусто­

ту, либо инициализирует новую пустую очередь.

enqueue (Е, [ ], [Е]).

enqueue(E, [H|T], [H|Tnew]) :- enqueue(E, T, Tnew). Этот рекур­сивный предикат добавляет в очередь, определяемую вторым аргументом, элемент Е. Третий элемент представляет новую очередь.

dequeue (Е, [Е | Т] , Т). Этот предикат создает новую очередь (третий аргумент), которая является результатом удаления очередного элемента (первого аргумента) из исходной очереди, определяемой вторым аргументом.

dequeue (Е, [Е | Т] , _). Этот предикат позволяет прочитать следующий эле­мент Е данной очереди.

member_queue(Element, Queue) :- member(Element, Queue). Это

выражение проверяет, содержится ли элемент Element в очереди Queue.

add_list_to_queue(List, Queue, Newqueue) :- append(Queue,List, New-queue). Очистка всех элементов очереди.

Очевидно, что операции 5 и 6 можно реализовать на основе первых четырех операций. Предикат append описан в разделе 14.10.

14.2.3. Приоритетная очередь

В приоритетной очереди (priority queue) элементы обычной очереди упорядочены, и каждый новый элемент добавляется в соответствующее место. Оператор удаления элемента из очереди извлекает из нее лучший отсортированный элемент. Приоритетная очередь была использована при разработке "жадного" алгоритма поиска в главе 4.

Поскольку приоритетная очередь - это, по существу, отсортированная обычная очередь, многие из ее операций совпадают с операциями для обычной очереди. К таким операциям относятся empty_queue, member_queue и dequeue (следующим элемен­том для операции dequeue является "лучший" отсортированный элемент). Операции enqueue в приоритетной очереди соответствует операция insert_pq, поскольку каж­дый новый элемент должен помещаться в отведенное для него место.

insert_pq(State, [ ], [State]):- !.

insert_pq(State, [H|Tail], [State, H|Tail]):-

precedes(State, H).

insert_pq(State, [H|T], [H|Tnew]):-

insert_pq(State, T, Tnew).

precedes(X, Y) :- X < Y. %оператор сравнения зависит от типов

%элементов

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

624 Часть VI. Языки и технологии программирования для искусственного интеллекта

Следующим оператором для приоритетной очереди является insert_list_pq. Этот предикат используется для добавления несортированного списка или множества элементов в приоритетную очередь. Это необходимо при добавлении дочернего состояния в приоритетную очередь при реализации "жадного" алгоритма поиска (глава 4 и подраздел 14.4.3). Оператор insert_list_pq использует оператор insert_pq для добавления в приоритетную очередь каждого нового элемента.

insert_list_pq([ ], L, L).

insert_list_pq([State/Tail], L, New_L) :-

insert_pq(State, L, L2),

insert_list_pq(Tail, L2, New_L).

14.2.4. Множество

И, наконец, опишем абстрактный тип данных множество (set). Множество - это набор неповторяющихся элементов. Его можно использовать для объединения всех дочерних со­стояний или поддержания списка closed в алгоритме поиска, представленном в главах 3 и 4. Множество элементов, например [а, Ь], представляется в виде списка [а,b], в кото­ром порядок элементов не играет роли. Для множества необходимо определить операции empty_set, member_set, delete_if_in_set и add_if_not_in_set. Потребуют­ся также операции для объединения и сравнения множеств, включая union, intersec­tion, set_difference,subset и equal_set.

empty_set( [ ]).

member_set(E, S) :-

member(E, S).

delete_if_in_set(E, [ ], [ ]).

delete_if_in_set(E, [E|T], T) :- !.

delete_if_in_set(E, [H|T], [H|T_new]) :-

delete_if_in_set(E, T, T_new), !. add_if_not_in_set(X, S, S) :-

member(X, S), !.

add_if_not_in_set(X, S, [X|S]).

union([ ], S, S).

union([H|T], S, S_new):-

union(T, S, S2),

add_if_not_in_set(H, S2, S_new), !.

subset([ ], _).

subset([H|T], S) :-

member_set(H, S) ,

subset(T, S).

intersection([ ], _, [ ]).

intersection([H|T], S, [H|S_new]) :-

member_set(H, S),

intersection(T, S, S_new), !.

intersection([_|T], S, S_new) :-

intersection(T, S, S_new), !.

set_difference([ ], _, [ ]).

set_difference([H|T], S, T_new) :-

member_set(H, S),

set_difference(T, S, T_new), !.

set_difference([H|T], S, [H|T_new]) :-

set_difference(T, S, T_new), !.

Глава 14. Введение в PROLOG 625

equal_set(Sl, S2)

subset(SI, S2)

subset(S2, SI)

14.3. Пример продукционной системы на языке PROLOG

В этом разделе будет рассмотрена продукционная система для решения задачи перевозки человека, волка, козы и капусты. Эта задача формулируется следующим образом.

Человеку требуется переправиться через реку и перевезти с собой волка, козу и капусту. На берегу реки находится лодка, которой должен управлять человек. Лодка одновременно может перевозить не более двух пассажиров (включая лодочника). Если волк останется на берегу с козой, то он ее съест. Если коза останется на берегу с капустой, то она уничтожит капусту. Требуется выработать последовательность переправки через реку таким образом, чтобы все четыре пассажира были доставлены в целости и сохранности на другой берег реки.

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

Для начала предположим, что все состояния устойчивы, и просто рассмотрим граф возможных состояний. В лодке можно перевозить четыре комбинации пассажиров: человека и волка, человека и козу, человека и капусту, а также одного человека. "Состоянием мира" является некоторая комбинация символов на двух берегах. На рис. 14.1 показаны несколько состояний процесса поиска. "Состояние мира" можно представить с помощью предиката state (F, W, G, С), в котором первый параметр определяет местоположение человека, второй параметр - местоположение волка, тре­тий - козы, а четвертый - капусты. Предполагается, что река течет с севера на юг, по­этому берега обозначим символами е (восточный) и w (западный). Таким образом, state(w, w, w, w) означает, что все объекты расположены на западном берегу. Эта ситуация соответствует началу решения задачи.

Следует отметить, что все описанные соглашения были произвольно выбраны автором. На самом деле, как отмечают специалисты в области искусственного интеллекта, выбор соответствующего представления - зачастую наиболее критичный аспект реше­ния задачи. Выбранные соглашения обеспечивают удобное представление логики преди­катов на языке PROLOG. Различные состояния мира создаются в результате переправы через реку и представляются изменениями значений параметров предиката state (рис. 14.1). Возможны также и другие представления.

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

Описанный выше рекурсивный вызов предиката path обеспечивает механизм управления поиском в продукционной системе. Продукционные правила - это правила изме­нения состояния в процессе поиска. Определим их на языке PROLOG как правила move.

Поскольку язык PROLOG оперирует хорновскими дизъюнктами, то продукционные правила на языке PROLOG должны либо напрямую описываться в хорновской дизъюнк-

626 Часть VI. Языки и технологии программирования для искусственного интеллекта

тивной форме, либо преобразовываться к этому формату. Выберем первый вариант (процесс приведения правил "если..., то..." к хорновской дизъюнктивной форме описан в разделе 12.2). В хорновской дизъюнктивной форме шаблоны текущего и последующего состояний должны располагаться в голове дизъюнктивного выражения, т.е. слева от оператора : -. Они являются аргументами предиката move. Условия, которым должно удов­летворять продукционное правило для возвращения следующего состояния, размещают­ся справа от оператора : -. Как будет показано в следующем примере, эти условия также могут быть представлены в виде ограничений унификации.

Рис. 14.1. Пример последовательности перевозок для задачи переправы человека, волка, козы и капусты

Сначала определим правила для перевозки через реку волка. Это правило должно учитывать перевозку как с левого берега на правый, так и наоборот, а также должно быть при­менимо, если человек и волк находятся на противоположных берегах реки. Таким образом, оно должно преобразовывать состояние state (e, e, G, С) в состояние state (w, w, G, С), а состояние state (w, w, G, C)-в state (e, e, G, С). Для состоя­ний state (с, w, G, С) и state (w, e, G, С) оно должно принимать значение "ложь". Переменные G и С представляют тот факт, что третий и четвертый параметры мо­гут быть связаны с любым из значений е или w. Независимо от значений этих параметров они не изменяются после переправы человека и волка. Некоторые из полученных состоя­ний могут оказаться "неустойчивыми".

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

move(state(X,X,G,C), state(Y,Y,G,C)) :- opp(X, Y). opp(e, w). opp(w, e).

Глава 14. Введение в PROLOG

627

Рис. 14.2. Часть графа состояний для задачи переправы человека, вол­ка, козы и капусты с учетом неустойчивых состояний

Это правило срабатывает в том случае, если в качестве первого параметра предикату move передается состояние (текущее положение на графе), соответствующее одинаковому местоположению человека и волка. При активизации этого правила генерируется новое состояние (второй параметр предиката move), в котором значение Y противопо­ложно значению X. Для получения этого нового состояния должны быть выполнены два условия. Во-первых, должны совпадать значения первых двух параметров, а во-вторых, оба новых местоположения должны быть противоположны старым.

Первое условие проверяется неявно в процессе унификации. Следовательно, если первые два параметра не совпадают, то предикат move даже не вызывается. Эту провер­ку можно явно выполнить с помощью следующего правила.

move(state(F, W, G, С), state(Z, Z, G, C)) :- F=W, opp(F, Z).

В этом эквивалентном правиле move сначала проверяется равенство значений F и W, и только при его выполнении (расположении обоих объектов на одном берегу реки) параметру Z присваивается значение, противоположное F. Заметим, что в языке PROLOG присваивание можно реализовать с помощью связывания значений переменных в процессе унификации. Связанные значения распространяются на все вхождения переменной в дизъюнктивном вы­ражении, и область действия переменной ограничивается содержащим ее дизъюнктом.

В процессе усечения поиска важную роль играет такое мощное средство программирования систем искусственного интеллекта, как проверка соответствия шаблонам. Со­стояния, не удовлетворяющие шаблонам, автоматически отсекаются для данного прави­ла. В этом смысле первая версия правила move обеспечивает более эффективное пред­ставление, поскольку, если первые два параметра не совпадают, то в процессе унификации это состояние даже на рассматривается.

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

628 Часть VI. Языки и технологии программирования для искусственного интеллекта

безопасным является любое состояние, в котором второй и третий параметры совпадают и противоположны первому параметру. В этом случае волк съест козу. Кроме того, небезопасным является и такое состояние, при котором одинаковы третий и четвертый па­раметры, и при этом они противоположны первому. Тогда коза съест капусту. Эти небезопасные ситуации можно представить в виде следующих правил unsafe.

unsafe(state(X, Y, Y, С)) :- opp(X, Y).

unsafe(state(X, W, Y, Y)) :- opp(X, Y).

Здесь необходимо отметить несколько моментов. Во-первых, если состояние "не является небезопасным" not unsafe (т.е. безопасно), то согласно определению встроен­ной процедуры not в языке PROLOG для этого состояния не может быть истинным ни один из предикатов unsafe. Следовательно, ни один из этих предикатов не может быть унифицирован с текущим состоянием, или при унификации их условия не должны выполняться. Во-вторых, встроенная процедура not не эквивалентна операции логического отрицания -1 в теории предикатов первого порядка. Процедура not - это, скорее, отри­цание за счет невыполнения противоположного утверждения. Чтобы проверить, как по­ведет себя предикат unsafe, необходимо протестировать множество состояний. Доба­вим к предыдущему продукционному правилу проверку not unsafe.

move(state(X, X, G, С), state(Y, Y, G, C)) :-

opp(X, Y), not(unsafe(state(Y, Y, G, C))).

Процедура not unsafe проверяет приемлемость нового состояния в процессе поиска с помощью вызова предиката unsafe. Если все критерии удовлетворяются, включая проверку (в алгоритме path) отсутствия этого состояния в списке уже пройденных состояний, для дан­ного состояния вызывается (рекурсивно) алгоритм path для перехода глубже по графу. При вызове предиката path новое состояние добавляется к списку уже пройденных.

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

Команда reverse_print_stack используется в условии останова алгоритма path для вывода пути окончательного решения. И, наконец, добавим пятое "псевдоправило", которое не содержит никаких условий и поэтому всегда срабатывает при невыполнении всех предыдущих правил. Оно означает возврат вызова алгоритма path из текущего состояния. Это псевдоправило позволяет пользователю отслеживать поведение продукционной системы в процессе ее работы.

Теперь рассмотрим полную программу на языке PROLOG, реализующую продукционную систему решения задачи переправы человека, волка, козы и капусты. Она должна включать предикаты unsafe и writelist, а также предикаты, описывающие абст­рактный тип данных стек (подраздел 14.2.1).

move (state (X, X, G, С) , state (Y, Y, G, С) ) :-

opp(X, Y) not(unsafe(state(Y, Y, G, C))),

writelist(['попытка переправить человека и волка', Y, Y, G, С] ) .

move(state(X, W, X, С) , state (Y, W, Y, С) ) :-

орр(Х, Y), not(unsafe(state(Y, W, Y, С) ) ) ,

writelist(['попытка переправить человека и козу', Y, W, Y, С] ) .

move (state (X, W, G, X) , state (Y, W, G, Y) ) :-

opp(X, Y), not(unsafe(state(Y, W, G, Y) )),

writelist(["попытка переправить человека и капусту', Y, W, G, Y] ) .

Глава 14. Введение в PROLOG 629

move (state (X, W, G, С) , state(Y, W, G, С) ) :-

opp(X, Y), not(unsafe(state(Y, W, G, C))),

writelist(['попытка переправить одного человека', Y, W, G, С] ) .

move (state (F, W, G, С) , state (F, W, G, С) ) :-

writelist([v ВОЗВРАТ из', F, W, G, C]), fail,

path(Goal, Goal, Been_stack):-

write("Путь решения: '), nl,

reverse_print_stack(Been_stack).

path(State, Goal, Been_stack):-

move(State, Next_state),

not(member_stack(Next_state, Been_stack)),

stack(Next_state, Been_stack, New_been_stack) ,

path(Next_state, Goal, New_been_stack),!.

opp(e, w).

opp (w, e) .

Этот код вызывается в запросе go, инициализирующем рекурсивный вызов алгорит­ма path. Чтобы упростить работу программы, можно создать предикат test, облег­чающий ввод начальных данных.

go(Start, Goal) :-

empty_stack(Empty_been_stack),

stack(Start, Empty_been_stack, Been_stack),

path(Start, Goal, Been_stack).

test :- go(state(w, w, w, w), state(e, e, e, e)).

Этот алгоритм возвращается из состояний, не обеспечивающих дальнейшего продвижения. Для мониторинга связывания различных переменных в процессе каждого вызова алгоритма path можно использовать команду trace. Следует отметить, что эта систе­ма является общей программой перемещения четырех объектов из любого (допустимого) местоположения на берегах реки в любое другое (допустимое) местоположение, включая поиск обратного пути к начальному состоянию. Другие интересные свойства этой про­дукционной системы, в том числе зависимость результатов поиска на графе от порядка следования правил, можно проиллюстрировать в следующих упражнениях. Приведем некоторые результаты трассировки выполнения программы, отображая лишь правила, действительно используемые для генерации новых состояний.

?- test.

попытка переправить человека и козу е w e w

попытка переправить одного человека w w e w

попытка переправить человека и волка е е е w

попытка переправить человека и козу w e w w

попытка переправить человека и капусту е е w e

попытка переправить человека и волка w w w e

попытка переправить человека и козу е w e e

ВОЗВРАТ из е, w, e, e

ВОЗВРАТ из w, w, w, e

попытка переправить одного человека w e w e

попытка переправить человека и козу е е е е

Путь решения:

state (w, w, w, w)

state(e, w, e, w)

state (w, w, e, w)

630 Часть VI. Языки и технологии программирования для искусственного интеллекта

state(e, e, e, w)

state (w, e, w, w)

state(e, e, w, e)

state(w, e, w, e)

state(e, e, e, e)

Итак, эта программа на языке PROLOG реализует продукционную систему решения зада­чи переправы человека, волка, козы и капусты. Правила move составляют продукционную память. Рабочая память представлена аргументами вызова алгоритма path. Механизм управ­ления продукционной системой реализуется с помощью рекурсивного вызова path. И, нако­нец, порядок следования правил для генерации дочерних состояний (разрешения конфликта) определяется порядком расположения этих правил в продукционной памяти.

14.4. Разработка альтернативных стратегий поиска

Как видно из предыдущего раздела, в самом языке PROLOG реализован поиск в глубину с возвратом. Этот момент более детально будет описан в разделе 14.7. Теперь рас­смотрим, как реализовать на языке PROLOG альтернативные стратегии поиска, описан­ные в главах 3-5. Для записи состояний в процессе поиска в глубину, в ширину и при реализации алгоритма поиска будут использованы списки open и closed. В случае неудачного завершения поиска в некоторой точке мы не будем возвращаться к предыдущим значениям этих списков. Они будут обновляться при вызове алгоритма path, и по­иск будет продолжаться с новыми значениями. Для предотвращения хранения старых версий списков open и closed будет использован оператор отсечения.

14.4.1. Поиск в глубину с использованием списка closed

Поскольку при возвратах в рекурсивных вызовах значения переменных восстанавливаются, алгоритм поиска в глубину из раздела 14.3 пополняет список пройденных со­стояний только состояниями, относящимися к текущему пути к цели. И хотя проверка наличия в списке каждого нового состояния позволяет избежать циклов, она требует по­вторного тестирования тех областей пространства, которые уже были достигнуты ранее при построении других путей, но отклонены на данный момент из-за их бесперспектив­ности. Это более полное множество состояний составляет список, получивший название closed в главе 3 и Closed_set в следующем алгоритме.

В множестве Closed_set хранятся все состояния текущего пути и состояния, отвергнутые при возврате алгоритма. Следовательно, теперь оно не представляет путь от исходного к текущему состоянию. Для хранения информации о пути определим упоря­доченную пару [State, Parent], представляющую каждое состояние и его родителя. Начальное состояние Start будет представлено парой [Start, nil]. Эти пары бу­дут использованы для воссоздания пути решения из множества Closed_set.

Опишем на языке PROLOG структуру программы для поиска в глубину, отслеживая значения списков open и closed и проверяя каждое новое состояние на его наличие в списке пройденных. Алгоритм path зависит от трех параметров: стека Open_stack, Closed_set (обрабатываемого как множество) и целевого состояния Goal. Текущее состояние State является следующим состоянием для Open_stack. Операторы stack и set описаны в разделе 14.2.

Глава 14. Введение в PROLOG 631

Поиск начинается с предиката до, инициализирующего вызов алгоритма path. Заметим, что при выполнении команды до в стек Open_stack помещается пара, описывающая начальное состояние с нулевым родителем [Start, nil]. Множество Closed_set пока пусто.

go(Start, Goal) :- ,

empty_stack(Empty_open),

stack([Start, nil], Empty_open, Open_stack),

empty_set(Closed_set),

path(Open_stack, Closed_set, Goal).

Вызов алгоритма path, зависящего от трех аргументов, имеет вид.

path(Open_stack, _, _) :-

empty_stack(Open_stack),

write("3TM правила не привели к решению'). path(Open_stack, Closed_set, Goal) :-

stack([State, Parent], _, Open_stack), State = Goal,

write('Решение найдено!'), nl,

printsolution([State, Parent], Closed_set). path(Open_stack, Closed_set, Goal) :-

stack([State, Parent], Rest_open_stack, Open_stack),

get_children(State, Rest_open_stack, Closed_set, Children),

add_list_to_stack(Children, Rest_open_stack, New_open_stack),

union([[State, Parent]], Closed_set, New_closed_set),

path(New_open_stack, New_closed_set, Goal), !. get_children(State, Rest_open_stack, Closed_set, Children) :-

bagof(Child, moves(State, Rest_open_stack,

Closed_set, Child), Children). moves(State, Rest_open_stack, Closed_set, [Next, State]) :-

move(State, Next),

not(unsafe(Next)), % проверка зависит от задачи

not(member_stack([Next, _], Rest_open_stack)),

not(member_set([Next, _], Closed_set)).

Предполагается, что правила move и (при необходимости) предикат unsafe некото­рым образом определены.

move(Present_state, Next_state) :- ... % первое правило

move(Present_state, Next_state) :- ... % второе правило

При вызове первой команды path поиск прекращается, если стек Open_stack пуст. Это означает, что в списке open больше не содержатся состояния для продолжения поис­ка. Обычно это свидетельствует о том, что для данного графа выполнен поиск полным перебором. Второй вызов path завершается при нахождении решения, которое и выводится на печать. Поскольку состояния графа поиска представлены парами [State, Parent], команда printsolution перейдет ко множеству Closed_set и рекурсивно перестроит путь решения. Заметим, что путь решения будет выведен в прямом порядке.

printsolution([State, nil], _) :-

write(State), nl.

printsolution([State, Parent], Closed_set) :-

member_set ( [Parent, Grandparent], Closed_set),

printsolution([Parent, Grandparent], Closed_set),

write(State), nl.

632 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

В этой программе предикат bagof накапливает состояния, достигнутые при срабатывании всех существующих продукционных правил. Естественно, необходимо хранить все по­томки конкретного состояния, поэтому их можно добавить в соответствующем порядке в список open. Вторым аргументом предиката bagof является новый предикат moves, вызы­вающий предикаты move для генерации всех состояний, которые могут быть достигнуты с помощью данного продукционного правила. Аргументами предиката moves являются теку­щее состояние, списки open и closed и переменная, представляющая состояние, достигае­мое при "хорошем" ходе. Прежде чем возвратить это состояние, предикат moves проверяет, что это новое состояние Next не содержится в множествах rest_open_stack, open (поскольку текущее состояние удалено) и closed_set. Предикат bagof вызывает moves и накапливает все состояния, удовлетворяющие этим условиям. Третий аргумент предиката bagof представляет новые состояния, помещенные в стек Open_stack.

В некоторых реализациях предикат bagof принимает значение "ложь", если для второго аргумента не найдено никаких соответствий, а значит, третий аргумент пуст. Это можно исправить с помощью подстановки (bagof (X, moves (S, Т, С, X), List) ; List= [ ] ) для текущих вызовов предиката bagof в данном коде.

Поскольку состояния поиска представлены парами "состояние-родитель", предикаты проверки вхождения элемента во множество member__set необходимо модифицировать таким образом, чтобы они отражали структуру проверки соответствия шаблону. Необходимо прове­рить, совпадает ли пара "состояние-родитель" с первым элементом списка таких пар, и, если нет - выполнить рекурсивное сравнение со всеми остальными элементами списка.

member_set([State, Parent], [[State, Parent]| _]).

member_set(X, [_|T]) :- member_set(X, T).

14.4.2. Поиск в ширину в языке PROLOG

Теперь рассмотрим оболочку (shell) алгоритма поиска в ширину, явно использующую списки open и closed. Эту оболочку совместно с правилами move и предикатами un­safe можно применять для решения любой задачи поиска. Алгоритм вызывается сле­дующим образом.

go(Start, Goal) :-

empty_gueue(Empty_open_gueue),

enqueue([Start, nil], Empty_open_queue, Open_gueue),

empty_set(Closed_set) ,

path(Open_queue, Closed_set, Goal).

Значения параметров Start и Goal очевидны. Они представляют начальное и целе­вое состояния. В этом алгоритме, как и при поиске в глубину, снова создаются упорядоченные пары [State, Parent] для хранения информации о каждом состоянии и его родителе. Начальное состояние Start представляется парой [Start, nil]. Эта ин-

Глава 14. Введение в PROLOG 633

формация используется командой printsolution для воссоздания пути решения на основе множества Closed_set. Первым параметром предиката path является откры­тая очередь Open_queue, вторым - множество Closed_set, а третьим- целевое состояние Goal. Переменные, значения которых не учитываются в дизъюнктивном вы­ражении, обозначаются символом _.

path(Open_queue, _, _) :-

empty_queue(Open_queue),

write('Поиск завершен, решение не найдено').

path(Open_queue, Closed_set, Goal)

dequeue([State, Parent], Open_queue, _), State = Goal,

write("Путь решения:'), nl,

printsolution([State, Parent], Closed_set).

path(Open_queue, Closed_set, Goal) :-

dequeue([State, Parent], Open_queue, Rest_open_queue),

get_children(State, Rest_open_queue, Closed_set, Children),

add_list_to_queue(Children, Rest_open_queue, New_open_queue) ,

union([[State, Parent]], Closed_set, New_closed_set),

path(New_open_queue, New_closed_set, Goal), !.

get_children(State, Rest_open_queue, Closed_set, Children) :-

bagof(Child, moves(State, Rest_open_queue,

Closed_set, Child), Children).

moves(State, Rest_open_queue, Closed_set, [Next, State]) :-

move(State, Next),

not(unsafe(Next)), ^проверка зависит от задачи

not(member_queue([Next, _], Rest_open_queue)),

not(member_set([Next, _], Closed_set)).

Этот фрагмент кода назван оболочкой, поскольку здесь не описаны правила move. Их необходимо добавить с учетом конкретной предметной области задачи. Операторы queue и set описаны в разделе 14.2.

Первое условие останова алгоритма path определяется для случая, когда предикат path вызывается с пустым первым аргументом Open_queue. Эта ситуация возникает, только если для графа больше не осталось непроверенных состояний, а решение не было найдено. Решение находится при вызове второго предиката path, когда голова очереди Open_queue совпадает с целевым состоянием Goal.

В процессе поиска пути предикаты bagof и moves накапливают все дочерние состояния для текущих состояний и поддерживают очередь. Работа этих предикатов описана в предыдущем разделе. Чтобы воссоздать путь решения, каждое состояние сохраня­ется в виде пары [State, Parent]. Родителем начального состояния является указатель nil. Как упоминалось в подразделе 14.4.1, попарное представление состояний требует некоторого усложнения проверки соответствия шаблонам в предикатах member, moves и printsolution.

14.4.3. Реализация "жадного" алгоритма поиска на языке PROLOG

Оболочка для реализации "жадного" алгоритма поиска - это модификация программы поиска в ширину, в которой открытая очередь для каждого нового вызова path за­меняется приоритетной очередью, упорядоченной по эвристическому критерию. В пред­лагаемом алгоритме эвристическая мера неразрывно связана с каждым новым состояни­ем открытой очереди и применяется для систематизации ее элементов. Мы будем также

634 Часть VI. Языки и технологии программирования для искусственного интеллекта

хранить информацию о родителе каждого состояния. Как и при реализации поиска в ширину, она используется для построения пути решения командой printsolution.

Чтобы отслеживать всю необходимую для поиска информацию, каждое состояние представим в виде списка из пяти элементов: описание состояния, родительское состояние, целое число, определяющее глубину поиска на графе, целое число, определяющее эвристическую меру качества состояния, и целочисленная сумма третьего и четвертого элемента. Первый и второй элементы списка находятся обычным образом, третий определяется пу­тем добавления единицы к предыдущей глубине, четвертый - это эвристическая мера для конкретной задачи. Пятый элемент списка используется для упорядочения состояний в от­крытой очереди Open_pq и вычисляется по формуле f(n)=g(n)+h(n) (см. главу 4).

Как и ранее, правила move не приводятся. Они определяются с учетом специфики задачи. Операторы работы с очередью и приоритетной очередью описаны в разделе 14.2. Мера качества состояния heuristic тоже определяется с учетом специфики задачи и отражает эвристический характер четвертого параметра в списке описаний.

Этот алгоритм имеет два условия останова и вызывается следующим образом.

gо(Start, Goal) :-

empty_set(Closed_set),

empty_pq(Open),

heuristic(Start, Goal, H),

insertjpq([Start, nil, 0, H, H], Open, Open_pq),

path(Open_pq, Closed_set, Goal).

Здесь nil - это родительское состояние для состояния Start, a H - его эвристиче­ская мера качества. Приведем код программы, реализующей "жадный" алгоритм поиска.

path(Open_pq, _, _) :-

empty_pq(Open_pq),

write("Поиск завершен, решение не найдено.').

path(Open_pq, Closed_set, Goal) :-

dequeue__pq( [State, Parent, _, _, _] , Open_pq, _) ,

State = Goal,

write("Путь решения:'), nl,

printsolution([State, Parent, _, _, _], Closed_set).

path(Open_pq, Closed_set, Goal) :-

dequeue_pq([State, Parent, D, H, S], Open_pq, Rest_open_pq),

get_children([State, Parent, D, H, S], Rest_open_pq,

Closed_set, Children, Goal),

insert_list_pq(Children, Rest_open_pq, New_open_pq),

union([[State, Parent, D, H, S]], Closed_set, New_closed_set),

path(New_open_pq, New_closed_set, Goal), !.

Предикат get_children генерирует все дочерние состояния для состояния State. Как и в предыдущих алгоритмах поиска, в нем используются предикаты bagof и moves. Работа этих предикатов более подробно описана в подразделе 14.4.1. Правила переходов, проверки безопасности допустимых переходов и эвристическая мера качества определяются с учетом конкретной задачи. Проверка принадлежности элемента множеству должна быть специально реализована для списков из пяти элементов.

get_children([State,_, D, _, _], Rest_open_pq, Closed_set, Chil­dren, Goal) :-

bagof(Child, moves([State, _, D, _, _], Rest_open_pq,

Closed_set, Child, Goal), Children).

Глава 14. Введение в PROLOG 635

Смотрите здесь бизнес практикум Синергии, to.