Лабораторная работа №3

Тема: Контроль механизма бэктрекинга при поиске решений.

Цель: Научиться использовать встроенные предикаты fail,cut и not.

Теоретическая часть

В Прологе существуют два специальных предиката, которые позволяют контролировать механизм бэктрекинга: предикат fail, заставляющий запускать механизм бэктрекинга, и cut (обозначается с помощью символа “!”), предназначенный для отмены бэктрекинга.

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

Пролог запускает бэктрекинг, когда очередное сопоставление завершается неудачей. Предикат 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.

goal

everybody.

После запуска программы, система попытается удовлетворить все цели, находящиеся в разделе goal. Таким образом, в нашей базе знаний будет организован поиск фактов, соответствующих предикату everybody, либо правил, голова которых сопоставима с данным предикатом.

Заметим, что не имеет смысла использовать в теле правила подцель после fail. Учитывая тот факт, что значением предиката fail выступает «ложь», то нет путей, которые смогли бы удовлетворить подцель, находящуюся после fail.

2. Отмена бэктрекинга. Предикат cut

Предикат cut генерирует значение «истина», что означает успех, и обозначается «!». Он размещается в теле правила как подцель. Когда обработка подцелей достигает cut, он всегда является успешным, а поэтому вызывается следующая за ним подцель. Из-за того, что cut был пройден, невозможно провести бэктрекинг подцелей, которые были расположены перед cut в обрабатываемом предложении, и поэтому невозможно перейти к другим вариантам, соответствующим текущему предикату.

Существует два основных правила использования предиката cut:

1. Если известно заранее, что полный перебор вариантов никогда не будет способствовать рациональному поиску решения, то использование cut («зелёное» отсечение) останавливает просмотр альтернативных значений.

2. Когда логика программы потребует использования cut для остановки просмотра альтернативных подцелей, тогда его называют «красным» отсечением.

Другими словами, предикат cut ограничивает автоматичный перебор. Во многих задачах возникает проблема либо ограничения бэктрекинга, либо его полной остановки.

Рассмотрим для начала программу, процесс выполнения которой содержит ненужный перебор. Пусть необходимо реализовать функцию y=f(x), которая задана в следующем виде:

• если х<10, то у=10;

• если 10<=х и х<20, то у=20;

• если 20<=х, то у=30.

На Прологе её можно выразить программой:

predicates

f(integer,integer).

clauses

f(X,10):- X < 10.

f(X,20):- X >= 10, X < 20.

f(X,30):- X >= 20.

Проанализируем, что будет делать программа, если задать вопрос:

Цель: f(5,Y), Y > 20.

При обработке первой цели f(5,Y), Y примет значение 10, поэтому другая подцель станет 10>20. она завершается неудачей. Однако очевидно, что и весь список подцелей, который будет проверяться благодаря бэктрекингу, тоже будет завершаться неудачей.

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

predicates

f(integer,integer).

clauses

f(X,10):- X < 10,!.

f(X,20):- X >= 10, X < 20,!.

f(X,30):- X >= 20.

Предикат cut не позволяет делать откат из тех точек программы, в которых он находится, - программа стала более эффективной. Но если сформировать запрос типа:

Цель: f(22,Y),

то Пролог-система сделает три проверки и только после этого свяжет с У значение 30. Однако наши проверки являются взаимоисключающими. Поэтому для повышения эффективности, можно предложить следующий вариант программы:

predicates

f(integer,integer).

clauses

f(X,10):- X < 10,!.

f(X,20):- X < 20,!.

f(X,30).

Предикат cut по-разному воздействует на сложный вопрос и на множество фраз. Рассмотрим случай, когда предикат отсечения является одной из подцелей составного вопроса:

цель: a(X),b(Y),!,c(X,Y,Z).

При исполнении этого типа запроса Пролог-система пройдет через предикат cut только в том случае, когда подцели a(X) и b(Y) будут удовлетворены. После того, как подцель cut будет выполнена, система не сможет вернуться назад для повторного просмотра подцелей «а» и «b», если подцель «с» не удовлетвориться при текущих значениях X и Y.

Приведём ещё один пример использования cut:

predicates

buy_car(symbol, symbol)

car(symbol, symbol,integer)

colors(symbol, symbol)

clauses

buy_car(Model, Color) :- car(Model, Color, Price),

colors(Color, sexy),!,

Price < 25000.

car(maserati, green, 25000).

car(corvette, black, 24000).

car(corvette, red, 26000).

car(porsche, red, 24000).

colors(red, sexy).

colors(black, mean).

colors(green,preppy).

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

Для пояснения работы предиката cut вернёмся к процессу управления выводом в Прологе. Пусть Пролог-программа выглядит следующим образом:

р: - a,b.

p: - c,d.

Эту программу, используя понятие процедуры, можно прочитать так. При выполнении процедуры р выполняются процедуры a и b. Если они завершаются успешно, тогда и процедура р считается успешно завершённой. В случае, если это не так, выполняются процедуры c и d. Иначе процедура р завершается неуспехом.

Такой алгоритм обработки можно реализовать на дереве типа И/ИЛИ (рис.1), где /\ обозначает «ИЛИ», а означает узел типа «И»:

Р

а b c d

Рис.1

Вершина типа «И» будет успешной только в том случае, когда её вершины-потомки успешны. Вершина типа «ИЛИ» будет успешной тогда, когда хотя бы одна из её вершин- потомков успешна.

Согласно со стратегией поиска в глубину, которая используется в Прологе, проводиться последовательный перебор дерева «И/ИЛИ» сверху-вниз, слева-направо. Это соответствует отделению самой левой подцели запроса и выполнению правил программы сверху-вниз.

Если при просмотре дерева какой-то из потомков вершины «ИЛИ» является успешным, то обработка других вершин-потомков (поддерева, которое находится правее) приостанавливается и считается, что эта вершина типа «ИЛИ» стала успешной.

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

Следует отметить, что обработка вершины «ИЛИ» не завершается, а только приостанавливается. Это связано с тем, что со временем возможно повторное обращение к этой вершине, и тогда ветви, которые не анализировались, могут снова привести к успеху в этой вершине (бэктрекинг).

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

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

Рассмотрим программу:

а(x): - b(x), ! , c(x).

a(x): - d(x).

b(c).

b(f).

c(e).

c(f).

d(g).

Это типичное «красное» отсечение.

На запрос а(Z) программа даст только один ответ – Z=e, так как она не будет возвращаться к вариантам, возникшим до обращения к cut (при обработке подцелей a(Z) и b(Z)).

Если же извлечь предикат cut из первого правила и создать запрос a(Z), то получим три ответа Z=e, Z=f, Z=g.

Отметим, что использование предиката cut делает программу эффективнее, но она теряет прозрачность логической семантики, остаётся только процедурной, что отвечает выбранной стратегии просмотра дерева.