Файл: Управлениелогическимвыводом.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):-N1is N-1,factorial(N1,F1), FisN*F1.

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

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

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

sign(X,1). 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 AfterFail-возвратпослеотказа).Предикатотказа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-метода(UserDefinedRepeat-повторение,управляемоепользователем).Встроенный предикат 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!].

---