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

Текст из файла (страница 4)

Visual Prolog при поиске решения задачи использует именно такой метод проб и возвращений назад; этот метод называется поиск с возвратом. Если, начиная поиск решения задачи (или целевого утверждения), Visual Prolog должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится, Visual Prolog вернется к точке отката и попробует проверить другую подцель.

predicates

likes(symbol,symbol)

tastes(symbol, symbol)

food(symbol)

clauses

likes(bill,X):-

food(X), tastes(X,good) .

tastes(pizza,good).

tastes(brussels_sprouts,bad).

food(brussels_sprouts).

food(pizza).

1. Программа ch04e02.pro

Эта маленькая программа составлена из двух множеств фактов и одного правила. Правило, представленное отношением likes, утверждает, что Билл любит вкусную пищу.

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

likes(bill, What).

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

В данном случае Пролог будет искать решение, производя с вершины программы поиск соответствия с подцелью likes (bill, what).

Он обнаруживает соответствие с первым предложением в программе и переменная What унифицируется с переменной X. Сопоставление с заголовком правила заставляет Visual Prolog попытаться удовлетворить это правило. Производя это, он двигается по телу правила и обращается к первой находящейся здесь подцели: food(X).

Если выполняется новое обращение, поиск соответствия для этого обращения вновь начинается с вершины программы.

Пытаясь согласовать первую подцель, Visual Prolog (начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.

Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная X связывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), Visual Prolog ставит точку возврата (маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на то место, откуда Пролог начнет поиск следующего возможного соответствия для food(X).

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

Поскольку переменная X связана с brussels_sprouts, следующее обращение будет выполняться так:

tastes(brussels_sprouts, good)

и Visual Prolog вновь начнет поиск с вершины программы, пытаясь согласовать это вращение. Поскольку соответствующих предложений не обнаруживается, обращение завершается неудачно, и теперь Visual Prolog запускает механизм возврата. Начиная поиск с возвратом, Пролог отступает к последней позиции, где была уставлена точка отката. В данном случае Пролог возвращается к факту

food(brussels_sprouts).

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

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

Обращение было food(X), так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение для этого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменная X связывается со значением pizza.

Пролог переходит к следующей подцели в правиле, имея при этом новую связанную переменную. Производится новое обращение, tastes (pizza, good), и начинается поиск (опять от вершины программы). На этот раз соответствие найдено, и целевое утверждение успешно выполняется.

Поскольку переменная what в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана со значением pizza и Visual Prolog сообщает решение:

What=pizza

1 Solution

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

Встроенный механизм поиска с возвратом в Прологе может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только одно решение. В других случаях может оказаться необходимым продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано.

Visual Prolog обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cut или отсечение (обозначается !) — для запрета возможности возврата.

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

Visual Prolog начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Visual Prolog поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2=3 или другой невозможной подцели. Программа ch04e06.pro (рис. 3) иллюстрирует использование этого специального предиката.

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.

1. Программа ch04e06.pro

Пусть необходимо найти все решения цели father (X,Y). Используя утилиту Test Goal, можно записать цель как

goal

father(X,Y).

Test Goal найдет все решения цели father (X,Y) и отобразит значения всех переменных следующим образом:

X=leonard, Y=katherine

X=carl, Y=jason

X=carl, Y=marilyn

3 Solutions

Но если вы скомпилируете эту программу и запустите ее, то Visual Prolog найдет только первое подходящее решение для father (X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к father приведет только к одному решению. Как же найти все возможные решения? Предикат everybody в программе ch04e06.pro использует fail для поддержки поиска с возвратом.

Задача предиката everybody — найти все решения для father и выдать полный ответ. Сравните предыдущие ответы утилиты Test Goal с целью father(X,Y) и ответы на выполнение следующей цели:

goal

everybody.

отображенные сгенерированной программой:

leonard is katherine' s father

carl is Jason's father

carl is marilyn's father

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

father (X, Y),

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

fail.

fail не может быть согласован (он всегда неуспешен), поэтому Visual Prolog вынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может произвести только одно решение.

Предикат write не может быть вновь согласован (он не может предложить новых решений), поэтому Visual Prolog должен выполнить откат дальше, на этот раз к первой подцели в правиле.

Обратите внимание, что помещать подцель после fail в теле правила бесполезно. Предикат fail все время завершается неудачно, нет возможности для достижения подцели, расположенной после fail.

1. Прерывание поиска с возвратом: отсечение

Visual Prolog предусматривает возможность отсечения, которая используется для прерывания поиска с возвратом; отсечение обозначается восклицательным знаком (!). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).

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

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

• Если вы заранее знаете, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), — примените отсечение, — программа станет быстрее и экономичнее. Такой прием называют зеленым отсечением.

• Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это — красное отсечение.

В этом вопросе даются примеры, показывающие, как следует использовать отсечение, рассматриваются несколько условных правил (rl, r2 и rЗ), которые определяют условный предикат г, а также несколько подцелей — а, b, с и т. д.

1. Предотвращение поиска с возвратом к предыдущей подцели в правиле

r1 :- а,b,

!,

c.

Такая запись является способом сообщить Visual Prolog о том, что вас удовлетворит первое решение, найденное им для подцелей а и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произвести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат rl.

В качестве конкретного примера рассмотрим программу ch04e07.pro (рис. 4).

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).

goal

buy_car(corvette,Y).

1. Рис. 4. Программа ch04e07.pro

В данном примере поставлена цель: найти corvette (Корвет) приятного цвета, подходящий по стоимости. Отсечение в правиле buy_car означает, что поскольку в базе данных содержится только один "Корвет" приятного цвета, хоть и со слишком высокой ценой, то нет нужды искать другую машину. Получив целевое утверждение

buy_car(corvette, Y)

программа отработает следующие шаги:

1. Visual Prolog обращается к саг, первой подцели для предиката buy_car.

2. Выполняет проверку для первой машины, maserati, которая завершается неудачно.

3. Затем проверяет следующее предложение саг и находит соответствие, связывая переменную Color со значением black.

4. Переходит к следующему обращению и проверяет, имеет ли выбранная машина приятный цвет. Черный цвет не является приятным в данной программе, таким образом, проверка завершается неудачно.

5. Выполняет поиск с возвратом к обращению саг и снова ищет corvette, удовлетворяющий этому критерию.

6. Находит соответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и Visual Prolog переходит к следующей подцели в правиле: к отсечению. Отсечение немедленно выполняется, "замораживая" все переменные, ранее связанные в этом предложении.

7. Переходит к следующей (и последней) подцели в правиле, к сравнению

Price < 25000.

8. Проверка завершается неудачно, и Visual Prolog пытается совершить поиск с возвратом с целью найти другую машину для проверки. Отсечение предотвращает попытку решить последнюю подцель, и наше целевое утверждение завершается неудачно.

1. Предотвращение поиска с возвратом к следующему предложению

Отсечение может быть использовано, как способ сообщить Visual Prolog, что он выбрал верное предложение для определенного предиката. Например, рассмотрим следующий фрагмент:

r(1) :-

!,

а, b, с.

r(2):-

!,

d.

r(3):-

!,

с.

r(_) :-

write("This is a catchall clause.").

Использование отсечения делает предикат r детерминированным. В данном случае Visual Prolog выполняет обращение к r с единственным целым аргументом. Предположим, что произведено обращение r(l). Visual Prolog просматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, Visual Prolog проставляет точку возврата около этого предложения.

Теперь Visual Prolog начинает обработку тела правила, проходит через отсечение и исключает возможность возвращения к другому предложению r. Это отменяет точки поиска с возвратом, повышая эффективность выполнения программы, а также гарантирует, что отлавливающее ошибки предложение будет выполнено лишь в том случае, если ни одно из условий не будет соответствовать обращению к r.

Обратите внимание, что конструкция такого типа весьма похожа на конструкцию case в других языках программирования; условие проверки записывается в заголовке правил. По возможности, всегда следует помещать проверочное условие именно в заголовок правила, — это повышает эффективность программы и упрощает ее чтение.

1. Детерминизм и отсечение

Если бы предикат r, определенный в предыдущей программе, не содержал отсечений, то это был бы недетерминированный предикат (способный производить множественные решения при помощи поиска с возвратом). В предыдущих реализациях Пролога программисты должны были обращать особое внимание на недетерминированные предложения из-за сопутствующих им дополнительных требований к ресурсам памяти. Теперь Visual Prolog сам выполняет проверку на недетерминированные предложения, облегчая вашу работу.

В Прологе существует директива компилятора check_determ. Если вставить эту директиву в самое начало программы, то Visual Prolog будет выдавать предупреждение в случае обнаружения недетерминированных предложений в процессе компиляции.

Характеристики

Список файлов книги