Файл: Управлениелогическимвыводом.docx

4. 
   УПРАВЛЕНИЕЛОГИЧЕСКИМВЫВОДОМ
   

ЦЕЛЬ: Знакомство с механизмами управления логическим выводом в Прологе. Отсечение. Моделирование циклов в Прологе.

1. ОТСЕЧЕНИЕ(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.



Если подцель «E,F»- неуспешна, бектрекинг попадает на «!», и вся цель

A - неуспешна.

Можно выделить три случая использования отсечения.

1. 
   Если при некоторых условиях какая-либо цель никогда не должна быть успешной, комбинация cut-failисключит выполнение остальных правил, согласующихся с этой целью.
   

Например, предикат not(P)можно определить с помощью отсечения следующим

---

образом:

not(P) :- P,!,fail. not(_) :- true.

2. 
   Для устранения бесконечных циклов.
   

В программе 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.

3. 
   При программировании взаимоисключающих утверждений. Например,
   

sign(X,-1):- X < 0,!.

sign(X,0):- X = 0,!.

sign(X,1). ¹ % X > 0.

ЗАДАНИЕ 4.1

Нарисуйте дерево вывода ответа на запрос

?- factorial(3,F).

ЗАДАНИЕ 4.2

Напишите программу для определения размера одежды, используя предикат размер(Номер,Рост) и следующие критерии определения номера:

Номер	1	2	3	4	5
Интервал	[158,164)	[164,170)	[170,176)	[176,182)	[182,188]

Например, второй рост можно определить правилом

размер(2,R):- R >= 164, R < 170.

Добейтесь наименьшего числа сравнений в программе, используя отсечение. Рассмотрите случай неуспешного определения роста.

2. ОРГАНИЗАЦИЯ ЦИКЛА 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.

ЗАДАНИЕ 4.3

Выполните программу 3 с данными запросами. Объясните результаты и нарисуйте деревья вывода.

ЗАДАНИЕ 4.4

Используя предикат fail, напишите правило, которое позволило бы распечатать столицы всех стран из базы.

country('England','London'). country('Russia','Moscow'). country('France','Paris').

country('China','Pekin').

country('Japan','Tokyo').

country('Italy','Rome').

3. 
   ОРГАНИЗАЦИЯ ЦИКЛА UDR-МЕТОД
   

Второй способ организации повторений получил название UDR-метода

(User Defined Repeat - повторение, управляемое пользователем).

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

Предикат repeat определяется следующим образом:

repeat.

repeat:- repeat.

ЗАМЕЧАНИЕ. Предикат repeat /0 является встроенным в SWI-Prolog. При попытке его переопределения интерпретатор скорей всего выдаст сообщение об ошибке.

ЗАДАНИЕ 4.5

Выполните программу 3 с запросом

?- repeat,a,fail.

Постройте дерево вывода и объясните результат.

---

ПРОГРАММА 4.

/* ввод с клавиатуры слов и вывод их на экран до тех пор, пока не будет введено слово stop (в конце терма, вводимого read, необходимо поставить точку и нажать клавишу Enter) */

r:- repeat, read(X), write(X), X=stop.

?-r.

Вывод схематично можно представить так:

ЗАДАНИЕ 4.6

Выполните программу 4 в режиме трассировки².

Можно предложить более общую схему организации цикла с помощью предиката repeatпри выполнении некоторого условия.

4. ИСПОЛЬЗОВАНИЕ НАДРЕЗОВ (SNIP)

Надрез обозначается открывающей скобкой [!и закрывающей скобкой !].

Например, для правила

цель:- подцель1,[! подцель2,подцель3 !],подцель4.

действие надреза распространяется на подцели подцель2и подцель3,

расположенные между этими двумя скобками.

Snip аналогичен cut, однако отличается от него тем, что если после бектрекинга управление передастся snip, весь предикат неуспешным не будет. Бектрекинг лишь "пропустит" те подцели, которые находятся внутри snip и продолжится для подцелей, которые расположены раньше snip³.

Отличие надреза от отсечения:

A :- B, [!C, D!], E.

A :- B, C, D, !, E.
Для cut если E неуспешна, бектрекинг попадает на cut и весь предикат A неуспешен, в отличие от ситуации со snip. Для snip, если подцель Е неуспешна, то бектрекинг попадает на подцель B.

Надрезы целесообразно использовать в случаях, когда нужно ограничить

---

бектрекинг для исключения ненужного поиска, но отсечение не требуется.

УПРАЖНЕНИЕ. Вообще говоря, надрезы не реализованы в SWI-Prolog. Используя отсечение, реализуйте надрез (т.е. «заморозьте» точки возврата только для предикатов, которые должны быть внутри надреза). Одна из реализаций может быть представлена в виде схемы (по результату равносильна вышеприведённой схеме надреза):

A:-B, T, E.

T:-C, D, !.

b(2). %(1)

b(3). %(2)

c(2). %(3)

c(3). %(4)

d(4). %(5)

d(5). %(6)

e(10). %(7)

e(11). %(8)

e(12). %(9)

a(X,Y,Z,W):-b(X),[! c(Y), d (Z) !],e(W). %(10) a(X,X,X,X):-d(X). %(11)

/* В SWI-Prolog надрез можно реализовать через отсечение следующим образом: */

a(X,Y,Z,W):-b(X),f(Y,Z),e(W). a(X,X,X,X):-d(X).

f(Y,Z):-C(Y),d(Z),!.

2 ?- a(X,Y,Z,W).
X = 2,Y = 2,Z = 4,W = 10 ; X = 2,Y = 2,Z = 4,W = 11 ; X = 2,Y = 2,Z = 4,W = 12 ; X = 3,Y = 2,Z = 4,W = 10 ; X = 3,Y = 2,Z = 4,W = 11 ; X = 3,Y = 2,Z = 4,W = 12 ; X = 4,Y = 4,Z = 4,W = 4 ; X = 5,Y = 5,Z = 5,W = 5.
Как видно из примера надрез «замораживает» предикаты c(Y) и d(Z) в строке (10). Поэтому при получении вывода с использованием этой строки значения переменных Y, Z при поиске всех альтернативных решений не меняются – для c(Y) и d(Z) не ищется других альтернатив, кроме как c(2) и d(4) соответственно.

ЗАДАНИЕ 4.7

Используйте базу данных из задания 1.6 лабораторной работы 1. Добавьте факты для каждого животного X

животное(X).

Для исключения повторения названия животных на запросы

"Ктоживетхотябы(ровно)вдвухсредахобитания?"

можно использовать надрез

цель(X):- животное(X),[!живет(X,Y),живет(X,Z),Y\=Z!].

---