Поиск с возвратом
Поиск с возвратом (backtracking) – это один из основных приемов поиска решений поставленной задачи в ПРОЛОГ’е. Выполняя поиск, ПРОЛОГ может столкнуться с необходимостью выбора между альтернативными путями. Тогда он ставит маркер у места развилки (точка отката) и выбирает первую подцель. Если она не выполняется, то ПРОЛОГ возвращается в точку отката и переходит к следующей подцели.
Среда Visual Prolog позволяет использовать отладчик для пошагового выполнения программы. Отладчик работает с откомпилированным кодом. В исходном коде можно ставить точки останова и выполнять программу по шагам. В режиме пошагового выполнения программы можно просматривать значения переменных и содержимое утвержденных фактов.
Пример
Имеется база данных, содержащая факты вида отдыхает(имя, город), украина(город), россия(город),прибалтика(город). Составить правило, позволяющее определить, кто отдыхал в России.
Проследить поиск решения задачи с помощью отладчика Visual Prolog и построить целевое дерево поиска с возвратом.
Решение:
1. Создайте новый проект (Project | New Project) и наберите текст программы:
DOMAINS
имя, город=string
PREDICATES
отдыхает(имя, город)
украина(город).
россия(город).
прибалтика(город).
отдых_Россия(имя)
CLAUSES
отдыхает(sasha, antalia).
отдыхает(anna, sochi).
отдыхает(dima, urmala).
отдыхает(oleg, kiev).
украина(kiev).
россия(sochi).
прибалтика(urmala).
отдых_Россия(X):-
отдыхает(X,Y),
россия(Y).
GOAL
отдых_Россия(X),
write(X),nl.
3. Сохраните проект (Project | Save Project)
4. Запустите его на исполнение ( Project | Run, или клавиша <F9>, или кнопка <R>). Результат выполнения программы:
anna
5. Проследите поиск этого решения с помощью отладчика(Debugger). Для этого:
а) запустите отладчик (Project | Debug);
б) в окне отладчика выберите команду View | Local Variables (для просмотра текущих значений переменных);
в) нажимайте клавишу <F7>(или Run | Trace Into) для пошагового выполнения программы, текущие значения переменных отображаются в окне Variables For Current Clause
рис.9. Окно отладчика
Поиск решения можно представить следующим образом:
|
рис.10. Целевое дерево поиска решения