Отсечение(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