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

В Прологе встроенный механизм поиска с возвратом может привести к

поиску ненужных решений, в результате чего теряется эффективность. Напри-

мер, когда желательно найти только единственное решение по данному вопро-

су. В других случаях может быть необходимым заставить Турбо Пролог про-

должать поиск дополнительных решений, даже если бы определенное целевое

утверждение уже согласовано. В подобных ситуациях необходимо управлять

процессом поиска с возвратом. В этом разделе показаны некоторые методы,

которые вы сможете использовать для управления поиском решений ваших це-

левых утверждений, выполняемым Турбо Прологом.

Турбо Пролог обеспечивает два инструментальных средства, которые да-

ют возможность управлять механизмом поиска с возвратом: предикат fail,

который используется для поддержания поиска с возвратом, и cut, или отсе-

чение (обозначается !), - используется для предотвращения поиска с возв-

ратом.

Использование предиката fail.

Турбо Пролог начинает поиск с возвратом, когда обращение завершается

неудачно. В определенных ситуациях бывает необходимо выполнить поиск с

возвратом, чтобы найти другие решения. Турбо Пролог поддерживает специ-

альный предикат, fail, вызывающий аварийное завершение, и следовательно

поддерживающий поиск с возвратом. Действие предиката fail равносильно эф-

фекту от сравнения 2=3 или другой невозможной подцели. Программа

CH05EX06. PRO иллюстрирует использование этого специального предиката.

/* Program CH05EX06.PRO - Использование предиката fail */

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) двояко:

1. Как вопрос системе Турбо Пролог по подсказке Goal: (как внешнее

целевое утверждение)

2. Внутри раздела программы goal (как внутреннее целевое утвержде-

ние).

Вот пример внешнего целевого утверждения:

Goal: father(X,Y),

father(Y,B).

Получив father(X,Y), как внешнее целевое утверждение, Турбо Пролог

напечатает все возможные решения привычным вам образом:

X= .... , Y= .... , B= ....

X= .... , Y= .... , B= ....

.... Solutions

Получив father(X,Y), как внутреннее целевое утверждение, Турбо Про-

лог продолжит работу со следующей подцелью после того, как первое обраще-

ние к father будет согласовано.

После того, как внутреннее целевое утверждение полностью выполнено,

ничто не говорит Турбо Прологу о необходимости поиска с возвратом. Поэто-

му внутреннее обращение к father приведет только к одному решению. Однако

предикат everybody (в программе CH05EX06.PRO) использует fail для поддер-

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

Задача предиката everybody - выдать более опрятный ответ в результа-

те работы программы. Сравните ответы к двум предыдущим целевым утвержде-

ниям:

Goal: father(X,Y)

X=leonard, Y=katherine

X=carl, Y=jason

X=carl, Y=marilyn

3 Solutions

и

Goal: everybody

leonard is katherine's father

carl is jason's father

carl is marilyn's father

No

Предикат everybody использует поиск с возвратом с тем, чтобы полу-

чить больше решений для father(X, Y), заставляя Пролог выполнять поиск с

возвратом сквозь тело правила everybody:

father(X, Y), write(X," is ",Y,"'s father\n"), fail

fail никогда не может быть согласован, поэтому Турбо Пролог вынужден вы-

полнять поиск с возвратом. При поиске с возвратом Пролог возвращается к

последнему обращению, которое может произвести множественные решения. Та-

кое обращение называют недетерминированным, в противоположность детерми-

нированному, которое может произвести только одно решение. Предикат write

не может быть вновь согласован (он не может предложить новых решений),

поэтому Турбо Пролог должен опять выполнить поиск с возвратом, на этот

раз к первой подцели в правиле.

Обратите внимание, что помещать подцель после fail в теле правила

бесполезно. Так как предикат fail все время завершается неудачно, нет ни-

какой возможности для достижения подцели, расположенной после fail.