Лекция: Поиск в глубину с итерационным заглублением.

Хорошим решением проблем поиска в глубину является использование предельного значения глубины поиска. Предельная глубина позволяет ограничить поиск только за­данным числом уровней. Это обеспечивает некоторое подобие «развертки» области по­иска в ширину при поиске в глубину.

Ограниченный поиск в глубину наиболее полезен, если известно, что решение находит­ся в пределах некоторой глубины, имеются ограничения во времени или пространство со­стояний чрезвычайно велико (как в шахматах). В таких задачах число рассматриваемых со­стояний ограничивают предельной глубиной поиска. На рис. 10.11. показан поиск в глубину для 8-головоломки, для которого предельная глубина ограничена пятью уровнями. Поэто­му именно на этой глубине возникает поперечная развертка пространства.

Такая модификация позволяет исправить нсмало недостатков как поиска в глубину, так и поиска в ширину. Итерационным заглублением [Korf, 1987] называется поиск в глубину, первая итерация которого ограничена 1 уровнем. Если цель не найдена, выпол­няется еще один шаг с предельной глубиной 2. В процессе поиска предельная глубина увеличивается на 1 на каждой итерации. На каждой итерации алгоритм выполняет поиск в глубину с учетом текущего предельного числа уровней. При этом при переходе от од­ной итерации к другой информация о пространстве состояний не сохраняется.

Поскольку алгоритм исследует пространство «по уровням», он может гарантировать нахождение кратчайшего пути к цели. Поскольку на каждой итерации осуществляется только поиск в глубину, степень использования пространства на каждом уровне п со­ставляет Вхп, где В — среднее число дочерних состояний вершины.

На первый взгляд кажется, что итерационное продвижение в глубину менее эффек­тивно по времени, чем поиск глубину или в ширину. Однако временная сложность алго­ритма (время выполнения алгоритма в зависимости от размерности задачи) в действительности имеет тот же самый порядок величины, что и каждый из этих алгоритмов О(Вn). Объяснение этого кажущегося парадокса приведено в [Korf, 1987].

«Поскольку число вершин на данном уровне дерева растет экспоненциально с увеличением глубины, почти все время вычислений тратится на самом глубоком уровне.»

К сожалению, можно показать, что в наихудшем случае все рассмотренные в этой главе стратегии поиска (поиск в глубину, в ширину и итерационное заглубление) обла­дают экспоненциальной сложностью. Это характерно для всех неинформированных алгоритмов поиска. Для снижения временной сложности алгоритмов поиска исполь­зуют направляющие эвристики. Поиск по первому наилучшему совпадению — это ал­горитм поиска, подобный представленным выше алгоритмам поиска в глубину и в ши­рину. Однако в процессе поиска по первому наилучшему совпадению состояния в спи­ске ореп, определяющие текущую границу поиска, упорядочиваются согласно некоторому эвристическому показателю качества. На каждой итерации поиск рассмат­ривает не самые глубокие, а самые «лучшие» состояния.