Поиск с итеративным углублением (или, точнее, поиск в глубину с итеративным углублением) представляет собой общую стратегию, часто применяемую в сочетании с поиском в глубину, которая позволяет найти наилучший предел глубины. Это достигается путем постепенного увеличения предела (который вначале становится равным 0, затем 1, затем 2 и т.д.) до тех пор, пока не будет найдена цель. Такое событие происходит после того, как предел глубины достигает значения d, глубины самого поверхностного целевого узла. Данный алгоритм приведен в листинге 3.5. В поиске с итеративным углублением сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется очень скромными требованиями к памяти, а именно, значением O(bd). Как и поиск в ширину, он является полным, если коэффициент ветвления конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла. На рис. 3.9 показаны четыре итерации применения процедуры Iterative-Deepening-Search к бинарному дереву поиска, где решение найдено в четвертой итерации.

Листинг 3.5. Алгоритм поиска с итеративным углублением, в котором повторно применяется поиск с ограничением глубины при последовательном увеличении пределов. Он завершает свою работу после того, как обнаруживается решение, или процедура поиска с ограничением глубины возвращает значение failure, а это означает, что решение не существует

Поиск с итеративным углублением может на первый взгляд показаться расточительным, поскольку одни и те же состояния формируются несколько раз. Но, как оказалось, такие повторные операции не являются слишком дорогостоящими. Причина этого состоит в том, что в дереве поиска с одним и тем же (или почти одним и тем же) коэффициентом ветвления на каждом уровне большинство узлов находится на нижнем уровне, поэтому не имеет большого значения то, что узлы на верхних уровнях формируются многократно. В поиске с итеративным углублением узлы на нижнем уровне (с глубиной d) формируются один раз, те узлы, которые находятся на уровне, предшествующем нижнему, формируются дважды, и т.д., вплоть до дочерних узлов корневого узла, которые формируются d раз. Поэтому общее количество формируемых узлов выражается следующей формулой: