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

Question

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

Answer 1

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

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

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

时间复杂度为 O(b^d) - 渐近与广度优先搜索相同。