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