Поиск с возвратом
Основные разделы ПРОЛОГ-программы
Как правило, программа на ПРОЛОГе состоит из четырех разделов.
DOMAINS – секция описания доменов (типов). Секция применяется, если в программе используются нестандартные домены.
Например:
name = string
data = integer
PREDICATES –секция описания предикатов. Секция применяется, если в программе используются нестандартные предикаты.
Например:
знает (name, name)
студент (name)
CLAUSES –секция предложений. Именно в этой секции записываются предложения: факты и правила вывода.
Например:
знает (лена, иван).
студент (иван).
знаком_студент(X,Y):- знает (X,Y ), студент (Y).
GOAL –секция цели. В этой секции записывается запрос.
Например:
знаком_студент(лена,X).
Простейшая программа может содержать только раздел GOAL, например:
GOAL
write (“Введите Ваше имя: ”), readln (Name),
write (“Здравствуйте, ”, Name, “!”).
Комментарий: write – стандартный предикат вывода, readln – стандартный предикат ввода строкового значения
Поиск с возвратом (backtracking) – это один из основных приемов поиска решений поставленной задачи в ПРОЛОГ’е. Выполняя поиск, ПРОЛОГ может столкнуться с необходимостью выбора между альтернативными путями. Тогда он ставит маркер у места развилки (точка отката) и выбирает первую подцель. Если она не выполняется, то ПРОЛОГ возвращается в точку отката и переходит к следующей подцели.
Рассмотрим механизм поиска на примере. Пусть имеются факты:
знает (лена, таня).
знает (лена, иван).
студент (иван).
Требуется определить, есть ли у Лены знакомые студенты.
Программа:
PREDICATES
знает (symbol, symbol)
студент (symbol)
знаком_студент(symbol, symbol)
CLAUSES
знает (лена, таня). % (1)
знает (лена, иван). % (2)
студент (иван). % (3)
знаком_студент(X,Y):- знает (X,Y), студент (Y). % (4)
GOAL
знаком_студент(лена, Name).
Поиск решения:
1. Пытаясь выполнить целевое утверждение знаком_студент(лена, Name), ПРОЛОГ проверяет каждое предложение из раздела CLAUSES. В результате сопоставления с предложением (4) - X=лена.Переменная Y унифицируется с переменной Name.
2. Переход к первой подцели знает (лена,Y) и поиск соответствующего предложения. В результате сопоставления с предложением (1) – Y=таня. Возле факта знает (лена, таня) устанавливается маркер.
3. Переход ко второй подцели студент (таня) и поиск соответствующего предложения. Факт не найден – возврат в точку отката.
4. Дальнейший поиск фактов, соответствующих первой подцели знает(лена,Y). В результате сопоставления с предложением (2) – Y=иван.
5. Переход ко второй подцели студент (иван) и поиск соответствующего предложения приводит к успешному завершению поиска.
Результат:
Name=иван