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

Поиск с возвратом — это механизм, который указывает Visual Prolog, как искать решения для программы. Этот процесс дает Прологу возможность перебрать все известные факты и правила для решения. Рассмотрены четыре основных принципа поиска с возвратом:

1. подцели должны проверяться по порядку, сверху вниз;

2. предикатные предложения проверяются в том порядке, в котором они появляются в программе, сверху вниз;

3. когда подцель сопоставляется с заголовком правила, тело правила должно после этого быть доказано (тело правила состоит из новых подцелей, которые должны быть доказаны);

4. цель доказана, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.

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

1. Согласование целевого утверждение всегда начинается с вершины программы.

2. При выполнении нового обращения поиск начинается с вершины программы.

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

4. При неуспешном соответствии обращения, переменная освобождается и может быть испытана новая подцель.

Детальный поиск с возвратом

Пример.

domains % раздел доменов

title, autor = symbol % домены название и автор – символьные

pages = unsigned % домен страницы – беззнаковое, количественное 0-4294967259

рredicates % раздел предикатов

book (title, pages) % задание предиката книги с указанием названия и количества страниц

written_by (autor, title) % задание писатели с указанием имени автора и названия написанной книги

Long_novel (title)

clauses % раздел предложений для задания пользовательских предикатов, правил, фактов

written_by (pushkin, pugahtev). % писатель Пушкин написал книгу Пугачев

written_by (lermontov, mziri). % писатель Лермонтов написал книгу Мцири

book (pugahtev, 100). % книга Пугачев содержит 320 страниц

book (mziri, 370). % книга Мцири содержит 370 страниц

Long_novel (Title):-

Written_by (_, Title),

Book (Title, Pages),

Pages>350. % внутреннее целевое утверждение

goal % раздел целей (запросов)

Рассмотрим следующий запрос с унификацией: показать все названия книг long_novel.

Long_novel (T).

Получим ответ

T=mziri