depth-first-search - 迭代加深如何比仅扫描指定深度级别的节点更有效。

Question

每次迭代重新扫描 n-1 级节点不是多余的吗？

Answer 1

我引用人工智能：一种现代方法：

迭代深化搜索可能看起来很浪费，因为状态是多次生成的。事实证明，这并不太昂贵。原因是在每一层具有相同（或几乎相同）分支因子的搜索树中，大部分节点都在底层，因此上层生成多次并不重要。在迭代加深搜索中，最底层（深度d）的节点生成一次，次底层的节点生成两次，依此类推，直到根的子节点，生成d次. 所以最坏情况下生成的节点总数为

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

这给出了 O(b^d) 的时间复杂度 - 与广度优先搜索渐近相同。