Вопрос 8) Управление поиском решений(Prolog)

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

1)    предикат fail, который используется для инициализации поиска с возвратом;

Если в теле правила отсутствует предикат fail, то тестирование программы выдаст только первое подходящее решение.

Поставим в конце правила предикат fail. В результате тестирования будут выданы все возможные решения.

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

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

 

2)    отсечение cut (обозначается !) – для запрета возможности возврата.

Через отсечение невозможно совершить откат (поиск с возвратом).

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

Отсечение применяется в одном из двух основных случаев:

а) если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям – это зеленое отсечение;

б) если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей – это красное отсечение.

predicates

  friend(symbol,symbol)

  girl(symbol)

  likes(symbol,symbol)

 

clauses

  friend(bill,jane):-

     girl(jane),

     likes(bill,jane),!.

  friend(bill,jim):-

     likes(jim,baseball),!.

  friend(bill,sue):-

     girl(sue).

 

  girl(mary).

  girl(jane).

  girl(sue).

 

  likes(jim,baseball).

  likes(bill,sue).

goal

  friend(bill,Who).

 

Программа выдает одно решение: “jane”. Если убрать отсечение в первом предложении, то программа выдаст 2 решения. Если убрать отсечение во втором предложении, то программа выдаст 3 решения.

Вопрос 9) Простые и составные объекты данных

Составные объекты данных позволяют интерпретировать некоторые части информации как единое целое таким образом, чтобы затем можно было легко разделить их вновь. Возьмем, например, дату "октябрь 15, 1991". Она состоит из трех частей информации - месяц, день и год. Представим ее на рис. 1, как древовидную структypy.

Рис.1. Древовидная структура даты

    Вы можете сделать это, объявив домен, содержащий составной объект date:

domains

date_cmp = date(string,integer,integer)

а затем просто записать:

D=date("October",15,1991).

    Такая запись выглядит как факт Пролога, но это не так - это объект данных, который вы можете обрабатывать наряду с символами и числами. Он начинается с имени, называемого функтором (в данном случае date), за которым следуют три аргумента.

    Обратите внимание, что функтор в Прологе - не то же самое, что функция и других языках программирования; это просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы.

    Замечание. Функтор не обозначает, что будут выполнены какие-либо вычисления.

    Аргументы составного объекта данных могут сами быть составными объектами. Например, вы можете рассматривать чей-нибудь день рождения (рис. 2), как информацию со следующей структурой:

Рис.2. Древовидная структура даты рождения

    На языке Пролог это выглядит следующим образом:

birthday(person("Leo", "Jensen"),date("Apr ", 14 , 1991))

    У составного объекта birthday в этом примере есть две части: объект person ("Leo","Jensen") и объект date("Apr",14,1900). Функторами для этих объектов будут person и date.