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

?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:

(1) можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

Применение второго предложения из можетзавладеть("может2") породило бы

(2) ход( состояние( удвери, наполу, уокна, неимеет), М', S2'),

можетзавладеть( S2')

С помощью хода перейти( уокна, Р2')получилось бы

(3) можетзавладеть( состояние( Р2', наполу, уокна, неимеет) )

Повторное использование предложения "может2" превратило бы список целей в

(4) ход( состояние(Р2', наполу, уокна, неимеет), М'', S2''),

можетзавладеть( S2'')

С этого момента начались бы отличия. Первым предложением, голова которого сопоставима с первой целью из этого списка, было бы теперь "перейти" (а не "залезть", как раньше). Конкретизация стала бы следующей:

S2'' = состояние( Р2'', наполу, уокна, неимеет).

Поэтому список целей стал бы таким:

(5) можетзавладеть( состояние( Р2'', наполу, уокна, неимеет) )

Применение предложения "может2" дало бы

(6) ход( cocтояниe( P2'', наполу, yoкнa, неимeeт), M''', S2'''),

можетзавладеть( S2''')

Снова первый было бы попробовано "перейти" и получилось бы

(7) можетзавладеть( состояние( Р2''', наполу, уокна, неимеет) )

Сравним теперь цели (3), (5) и (7). Они похожи и отличаются лишь одной переменной, которая по очереди имела имена Р', Р'' и P'''. Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.

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

Теперь уместно спросить: "Не можем ли мы внести какое-либо более существенное изменение в нашу программу, так чтобы полностью исключить опасность зацикливания? Или же нам всегда придется рассчитывать на удачный порядок предложений и целей?" Как оказывается, программы, в особенности большие, были бы чересчур ненадежными, если бы можно было рассчитывать лишь на некоторый удачный порядок. Существует несколько других методов, позволяющих избежать зацикливания и являющихся более общими и надежными, чем сам по себе метод упорядочивания. Такие методы будут систематически использоваться дальше в книге, в особенности в тех главах, в которых пойдет речь о нахождении путей (в графах), о решения интеллектуальных задач и о переборе.

Уже в примерах программ гл. 1 существовала скрытая опасность зацикливания. Определение отношения предокв этой главе было таким:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

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

В соответствии с декларативной семантикой Пролога мы можем, не меняя декларативного смысла, изменить

(1) порядок предложений в программе и

(2) порядок целей в телах предложений.

Процедура предоксостоит из двух предложений, и одно из них содержит в своем теле две цели. Возможны, поэтому, четыре варианта данной программы, все с одинаковым декларативным смыслом. Эти четыре варианта можно получить, если

(1) поменять местами оба предложения и

(2) поменять местами цели в каждом из этих двух последовательностей предложений.

Соответствующие процедуры, названные пред1, пред2, пред3и пред4, показаны на рис. 2.16.

Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать, отношение родительопределенным так, как показано на рис. 1.1 гл. 1. и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения предок:

?- пред1( том, пат).

да

?- пред2( том, пат).

да

?- пред3( том, пат).

да

?- пред4( том, пат).

% Четыре версии программы предок

% Исходная версия

пред1( X, Z) :-

родитель( X, Z).

пред1( X, Z) :-

родитель( X, Y),

пред1( Y, Z).

% Вариант а: изменение порядка предложений в исходной версии

пред2( X, Z) :-

родитель( X, Y),

пред2( Y, Z).

пред2( X, Z) :-

родитель( X, Z).

% Вариант b: изменение порядка целей во втором предложении

% исходной версии

пред3( X, Z) :-

родитель( X, Z).

пред3( X, Z) :-

пред3( X, Y),

родитель( Y, Z).

% Вариант с: изменение порядка предложений и целей в исходной

% версии

пред4( X, Z) :-

пред4( X, Y),

родитель( Y, Z).

пред4( X, Z):-

родитель( X, Z).

Рис. 2.16. Четыре версии программы предок.

В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".

На рис. 1.11 гл. 1 были показаны все шаги вычислений по пред1(в главе 1 она называлась предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по пред2, пред3и пред4. На рис. 2.17 (с) ясно видно, что работа пред4 — бесперспективна, а рис. 2.17(а) показывает, что пред2довольно неэффективна по сравнению с пред1: пред2производит значительно больший перебор и делает больше возвратов по фамильному дереву.