Не избыточно ли повторно сканировать n-1 уровней узлов для каждой итерации?
Я цитирую Искусственный интеллект: современный подход :
Итеративный углубленный поиск может показаться расточительным, поскольку состояния генерируются несколько раз.Оказывается, это не слишком дорого.Причина в том, что в дереве поиска с одинаковым (или почти одинаковым) фактором ветвления на каждом уровне большинство узлов находятся на нижнем уровне, поэтому не имеет большого значения, что верхние уровни генерируются многократно.В итеративном углубленном поиске узлы на нижнем уровне (глубина d ) генерируются один раз, узлы на нижнем уровне - дважды, и так далее, вплоть до дочерних элементов корня., которые генерируются d раз.Таким образом, общее количество узлов, сгенерированных в худшем случае, составляет N (IDS) = (d) * b + (d-1) * b ^ 2 + ... + (1) * b ^ d , что дает временную сложность O (b ^ d) - асимптотически такую же, как поиск в ширину.
Итеративный углубленный поиск может показаться расточительным, поскольку состояния генерируются несколько раз.Оказывается, это не слишком дорого.Причина в том, что в дереве поиска с одинаковым (или почти одинаковым) фактором ветвления на каждом уровне большинство узлов находятся на нижнем уровне, поэтому не имеет большого значения, что верхние уровни генерируются многократно.В итеративном углубленном поиске узлы на нижнем уровне (глубина d ) генерируются один раз, узлы на нижнем уровне - дважды, и так далее, вплоть до дочерних элементов корня., которые генерируются d раз.Таким образом, общее количество узлов, сгенерированных в худшем случае, составляет
N (IDS) = (d) * b + (d-1) * b ^ 2 + ... + (1) * b ^ d
, что дает временную сложность O (b ^ d) - асимптотически такую же, как поиск в ширину.