Основные правила поиска с возвратом

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

2. Предикатные предложения проверяются в том порядке, в каком они появляются в программе, сверху вниз.

3. Когда подцель соответствует заголовку правила, далее должно быть согласовано тело этого правила: тело правила теперь образует новое множество подцелей для согласования.

4. Целевое утверждение является согласованным, когда соответствующий факт найден для каждой оконечности (листа) целевого дерева.

При помощи поиска с возвратом в режиме тестирования программы будут найдены все возможные решения задачи.

Пример 7. (слайд 12)

Для задачи, условие которой сформулировано в примере1 (без учета высказывания B), организовать поиск решений для ответа на вопросы: «Кто из работников может быть поваром (администратором, кондитером)?»

DOMAINS

name, prof = symbol

PREDICATES

профессия(prof)

сотрудник(name)

должность(name,prof)

CLAUSES

профессия(администратор).

профессия(повар). (**)

профессия(кондитер).

профессия(кассир).

профессия(дворник).

сотрудник(голубева, жен). (***)

сотрудник(иванова, жен).

сотрудник(васин, муж).

сотрудник(смирнов, муж).

сотрудник(азаров, муж).

должность(X,Y):- (*)

сотрудник(X), X=голубева, профессия(Y)), not(Y=повар).

должность(X,Y):-

сотрудник(X), X = иванова, профессия(Y), not(Y=кондитер),

not(Y=кассир), not(Y=повар).

должность(X,Y):-

сотрудник(X), X=васин, профессия(Y), not(Y=администратор),

not(Y=повар), not(Y=кассир),

not(Y=кондитер).

должность(X,Y):-

сотрудник(X), X=смирнов, профессия(Y), not(Y=кондитер),

not(Y=кассир).

должность(X,Y):-

сотрудник(X), X=азаров, профессия(Y), not(Y=кассир).

GOAL

должность(Кто, повар).

% должность(Кто, администратор).

% должность(Кто, кондитер).

n

На этом примере полезно рассмотреть процесс поиска с возвратом. Пролог будет искать решение, производя с вершины программы поиск соответствия с целью должность(Кто, повар). В разделе предложений терм (*) содержит правило, заголовок которого может быть успешно согласован с целевым утверждением. Переменная Кто будет согласована с переменной X, а переменная Y конкретизирована значением повар. Далее Пролог продвигается по процедуре описания предиката сотрудник. И сразу же переменная X будет конкретизирована значением голубева, после чего успешным будет предикат равенства X=голубева, а Пролог, действуя от вершины программы, приступит к согласованию подцели профессия(повар), поскольку переменная Y конкретизирована. Терм (**) обеспечивает ее успех. Основная цель согласована, получено решение. Не следует забывать, что терм (***) помечен точкой отката при согласовании подцели сотрудник(X). Пролог совершит откат в эту точку, затем будет проводить сопоставление предиката сотрудник, но необходимость согласования последующего предиката равенства X = голубева к успеху не приведет. Полог совершит откат к предыдущей точке отката, которая находится в терме (*). После чего Пролог приступит к согласованию основной цели с правилом, сформулированным для того же предиката должность(X,Y) в терме, следующем за (*). Дальнейшие действия будут аналогичны вышеописанным. Заметим, что первая и вторая цели будут иметь по 4 решения, а третья – два.

Управление поиском решений

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

Предикат fail

Предикат fail используется для инициализации поиска с возвратом.

Рассмотрим, как работает предикат fail. Действует fail очень просто – цель с использованием данного предиката НИКОГДА не доказывается, а, следовательно, всегда включается поиск с возвратом. Для получения такого же эффекта можно сформулировать, например, вот такую цель: 3=2. Эффект будет абсолютно тем же самым. Предикат fail используется в тех случаях, когда в программе есть внутренняя цель, и необходимо позаботиться о нахождении всех возможных решений.

Пример 8. (слайд 13)

Распечатать названия всех континентов, относительно которых есть данные в разделе предложений.

PREDICATES

continent(string)

print

 

CLAUSES

continent("Евразия").

continent("Северная Америка").

continent("Южная Америка").

continent("Африка").

continent("Антарктида").

continent("Австралия").

 

print:-

continent(Continent_name),

write(Continent_name,"\n"), fail.

print.

 

GOAL

print.

