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

В1', …, Вn', G2, …, Gm

(Заметим, что, если С — факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, — привести к успешному завершению.)

Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей

В1'', …, Вn", G2', …, Gm'

• Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С — предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.

Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на рис. 2.11.

Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислитьв том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.

procedure вычислить (Прогр, СписокЦелей, Успех)

Входные параметры:

Прогр: список предложений

СписокЦелей: список целей

Выходной параметр:

Успех: истинностное значение; Успех принимает значение

истина, если список целевых утверждений

(их конъюнкция) истиннен с точки зрения Прогр

Локальные переменные:

Цель: цель

ДругиеЦели : список целей

Достигнуты: истинностное значение

Сопоставились: истинностное значение

Конкрет: конкретизация переменных

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. Вычисление целевых утверждений Пролога.

Всякий раз, как рекурсивный вызов процедуры вычислитьприводят к неуспеху, процесс вычислений возвращается к ПРОСМОТРУи продолжается с того предложения С, которое использовалось последним. Поскольку применение предложения С не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.