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

Братко Иван

Попытка применить правило 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, вне зависимости от наличия отсечения в предложении, которое используется для достижения С.

5.2. Примеры, использующие отсечение 

5.2.1. Вычисление максимума

Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения

mах( X, Y, Мах)

где Мах = X, если X больше или равен Y, и Мах есть Y, если X меньше Y. Это соответствует двум таким предложениям:

mах( X, Y, X) :- X >= Y.

max( X, Y, Y) :- X < Y.

Эти правила являются взаимно исключающими. Если выполняется первое, второе обязательно потерпит неудачу. Если неудачу терпит первое, второе обязательно должно выполниться. Поэтому возможна более экономная формулировка, использующая понятие "иначе":

 если X ≥ Y, то Мах = X,

 иначе Мах = Y.

На Прологе это записывается при помощи отсечения:

mах( X, Y, X) :- X >= Y, !.

mах( X, Y, Y).

5.2.2. Процедура проверки принадлежности списку, дающая единственное решение

Для того, чтобы узнать, принадлежит ли X списку L, мы пользовались отношением

принадлежит( X, L)

Программа была следующей:

принадлежит( X, [X | L] ).

принадлежит X, [Y | L] ) :- принадлежит( X, L).

Эта программа дает "недетерминированный" ответ: если X встречается в списке несколько раз, то будет найдено каждое его вхождение. Исправить этот недостаток не трудно: нужно только предотвратить дальнейший перебор сразу же после того, как будет найден первый X, а это произойдет, как только в первом предложении наступит успех. Измененная программа выглядит так:

принадлежит( X, [X | L] ) :- !.

принадлежит( X, [Y | L] ) :- принадлежит( X, L).