artificial-intelligence - 通过增加分支因子和深度在迭代深化中的开销效应

Question

我正在从这个链接学习迭代深化。我主要关心的是Overhead。该链接说

分支因子越高，重复扩展状态的开销越低

该声明没有给出解释，该链接也没有给出令人信服的论据。我正在寻找这个陈述背后的原因，因为我认为开销应该随着分支因子的增加而增加，这也意味着没有节点在增加，那么开销是如何减少的？

直到现在我还没有找到任何合理和有用的东西。如果有人可以帮助纠正我的概念，那么我将不胜感激。

Answer 1

您的问题的答案在语句上方的公式中

 (d)b + (d-1)b^{2} + \cdots + 3b^{d-2} + 2b^{d-1} + b^{d}

做 BFS 的成本——你应该比较的是——

 b + b^{2} + \cdots + b^{d-2} + b^{d-1} + b^{d}

因此开销是

   (d-1)b + (d-2)b^{2} + \cdots + 2b^{d-2} + 1b^{d-1} 

显然，这在很大程度上受到分支因素的影响。尤其是在看最后一个学期的时候1b^{d-1}