Логическое программирование

       

Ограничение перебора


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

Рассмотрим двухступенчатую функцию.

Правило 1:  если X<3, то Y=0

Правило 2:  если 3£X и X<6, то Y=2

Правило 3:   если 6£ X, то Y=4

На Прологе это можно выразить с помощью бинарного отношения f(X,Y) так:

f(X,0) :- X<3.

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

f(X,4) :-  6=<X.

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

·     Эксперимент 1.

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



Три правила, входящие в отношение f, являются взаимоисключающими, поэтому успех возможен самое большое в одном из них. Следовательно, мы (но не пролог-система) знаем, что, как только успех наступил в одном из них, нет смысла проверять остальные, поскольку все равно они обречены на неудачу. О том, что в правиле 1 наступил успех, становится известно в точке, обозначенной словом “отсечение”. Для предотвращения бессмысленного перебора мы должны явно указать пролог-системе, что не нужно осуществлять возврат из этой точки.

Мы можем сделать это при помощи конструкции отсечения. “Отсечение” записывается в виде символа ‘!’, который вставляется между целями и играет роль некоторой псевдоцели.

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

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

f(x,4) :-  6 =< X.

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

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


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

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

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

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

?- f(7,Y).

Y=4

Yes

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

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

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;

No

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

Назовем “целью-родителем” ту цель, которая унифицировалась с головой предложения, содержащего отсечение.


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


Пример:

H :- B1,B2,...,Bm,!,...,Bn.

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

Пример:

C :- P,Q,R,!,S,T,U.

C :- V.

A :- B,C,D.

?- A.

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

C:-V.

также не будет учитываться. Тем не менее, перебор будет возможен в списке целей S,T,U. Отсечение повлияет только на цель C. Оно будет невидимо из цели A, и автоматический перебор все равно будет происходить в списке целей B,C,D вне зависимости от наличия отсечения в предложении, которое используется для достижения C.


Содержание раздела