Поиск с возвратом

Основные разделы ПРОЛОГ-программы

Как правило, программа на ПРОЛОГе состоит из четырех разделов.

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=иван

Дата добавления: 2014-01-05