Solition

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

 

 

рис.2. Целевое дерево поиска с возвратом

Благодаря механизму поиска с возвратом ПРОЛОГ в состоянии находить все возможные решения, имеющиеся для данной задачи.

Основные правила поиска с возвратом:

1) Цели должны быть доказаны по порядку, слева направо.

2) Для доказательства некоторой цели предложения просматриваются в том порядке, в каком они появляются в тексте программы.

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

4) Цель считается доказанной, если с помощью соответствующих фактов доказаны все цели, находящиеся в листьевых вершинах дерева целей.

4.8. Управление поиском с возвратом: предикаты fail и отсечения

Для управление поиском с возвратом используются два стандартных предиката: fail и отсечения.

1. fail – это тождественно-ложный предикат, искусственно создающий ситуацию неуспеха и заставляющий продолжить поиск. Использование предиката fail позволяет найти все решения задачи.

Пример 1. Вывести список студентов 4-го курса.

DOMAINS

name=string

kurs=integer

PREDICATES

Student(name, kurs)

spisok

CLAUSES

Student("Ира",2).

Student("Юра",4).

Student("Коля",1).

Student("Леша",4).

Student("Оля",4).

spisok:-Write("Список студентов 4 курса"), nl, Student(X,4),

Write(X), nl, fail.

GOAL

spisok.

Комментарий: nl (new line) – предикат перевода курсора на новую строку

В данном примере после первого найденного решения (Х= «Юра») и его вывода предикат fail заставляет вернуться в точку отката и продолжить поиск, просматривая другие факты. В результате будут найдены все решения, удовлетворяющие запросу.

Результат выполнения программы:

Список студентов 4 курса

Юра

Леша

Оля

2. Чтобы ограничить пространство поиска и прервать поиск решений при выполнении какого-либо условия, используется предикат отсечения (обозначается!), Однажды пройдя через отсечение, невозможно вернуться назад, т.к. этот предикат является тождественно-истинным. Процесс может только перейти к следующей подцели, если такая имеется.

Если задано предложение вида:

R:-A, B,!, C.

то после достижения подцелей А и В процесс поиска других решений этих подцелей прекращается и вычислительный процесс перейдет к следующей подцели С.

Например, чтобы в примере 1 вывести все возможные пары одного из студентов 4-го курса со всеми остальными студентами, следует изменить правило spisok

spisok:- Student(X,4),!, Student(Y,_), X<>Y,
Write(X," - ",Y), nl, fail.

Результат выполнения программы:

Юра - Ира

Юра - Коля

Юра - Леша

Юра – Оля