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

При вычислении первой цели f( 1, Y) Y конкретизируется нулем. Поэтому вторая цель становится такой:

2 < 0

Она терпит неудачу, а поэтому и весь список целей также терпит неудачу. Это очевидно, однако перед тем как признать, что такому списку целей удовлетворить нельзя, пролог-система при помощи возвратов попытается проверить еще две бесполезные в данном случае альтернативы. Пошаговое описание процесса вычислений приводится на рис. 5.2.

Три правила, входящие в отношение f, являются взаимоисключающими, поэтому успех возможен самое большее в одном из них. Следовательно, мы (но не пролог-система) знаем, что, как только успех наступил в одном из них, нет смысла проверять остальные, поскольку они все равно обречены на неудачу. В примере, приведенном на рис. 5.2, о том, что в правиле 1 наступил успех, становится известно в точке, обозначенной словом "ОТСЕЧЕНИЕ". Для предотвращения бессмысленного перебора мы должны явно указать пролог-системе, что не нужно осуществлять возврат из этой точки. Мы можем сделать это при помощи конструкции отсечения. "Отсечение" записывается в виде символа '!', который вставляется между целями и играет роль некоторой псевдоцели. Вот наша программа, переписанная с использованием отсечения:

f( X, 0) :- X < 3, !.
f( X, 2) :- 3 =< X, X < 6, !.
f( X, 4) :- 6 =< X.

Символ '!' предотвращает возврат из тех точек программы, в которых он поставлен. Если мы теперь спросим

?- f( 1, Y), 2 < Y.

то пролог-система породит левую ветвь дерева, изображенного на рис. 5.2. Эта ветвь потерпит неудачу на цели 2 < 0. Система попытается сделать возврат, но вернуться она сможет не далее точки, помеченной в программе символом '!'. Альтернативные ветви, соответствующие правилу 2 и правилу 3, порождены не будут.

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

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

5.1.2. Эксперимент 2

Проделаем теперь еще один эксперимент со второй версией нашей программы. Предположим, мы задаем вопрос:

?- f( 7, Y).
Y = 4

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

Попытка применить правило 1:

 7 < 3 терпит неудачу, происходит возврат, и попытка применить правило 2 (точка отсечения достигнута не была)

Попытка применить правило 2:

 3 ≤ 7 успех, но 7 < 6 терпит неудачу; возврат и попытка применить правило 3 (точка отсечения снова не достигнута)

Попытка применить правило 3:

 6 ≤ 7 — успех

Приведенные этапы вычисления обнаруживают еще один источник неэффективности. В начале выясняется, что X < 3 не является истиной (7 < 3 терпит неудачу). Следующая цель — 3 =< X (3 ≤ 7 — успех). Но нам известно, что, если первая проверка неуспешна, то вторая обязательно будет успешной, так как второе целевое утверждение является отрицанием первого. Следовательно, вторая проверка лишняя и соответствующую цель можно опустить. То же самое верно и для цели 6 =< X в правиле 3. Все эти соображения приводят к следующей, более экономной формулировке наших трех правил:

 если X < 3, то Y = 0

 иначе, если 3 ≤ X и X < 6, то Y = 2,

 иначе Y = 4.

Теперь мы можем опустить в нашей программе те условия, которые обязательно выполняются при любом вычислении. Получается третья версия программы:

f( X, 0) :- X < 3, !.
f( X, 2) :- X < 6, !.
f( X, 4).

Эта программа дает тот же результат, что и исходная, но более эффективна, чем обе предыдущие. Однако, что будет, если мы теперь удалим отсечения? Программа станет такой:

f( X, 0) :- X < 3.
f( X, 2) :- X < 6.
f( X, 4).

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

?- f( 1, Y).

Y = 0;
Y = 2;
Y = 4;

nо (нет)

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

Более точный смысл механизма отсечений можно сформулировать следующим образом:

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

Чтобы прояснить смысл этого определения, рассмотрим предложение вида

H :- В1, В2, ..., Вm, !, ..., Вn.

Будем считать, что это предложение активизировалось, когда некоторая цель G сопоставилась с H. Тогда G является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях В1, …, Вm. При выполнении отсечения это (текущее) решение В1, …, Вm "замораживается" и все возможные оставшиеся альтернативы больше не рассматриваются. Далее, цель G связывается теперь с этим предложением: любая попытка сопоставить G с головой какого-либо другого предложения пресекается.

Применим эти правила к следующему примеру:

С :- P, Q, R, !, S, T, U.
С :- V.
А :- В, С, D.
?- А.

Здесь А, В, С, D, P и т.д. имеют синтаксис термов. Отсечение повлияет на вычисление цели С следующим образом. Перебор будет возможен в списке целей P, Q, R; однако, как только точка отсечения будет достигнута, все альтернативные решения для этого списка изымаются из рассмотрения. Альтернативное предложение, входящее в С:

С :- V.

также не будет учитываться. Тем не менее, перебор будет возможен в списке целей S, T, U. "Цель-родитель" предложения, содержащего отсечения, — это цель С в предложении

А :- В, С, D.

Поэтому отсечение повлияет только на цель С. С другой стороны, оно будет "невидимо" из цели А. Таким образом, автоматический перебор все равно будет происходить в списке целей В, С, D, вне зависимости от наличия отсечения в предложении, которое используется для достижения С.