Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
лекция1.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
135 Кб
Скачать
☆

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

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

Попытка согласования целевого утверждения начинается с вершины программы. Если соответствие обнаружено, то инициируется процесс конкретизации переменных.

В том случае, когда в программе существует более чем один возможный ответ на некоторое обращение, ставится точка возврата после соответствующего факта. Эта точка указывает на то место, откуда начнется поиск следующего возможного согласования для некоторого предложения. Механизм возврата запускается тогда, когда в программе не обнаруживается соответствующих предложений. Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и ищет другое решение для исходного обращения.

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

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

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

        3. Когда подцель соответствует заголовку правила, далее должно быть согласовано тело этого правила: тело правила теперь образует новое множество подцелей для согласования.

        4. Целевое утверждение является согласованным, когда соответствующий факт найден для каждой оконечности (листа) целевого дерева.

При помощи поиска с возвратом в режиме тестирования программы будут найдены все возможные решения задачи.

Пример 7. (слайд 12)

Для задачи, условие которой сформулировано в примере1 (без учета высказывания B), организовать поиск решений для ответа на вопросы: «Кто из работников может быть поваром (администратором, кондитером)?»

DOMAINS

name, prof = symbol

PREDICATES

профессия(prof)

сотрудник(name)

должность(name,prof)

CLAUSES

профессия(администратор).

профессия(повар). (**)

профессия(кондитер).

профессия(кассир).

профессия(дворник).

сотрудник(голубева, жен). (***)

сотрудник(иванова, жен).

сотрудник(васин, муж).

сотрудник(смирнов, муж).

сотрудник(азаров, муж).

должность(X,Y):- (*)

сотрудник(X), X=голубева, профессия(Y) ), not(Y=повар).

должность(X,Y):-

сотрудник(X), X = иванова, профессия(Y), not(Y=кондитер),

not(Y=кассир), not(Y=повар).

должность(X,Y):-

сотрудник(X), X=васин, профессия(Y), not(Y=администратор),

not(Y=повар), not(Y=кассир),

not(Y=кондитер).

должность(X,Y):-

сотрудник(X), X=смирнов, профессия(Y), not(Y=кондитер),

not(Y=кассир).

должность(X,Y):-

сотрудник(X), X=азаров, профессия(Y), not(Y=кассир).

GOAL

должность(Кто, повар).

% должность(Кто, администратор).

% должность(Кто, кондитер).

На этом примере полезно рассмотреть процесс поиска с возвратом. Пролог будет искать решение, производя с вершины программы поиск соответствия с целью должность(Кто, повар). В разделе предложений терм (*) содержит правило, заголовок которого может быть успешно согласован с целевым утверждением. Переменная Кто будет согласована с переменной X, а переменная Y конкретизирована значением повар. Далее Пролог продвигается по процедуре описания предиката сотрудник. И сразу же переменная X будет конкретизирована значением голубева, после чего успешным будет предикат равенства X=голубева, а Пролог, действуя от вершины программы, приступит к согласованию подцели профессия(повар), поскольку переменная Y конкретизирована. Терм (**) обеспечивает ее успех. Основная цель согласована, получено решение. Не следует забывать, что терм (***) помечен точкой отката при согласовании подцели сотрудник(X). Пролог совершит откат в эту точку, затем будет проводить сопоставление предиката сотрудник, но необходимость согласования последующего предиката равенства X = голубева к успеху не приведет. Полог совершит откат к предыдущей точке отката, которая находится в терме (*). После чего Пролог приступит к согласованию основной цели с правилом, сформулированным для того же предиката должность(X,Y) в терме, следующем за (*). Дальнейшие действия будут аналогичны вышеописанным. Заметим, что первая и вторая цели будут иметь по 4 решения, а третья – два.