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

Братко Иван

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

(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

производит значительно больший перебор и делает больше возвратов по фамильному дереву.

Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения

предок

основаны на двух соображениях:

• более простое — нужно проверить, не удовлетворяют ли два аргумента отношения

предок

отношению

родитель

;

• более сложное — найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями

родитель

и

предок

).

Из всех четырех вариантов отношения

предок

,

пред1

использует наиболее простое соображение в первую очередь. В противоположность этому

пред4

всегда сначала пробует использовать самое сложное.

Пред2

 и

пред3

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

пред1

следует предпочесть просто на основании правила "самое простое пробуй в первую очередь".

Наши четыре варианта процедуры

предок

можно далее сравнить, рассмотрев вопрос: "На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?" Оказывается,

пред1

и

пред2

оба способны найти ответ на любой вид вопроса относительно предков;

пред4

никогда не находит ответа, а

пред3

иногда может найти, иногда нет. Вот пример вопроса, на который

пред4

ответить не может:

?- пред3( лиз, джим).

Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно и

пред3

нельзя признать верным с точки зрения процедурного смысла.

Рис. 2.17. Поведение трех вариантов формулировки отношения

предок

при ответе на вопрос, является ли Том предком Пат?

2.6.3. Сочетание декларативного и процедурного подходов

В предыдущем разделе было показано, что порядок целей и предложений имеет существенное значение. Более того, существуют программы, которые верны в декларативном смысле, но на практике не работают. Такое противоречие между декларативным и процедурным смыслами может вызвать недовольство. Кто-нибудь спросит: "А почему вообще не забыть о декларативном смысле?" Такое пожелание становится особенно сильным, когда рассматриваются предложения типа:

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