На этом шаге мы рассмотрим управление поиском решений.
Встроенным механизм поиска с возвратом в Прологе может принести к поиску не нужных решений, в результате чего теряется эффективность, например, когда желательно найти только одно решение. В других случаях может оказаться необходимым продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано. В этом шаге показаны некоторые методы, которые можно использовать для управления поиском решений ваших целевых утверждений.
Пролог обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cut или отсечение (обозначается !) - для запрета возможности возврата.
Использование предиката fail
Пролог начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Пролог поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2 = 3 или другой невозможной подцели. Программа pro30_1.pro иллюстрирует использование этого специального предиката.
domains
name=symbol
predicates
father(name, name)
everybody
clauses
father(leonard,katherine).
father(carl,jason).
father(carl,marilyn).
everybody:-
father(X,Y),
write(X," is ",Y,"'s father\n"),
fail.
Пусть необходимо найти все решения цели father (X,Y). Цель можно записать как
father (X,Y).
Пролог найдет все решения цели father (X,Y) и отобразит значения всех переменных следующим образом:
X=leonard,Y=katherine X=carl,Y=jason X=carl,Y=marilyn
Нo если вы скомпилируете эту программу и запустите ее (командой меню Run), то Пролог найдет только первое подходящее решение для father (X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к father приведет только к одному решению. Как же найти все возможные решения? Предикат everybody в программе использует fail для поддержки поиска с возвратом.
Задачa предиката everybody - найти все решения для father и выдать полный ответ. Сравните предыдущие ответы Пролога с целью father (X,Y) и ответы на выполнение следующей цели:
everybody.
leonard is katherine's father
carl is jason's father
carl is marilyn's father
Предикат everybody использует поиск с возвратом с тем, чтобы получить все решения для father (X,Y), заставляя Пролог выполнять поиск с возвратом сквозь тело правила everybody:
father(X,Y), write(X, " is ",Y, "'s father\n"), fail.
fail не может быть согласован (он всегда неуспешен), поэтому Пролог вынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может произвести только одно решение.
Предикат write не может быть вновь согласован (он не может предложить новых решений), поэтому Пролог должен выполнить откат дальше, на этот раз к первой подцели в правиле.
Обратите внимание, что помещать подцель после fail в теле правила бесполезно. Предикат fail все время завершается неудачно, нет возможности для достижения подцели, расположенной после fail.
На следующем шаге мы рассмотрим отсечения.
