ОТСЕЧЕНИЕ(CUT)
Для управления механизмом перебора используются встроенные предикаты: отсечение («!») и неудача (fail). Предикат отсечения применяется, когда надо изменить процесс возврата.
ПРОГРАММА 1.
a(1,1). %(1)
b(2). %(2)
b(3). %(3)
c(2). %(4)
c(3). %(5)
d(4). %(6)
a(X,Y):-b(X),!,c(Y). %(7)
a(X,X):-d(X). %(8)
?- a(N,M).
Если бы не было предиката отсечения «!», то мы получили бы шесть ответов: N=1,M=1; N=2,M=2; N=2,M=3; N=3,M=2; N=3,M=3; N=4,M=4. При выполнении предиката отсечения («проходе» «!» слева направо), предикаты, стоящие в правиле (7) левее «!», «замораживаются», т.е. устраняются все их точки ветвления и прекращается поиск альтернативных решений для b(X), а для a(X,Y) - использование альтернативных утверждений (8), лежащих ниже правила (7). Для предиката c(Y) продолжается поиск альтернативных решений, но невозможен возврат левее «!». Получим три ответа: N=1,M=1; N=2,M=2; N=2,M=3.
A :- B , C , D , ! , E , F.
Если подцель «E,F» - неуспешна, бектрекинг попадает на «!», и вся цель A - неуспешна.
Можно выделить три случая использования отсечения.
I. Если при некоторых условиях какая-либо цель никогда не должна быть успешной, комбинация cut-fail исключит выполнение остальных правил, согласующихся с этой целью.
Например, предикат not(P) можно определить с помощью отсечения следующим образом:
not(P) :- P,!,fail.
not(_) :- true.
II. Для устранения бесконечных циклов.
В программе 2, приведенной ниже, с помощью отсечения обеспечивается выход из рекурсии. При выполнении правила 1 по предикату отсечения происходит замораживание всех альтернативных утверждений для factorial, стоящих ниже правила 1, (т.е. прекращается выполнение рекурсивного правила 2).
ПРОГРАММА 2.
factorial(0, 1):- !. /* Условие выхода из рекурсии 0!=1 */
factorial(N,F) :- N1 is N-1, factorial(N1, F1), F is N*F1.
III. При программировании взаимоисключающих утверждений.
Например,
sign(X,-1):- X < 0,!.
sign(X,0):- X = 0,!.
sign(X,1). [5] % X > 0.
ЗАДАНИЕ 4.1
Нарисуйте дерево вывода ответа на запрос
?- factorial(3,F).
ЗАДАНИЕ 4.2
Напишите программу для определения размера одежды, используя предикат размер(Номер,Рост) и следующие критерии определения номера:
| Номер | |||||
| Интервал | [158,164) | [164,170) | [170,176) | [176,182) | [182,188] |
Например, второй рост можно определить правилом
размер(2,R):- R >= 164, R < 170.
Добейтесь наименьшего числа сравнений в программе, используя отсечение. Рассмотрите случай неуспешного определения роста.
ОРГАНИЗАЦИЯ ЦИКЛА BAF-МЕТОД
Первый метод организации повторений получил название BAF-метода (Backtrack After Fail - возврат после отказа).
Предикат отказа fail используется для получения гарантированного неуспеха при доказательстве некоторой цели. Например, правило
A:- B,fail.
будет выполняться столько раз, сколько имеется альтернатив для B в этом правиле.
ПРОГРАММА 3.
a:- write(1).
a:- write(2).
b(X):- a,X='еще'.
c:- a.
d:- a,fail.
?-b(X).
?-c.
?-d.