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.
Результат выполнения программы:
Юра - Ира
Юра - Коля
Юра - Леша
Юра – Оля