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

Поиск с возвратом (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 (для просмотра текущих значений переменных);

поиск с возвратом - student2.ru в) нажимайте клавишу <F7>(или Run | Trace Into) для пошагового выполнения программы, текущие значения переменных отображаются в окне Variables For Current Clause

поиск с возвратом - student2.ru

рис.9. Окно отладчика

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

решение: X= anna
поиск с возвратом - student2.ru поиск с возвратом - student2.ru

рис.10. Целевое дерево поиска решения

Наши рекомендации