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

Братко Иван

черный( X), большой( X)

(3) Просмотр программы для нахождения предложения, сопоставимого с

черный( X)

. Найдено предложение 5:

черный ( кот)

. У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до

большой( кот)

(4) Просмотр программы в поисках цели

большой( кот)

. Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации 

X = кот

. Список целей теперь снова

черный( X), большой( X)

Продолжение просмотра программы ниже предложения 5. Ни одно предложение не

найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):

темный( Z) :- коричневый( Z).

Замена первой цели в списке на

коричневый( X)

, что дает

коричневый( X), большой( X)

(5) Просмотр программы для обнаружения предложения, сопоставимого

коричневый( X)

. Найдено предложение

коричневый( медведь)

. У этого предложения нет тела, поэтому список целей уменьшается до

большой( медведь)

(6) Просмотр программы и обнаружение предложения

большой( медведь)

. У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных такова:

Рис. 2.10. Пример, иллюстрирующий процедурную семантику Пролога: шаги вычислений, выполняемых процедурой

вычислить

.

В главе 1 в разд. "Как пролог-система отвечает на вопросы" мы уже фактически рассмотрели, что делает процедура

вычислить

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

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

Чтобы вычислить список целевых утверждений

 G1, G2, …, Gm

процедура

вычислить

делает следующее:

• Если список целей пуст - завершает работу успешно.

• Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.

• ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

Если С найдено и имеет вид

H :- B1, ..., Вn.

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G1, …, Gm. Пусть С' — это

Н' :- B1', ..., Вn'.

Сопоставляется G1 с H'; пусть S — результирующая конкретизация переменных. В списке целей G1, G2, …, Gm, цель G1 заменяется на список В1', …, Вn', что порождает новый список целей:

В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.

Создать вариант этого предложения