ВУЗ:
Составители:
Рубрика:
64
3.2 Основные стратегии поиска решений в пространстве
состояний
3.2.1 Поиск в глубину
Программа решения задачи о N ферзях реализует стратегию поиска в
глубину. Под термином «в глубину» имеется в виду тот порядок, в котором
рассматриваются альтернативы в пространстве состояний. Всегда, когда
алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в
которую следует перейти для продолжения поиска, он предпочитает самую
«глубокую» из них. Самая глубокая вершина – это вершина, расположенная
дальше других от стартовой вершины. На следующем рисунке показан
пример, который иллюстрирует работу алгоритма поиска в глубину. Этот
порядок в точности соответствует результату трассировки процесса
вычислений при поиске решения.
Порядок
обхода вершин указан пунктирными стрелками, a – начальная
вершина, j и f – целевые вершины.
Поиск в глубину наиболее адекватен рекурсивному стилю
программирования, принятому в Прологе. Причина этого состоит в том, что
обрабатывая цели, Пролог сам просматривает альтернативы именно в
глубину.
На Прологе переход от одной проблемной ситуации к другой может
быть представлен при помощи
предиката after (X, Y, C), который истинен
тогда, когда в пространстве состояний существует разрешенный ход из
вершины X в вершину Y, стоимость которого равна C. Предикат after может
быть задан в программе явным образом в виде фактов, однако такой принцип
a
b
c
d
e f
g
h i
j
k
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
