Чем итеративное углубление более эффективно, чем простое сканирование узлов на заданном уровне глубины.

Question

Не избыточно ли повторно сканировать n-1 уровней узлов для каждой итерации?

Answer 1

Я цитирую " Искусственный интеллект: современный подход":

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

N(IDS) = (d)*b+(d-1)*b^2+...+(1)*b^d

которая дает временную сложность O(b^d) - асимптотически такая же, как поиск в ширину.