Иван Братко - Программирование на языке Пролог для искусственного интеллекта
Прогр: список предложений
СписокЦелей: список целей
Выходной параметр:
Успех: истинностное значение; Успех принимает значение
истина, если список целевых утверждений
(их конъюнкция) истиннен с точки зрения Прогр
Локальные переменные:
Цель: цель
ДругиеЦели: список целей
Достигнуты: истинностное значение
Сопоставились: истинностное значение
Конкрет: конкретизация переменных
H, Н', B1, B1', …, Вn, Вn': цели
Вспомогательные функции:
пycтой( L): возвращает истину, если L — пустой список
голoвa( L): возвращает первый элемент списка L
хвост( L): возвращает остальную часть списка L
конкат( L1, L2): создает конкатенацию списков — присоединяет
список L2 к концу списка L1
сопоставление( T1, T2, Сопоставились, Конкрет): пытается
сопоставить термы Т1 и T2; если они сопоставимы, то
Сопоставились — истина, а Конкрет представляет
собой конкретизацию переменных
подставить( Конкрет, Цели): производит подстановку переменных
в Цели согласно Конкрет
begin
if пустой( СписокЦелей) then Успех : = истина
else
begin
Цель : = голова( СписокЦелей);
ДругиеЦели : = хвост( СписокЦелей);
Достигнута : = ложь;
while not Достигнута and
"в программе есть еще предложения" do
begin
Пусть следующее предложение в Прогр есть
H :- B1, …, Вn.
Создать вариант этого предложения
Н' :- В1', …, Вn'.
сопоставление( Цель, Н',
Сопоставились, Конкрет)
if Сопоставились then
begin
НовыеЦели :=
конкат( [В1', …, Вn' ], Другие Цели);
НовыеЦели : =
подставить( Конкрет, НовыеЦели);
вычислить( Прогр, НовыеЦели, Достигнуты)
end
end;
Успех : = Достигнуты
end
end;
Рис. 2.11. Вычисление целевых утверждений Пролога.
Всякий раз, как рекурсивный вызов процедуры вычислить приводят к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения С, которое использовалось последним. Поскольку применение предложения С не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.
Мы уже знаем, что даже после успешного завершения пользователь может заставить систему совершить возврат для поиска новых решений. В нашем описании процедуры вычислить эта деталь была опущена.
Конечно, в настоящих реализациях Пролога в процедуру вычислить добавлены и еще некоторые усовершенствования. Одно из них — сокращение работы по просмотрам программы с целью повышения эффективности. Поэтому на практике пролог-система не просматривает все предложения программы, а вместо этого рассматривает только те из них, которые касаются текущего целевого утверждения.
Упражнение2.9. Рассмотрите программу на рис. 2.10 и по типу того, как это сделано на рис. 2.10, проследите процесс вычисления пролог-системой вопроса
?- большой( X), темный( X).
Сравните свое описание шагов вычисления с описанием на рис. 2.10, где вычислялся, по существу, тот же вопрос, но с другой последовательностью целей:
?- темный( X), большой( X).
В каком из этих двух случаев системе приходится производить большую работу для нахождения ответа?
2.5. Пример: обезьяна и банан
Задача об обезьяне и банане часто используется в качестве простого примера задачи из области искусственного интеллекта. Наша пролог-программа, способная ее решить, показывает, как механизмы сопоставления и автоматических возвратов могут применяться для подобных целей. Мы сначала составим программу, не принимая во внимание процедурную семантику, а затем детально изучим ее процедурное поведение. Программа будет компактной и наглядной.
Рассмотрим следующий вариант данной задачи. Возле двери комнаты стоит обезьяна. В середине этой комнаты к потолку подвешен банан. Обезьяна голодна и хочет съесть банан, однако она не может дотянуться до него, находясь на полу. Около окна этой же комнаты на полу лежит ящик, которым обезьяна может воспользоваться. Обезьяна может предпринимать следующие действия: ходить по полу, залезать на ящик, двигать ящик (если она уже находится около него) и схватить банан, если она стоит на ящике прямо под бананом. Может ли обезьяна добраться до банана?
Одна из важных проблем при программировании состоит в выборе (адекватного) представления решаемой задачи в терминах понятий используемого языка программирования. В нашем случае мы можем считать, что "обезьяний мир" всегда находится в некотором состоянии, и оно может изменяться со временем. Текущее состояние определяется взаиморасположением объектов. Например, исходное состояние мира определяется так:
(1) Обезьяна у двери.
(2) Обезьяна на полу.
(3) Ящик у окна.
(4) Обезьяна не имеет банана.
Удобно объединить все эти четыре информационных фрагмента в один структурный объект. Давайте в качестве такого объединяющего функтора выберем слово "состояние". На рис. 2.12 в виде структурного объекта изображено исходное состояние.
Нашу задачу можно рассматривать как игру для одного игрока. Давайте, формализуем правила этой игры. Первое, целью игры является ситуация, в которой обезьяна имеет банан, т.е. любое состояние, у которого в качестве четвертой компоненты стоит "имеет":
состояние( _, _, _, имеет)
Второе, каковы разрешенные ходы, переводящие мир из одного состояния в другое? Существуют четыре типа ходов:
(1) схватить банан,
(2) залезть на ящик,
(3) подвинуть ящик,
(4) перейти в другое место.
Рис. 2.12. Исходное состояние обезьяньего мира, представленное в виде структурного объекта. Его четыре компоненты суть горизонтальная позиция обезьяны, вертикальная позиция обезьяны, позиция ящика, наличие или отсутствие у обезьяны банана.
Не всякий ход допустим при всех возможных состояниях мира. Например, ход "схватить" допустим, только если обезьяна стоит на ящике прямо под бананом (т.е. в середине комнаты) и еще не имеет банана. Эти правила можно формализовать в Прологе в виде трехместного отношения ход:
ход( Состояние1, М, Состояние2)
Три аргумента этого отношения определяют ход, следующим образом:
Состояние1 --------> Состояние2
М
Состояние1 это состояние до хода, М — выполняемый ход, и Состояние2 — состояние после хода.
Ход "схватить", вместе с необходимыми ограничениями на состояние перед этим ходом, можно выразить такой формулой:
ход( состояние( середина, наящике, середина, неимеет),
% Перед ходом
схватить, % Ход
состояние( середина, наящике, середина, имеет) ).
% После хода
В этом факте говорится о том, что после хода у обезьяны уже есть банан и что она осталась на ящике в середине комнаты.
Таким же способом можно выразить и тот факт, что обезьяна, находясь на полу, может перейти из любой горизонтальной позиции P1 в любую позицию Р2. Обезьяна может это сделать независимо от позиции ящика, а также независимо от того, есть у нее банан или нет. Все это можно записать в виде следующего прологовского факта:
