В Прологе существуют два специальных предиката, которые позволяют контролировать механизм бэктрекинга: предикат 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), где /\ обозначает «ИЛИ», а A означает узел типа «И»:

    Рис.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 делает программу эффективнее, но она теряет прозрачность логической семантики, остаётся только процедурной, что отвечает выбранной стратегии просмотра дерева.

3.      ОТРИЦАНИЕ КАК НЕУДАЧА. ПРЕДИКАТ not

Рассмотрим фразу: «Ваня любит все игры кроме баскетбола.». Попробуем записать её на Прологе. Первая часть этого утверждения выражается легко: «Ваня любит Х, если Х – игра», или же:

                          like(wanja,X):-game(X).

Однако необходимо исключить баскетбол. Это можно сделать, воспользовавшись иной формулировкой:

Если Х – баскетбол, тогда „Ваня любит Х” не будет истиной, иначе, если Х – игра, то „Ваня любит Х”.

Для реализации этого на Прологе воспользуемся предикатом fail, который всегда завершается неуспешно и при этом влечёт неуспешное завершение и той фразы, являющейся для него родительской.           

            like(wanja, X):- basketball(X),!,fail.

            like(wanja, X):- game(X).

Тут отсечение отбросит рассмотрение другого правила, если игра – баскетбол, а fail вызовет неуспех.

Этот пример показывает, что желательно иметь унарный предикат not, такой, что not(Цель) будет истиной в случае, когда Цель является ложью. На Прологе его можно описать так:

            not(P):- P,!, fail;

            true.

Пролог-система имеет встроенный предикат not, реализованный подобным образом.

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

            like(wahja,X):- game(X),

                                    not(basketball(X))

Важно отметить: предикат not выполняется успешно, когда подцель не является истиной, т.е. тогда, когда ассоциированная с ним подцель не может дать истину.

Следующая программа показывает использование предиката not.

            domains

                        name = symbol

                        gpa = real

 

            predicates

                        honor_student(name)

                        student(name, gpa)

                        probation(name)

 

            clauses

            honor_student(Name):-

                        student(Name, GPA),

                        GPA>=3.5,

                        not(probation(Name)).

            student("Betty Blue", 3.5).

            student("David Smith", 2.0).

            student("John Johnson", 3.7).

            probation("Betty Blue").

            probation("David Smith").

 

На запрос honor_student(Name) она выдаст список студентов, средний балл которых больше или равен 3,5 за исключением студентов Betty Blue и David Smith, которые проходят практику.

4.ТРУДНОСТИ В ИСПОЛЬЗОВАНИИ ОТСЕЧЕНИЯ И ОТРИЦАНИЯ

Отметим сначала достоинства использования отсечения:

1. С помощью предиката cut можно повысить эффективность программы.

2. Используя cut, можно описать взаимоисключающие правила, поэтому существует возможность запрограммировать утверждения типа: если P, то Q, иначе R.

Ограничения на использование отсечения выходят за пределы декларативной стороны Пролог-программы. Если в программе нет отсечения, то можно менять порядок фактов и целей. Когда же предикат cut присутствует в программе, то изменение порядка фактов может выйти на её декларативное изменение (дать другое решение).

Если исключение отсечения из программы не меняет её декларативный смысл, то такое отсечение называют «зелёным». В другом случае отсечение называют «красным».

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

Если задать системе следующий запрос:

цель: not(dog(baks)),

она возможно ответит „да”. Однако этот ответ нельзя рассматривать как утверждение о том, что „Бакс не собака”. Просто системе не достаточно информации для подтверждения высказывания „Бакс - собака”. Такой подход берёт своё начало от предположения о замкнутости мира. Согласно данному предположению мир замкнут в том смысле, что всё существующее в нем либо указано в программе, либо может быть выведено из неё. И в другом случае, когда чего-то нет в программе (или не может быть выведено), то оно является ложным, и следовательно будет истинным его отрицание.

Мы же традиционно не считаем мир замкнутым: если в программе явно не указано, что dog(baks), то это не означает, что мы хотим сказать: Бакс не собака.

Приведём ещё один пример осторожного применения not:

            predicates

                        r(symbol)

                        g(symbol)

                        p(symbol)

            clauses

                        r(a).

                        g(b).

                        p(X):-not(r(X)).

На запрос цель: g(X), p(X) система ответит X=b, а на цель: p(X),g(X) – no (нет). Вся разница в том, что в первом случае переменная Х в момент обработки p(X) была уже связанной, а в другом – этого ещё не произошло.