Упражнение на поиск с возвратом.

Используя программу CH05EX03.PRO, решите, что ответит Турбо Пролог

на следующее целевое утверждение:

player(Person1, 9), player(Person2, 10).

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

ем.

Детальный обзор поиска с возвратом.

Овладев знаниями на предыдущем простом примере, вы можете теперь

взглянуть более подробно на то, как работает механизм поиска с возвратом

в Турбо Прологе. Начнем с того, что рассмотрим программу CH05EX04.PRO в

свете следующего целевого утверждения, состоящего из двух подцелей:

likes(X, wine) , likes(X, books)

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

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

целевым деревом:

/\

/ \

/ \

/ \

likes(X,wine) likes(X,books)

Перед началом исследования целевого утверждения целевое дерево сос-

тоит из двух несогласованных подцелей. На последующих изображениях целе-

вого дерева согласованная подцель в целевом дереве будет отмечаться под-

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

целью.

/* Program CH05EX04.PRO */

domains

name, thing = symbol

predicates

likes(name, thing)

reads(name)

is_inquisitive(name)

clauses

likes(john, wine)

likes(lance, skiing)

likes(Z, books) :-

reads(Z), is_inqusitive(Z).

likes(lance, books).

likes(lance, films).

reads(john).

is_inqusitive(john).

Четыре основных принципа поиска с возвратом.

В данном примере целевое дерево демонстрирует, что должны быть сог-

ласованы две подцели. Чтобы достичь этого, Турбо Пролог придерживается

первого фундаментального правила поиска с возвратом:

------------------------------------------------------------

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

------------------------------------------------------------

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

сопоставления предложения, исходя из второго основного правила поиска с

возвратом:

------------------------------------------------------------

Предикатные предложения проверяются в том порядке, в каком

они появляются в программе, сверху вниз.

------------------------------------------------------------

Выполняя программу CH05EX04.PRO, Tурбо Пролог находит предложение,

соответствующее первому факту, определяющему предикат likes. Посмотрите

на целевое дерево теперь.

/\

/ \

/ \

/ \

likes(X,wine) likes(X,books)

-------------

likes(john,wine)

Подцель likes(X, wine) соответствует факту likes(john, wine), и X

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

щую справа подцель.

Обращение ко второй подцели начинает совершенно новый поиск с усло-

вием X=john. Первое предложение

likes(john, wine)

не соответствует подцели

likes(X, books)

так как вино - это вовсе не то же самое, что книги. Поэтому Турбо Пролог

должен проверить следующее предложение, но lance не соответствует значе-

нию X (потому что в данном случае Х связан с john), так что поиск продол-

жается с третьим предложением, определяющим предикат likes:

likes(Z, books):- reads(Z), is_inquisitive(Z).

Аргумент Z суть переменная, поэтому она может соответствовать Х.

Вторые аргументы находятся в согласии, так что обращение соответствует

заголовку правила. Когда Х согласуется с Z, аргументы унифицируются. В

результате унификации аргументов Турбо Пролог приравняет значение, кото-

рое имеет Х (то есть john), и переменную Z. В результате переменная Z те-

перь также имеет значение john.

Теперь подцель соответствует левой части (заголовку) правила. Про-

должение поиска определяется третьим фундаментальным правилом поиска с

возвратом:

--------------------------------------------------------------

Когда подцель соответствует заголовку правила, тело этого

правила должно быть согласовано следующим. Тело правила

затем образует новое множество подцелей для согласования.

--------------------------------------------------------------

Это дает следующее целевое дерево:

/\

/ \

/ \

/ \

likes(X,wine) likes(X,books)

------------- --------------

likes(john,wine) likes(Z,books)

/\

/ \

/ \

/ \

reads(Z) is_inquisitive(Z)

Теперь целевое дерево включает в себя подцели

reads(Z) и is_inquisitive(Z)

где Z связана со значением john. Теперь Турбо Пролог будет искать факты,

соответствующие обеим подцелям. Вот последнее результирующее целевое де-

рево:

/\

/ \

/ \

likes(X,wine) likes(X,books)

------------- --------------

likes(john,wine) likes(Z,books)

/\

/ \

/ \

reads(Z) is_inquisitive(Z)

-------- -----------------

reads(john) is_inquisitive(john)

Как гласит четвертое основное правило поиска с возвратом:

-------------------------------------------------------

Целевое утверждение считается согласованным, когда

соответствующий факт найден для каждой оконечности

(листа) целевого дерева.

-------------------------------------------------------

Таким образом, теперь начальное целевое утверждение согласовано.

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

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

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

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

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

непосредственно отвечает:

X=john

1 Solution

Goal :_

Как вы видели в программе CH05EX04.PRO, однажды согласовав внешнее

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

тернативных решений. Он также возвращается назад, если подцель не выпол-

няется, надеясь пересогласовать предыдущую подцель таким образом, чтобы

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

Выполняя подцель, Турбо Пролог начинает поиск с первого предложения,

определяющего предикат. Затем может произойти одно из двух:

1. Он находит соответствующее предложение, тогда происходит следую-

щее:

а. Если имеется другое предложение, которое, возможно, может

вновь согласовать подцель, Турбо Пролог выставляет указатель (с

тем, чтобы отметить точку возврата) возле этого соответствующего

предложения.

b. Все свободные переменные в подцели, которые соответствуют зна-

чениям в предложении, связываются с соответствующими значениями.

c. Если данное соответствующее предложение является заголовком

правила, то затем оценивается тело этого правила; подцели в теле

правила должны быть выполнены для успешного завершения обращения.

2. Он не может найти соответствующее предложение, таким образом це-

левое утверждение не согласуется. Турбо Пролог выполняет поиск с

возвратом в попытке вновь согласовать предыдущую подцель. Когда про-

цесс достигает последней точки возврата, Турбо Пролог освобождает

все переменные, которым были присвоены новые значения после того,

как была проставлена точка возврата; затем пытается вновь согласо-

вать исходное обращение.

Турбо Пролог начинает поиск с вершины программы. Когда он выполняет

возврат к обращению, новый процесс поиска начинается с точки поиска с

возвратом, выставленной последней. Если поиск безуспешен, то вновь выпол-

няется поиск с возвратом. Если процесс поиска с возвратом исчерпал все

предложения для всех подцелей, то значит целевое утверждение не согласу-

ется.