Если в теле правила print отсутствует предикат fail, то тестирование программы выдаст только первое подходящее решение. Поставим в конце правила предикат fail. В результате тестирования будут выданы все возможные решения.

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

Помещать подцель после fail в теле правила бесполезно, т.к. такая подцель никогда не будет достигнута.

Отсечение (cut)

Отсечение cut (обозначается!) используется для запрета возможности возврата.

Через отсечение невозможно совершить откат (поиск с возвратом). Отсечение помещается в программу таким же образом, как и подцель в теле правила. Когда процесс проходит через отсечение, немедленно удовлетворяется обращение к cut и выполняется обращение к очередной подцели (если таковая имеется). Однажды пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатываемый предикат (предикат, содержащий отсечение).

Отсечение применяется в одном из двух основных случаев:

а) если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям – это зеленое отсечение;

б) если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей – это красное отсечение.

Пример 9. (слайды 14-15)

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

PREDICATES

vid(integer,integer,integer)

tip(integer,integer,integer)

suchestv(integer,integer,integer)

CLAUSES

suchestv(A,B,C):-

(A+B-C)*(A+C-B)*(B+C-A)>0,

write("треугольник существует"), nl,

vid(A,B,C), tip(A,B,C). //1

suchestv(A,B,C):-

(A+B-C)*(A+C-B)*(B+C-A)<=0,

write("треугольник не существует"),nl.

vid(A,B,C):-

(A*A+B*B-C*C)*(A*A+C*C-B*B)*(B*B+C*C-A*A)>0,

write("остроугольный"),nl.

vid(A,B,C):-

(A*A+B*B-C*C)*(A*A+C*C-B*B)*(B*B+C*C-A*A)<0,

write("тупоугольный"),nl.

vid(A,B,C):-

(A*A+B*B-C*C)*(A*A+C*C-B*B)*(B*B+C*C-A*A)=0,

write("прямоугольный"),nl.

tip(A,B,C):-

A=C, B=C,

write("равносторонний"), nl.

tip(A,B,C):-

(A-B)*(B-C)*(C-A)=0,

write("равнобедренный"), nl.

tip(A,B,C):-

A<>B,B<>C,C<>A,

write("обычного вида"), nl.

 

GOAL

random(10,A),write(A),nl,

random(10,B),write(B),nl,

random(10,C),write(C),nl,

A*B*C<>0,

suchestv(A,B,C),

readchar(_).

Программа при помощи встроенных предикатов random и write конкретизирует значения переменных A, B, C,выводит их на экран и приступает к согласованию предиката существования треугольника. В процессе согласования терма 1 программа будет обращаться к правилам для определения вида и типа треугольников.

Если бы мы первоначально записали правила раздела CLAUSESнесколько иначе, а именно (слайд 16)

CLAUSES

suchestv(A,B,C):- //1

(A+B-C)*(A+C-B)*(B+C-A)>0,ъ

write("треугольник существует"), nl,

vid(A,B,C), tip(A,B,C),!.

suchestv(_,_,_):- //2

write("треугольник не существует"),nl.

 

vid(A,B,C):-

(A*A+B*B-C*C)*(A*A+C*C-B*B)*(B*B+C*C-A*A)>0,

write("остроугольный"),nl,!.

vid(A,B,C):-

(A*A+B*B-C*C)*(A*A+C*C-B*B)*(B*B+C*C-A*A)<0,

write("тупоугольный"),nl,!.

vid(_, _, _):- write("прямоугольный"),nl. //3

 

tip(A,B,C):-

A=C, B=C, write("равносторонний"),!, nl.

tip(A,B,C):-

(A-B)*(B-C)*(C-A)=0, write("равнобедренный"),!, nl.

tip(_, _, _):- //4

write("общего вида"), nl.

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

suchestv(_,_,_):- //2

write("треугольник не существует"),nl.

Похожие действия (убрали условие в термах) относительно предикатов vid(A,B,C) и tip(A,B,C) позволяют охарактеризовать отсечения как красные, а описание термов 3 и 4 дать через анонимные переменные.

Если в данной редакции запустить программу на выполнение, то она будет работать точно так же, как и в первом варианте. Более того, в первом варианте программы можно добавить зеленое отсечение в те же термы. Это никак не повлияет на работу программы, но сократит количество выполняемых операций.