Основные правила поиска с возвратом
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)
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 дать через анонимные переменные.
Если в данной редакции запустить программу на выполнение, то она будет работать точно так же, как и в первом варианте. Более того, в первом варианте программы можно добавить зеленое отсечение в те же термы. Это никак не повлияет на работу программы, но сократит количество выполняемых операций.