Использование предиката 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.

 

1. ОТМЕНА БЭКТРЕКИНГА. ПРЕДИКАТ 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.