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