Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Цель работы: формирование навыков осуществления поиска решений при помощи отката.

Используемое программное обеспечение: Visual Prolog 5.2.

 

Теоретические сведения

Часто, при решении реальных проблем, Вы должны довести задачу до ее логического заключения. Если это заключение не дает Вам ответ, который Вы искали, Вам следует использовать альтернативное решение. Наверняка, когда Вы были ребенком, играли в лабиринт. Точный способ нахождения выхода из лабиринта состоит в том, чтобы поворачивать налево на каждой развилке в лабиринте, пока не попадете в тупик. Как только попали в тупик, нужно вернуться к последней развилке и повернуть на право, а потом опять поворачивать налево на каждой развилке. Систематически перебирая все пути, Вы, в конечном счете, найдете правильный маршрут и выйдите из лабиринта.

Visual Prolog использует этот же метод «восстановления и повторной попытки», называемый откатом, для решения задачи. Как только Visual Prolog начнет искать решение задачи (или цель), ему, возможно, придется выбирать между двумя возможными случаями. Он устанавливает маркер в месте разветвления (точка отката) и выбирает первую подцель. Если эта подцель терпит неудачу (эквивалент достижению тупика), Visual Prolog возвращается в точку отката и пробует альтернативную подцель.

Правила отката:

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

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

Стараясь удовлетворить первую подцель, Visual Prolog, начиная с верха, пытается сопоставлять ее с каждым фактом или головой правила, с которым сталкивается.

3. Когда запросу найдено подходящее соответствие, говорят, что запрос выполнен, и можно переходить к следующей подцели.

4. Если переменная была связана в предложении, единственный способ освободить ее заключается в откате.

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

При помощи отката Visual Prolog может находить не только первое решение задачи, но и все возможные решения.

Принципы отката:

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

Visual Prolog определяет, каким предложением можно удовлетворить подцель согласно второму основному принципу отката:

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

Продолжение поиска происходит согласно третьему основному принципу отката:

3. Если подцель соответствует голове правила, тело этого правила должно быть так же выполнено. Тело правила предоставляет новый набор подцелей, которые необходимо решить.

Согласно четвертому основному принципу отката:

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

Рассмотрим программу, которая содержит информацию (факты) об именах и возрасте некоторых игроков в теннисном клубе.

1. Опишите раздел доменов. Задайте типы аргументов предиката.

child = symbol

age = integer

2. Опишите раздел предикатов.

nondeterm player(child, age)

3. Опишите раздел предложений.

player(peter, 9).

player(paul, 10).

player(chris, 9).

player(susan, 9).

Ваша программа должна выглядеть следующим образом:






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.