广度优先搜索的时空复杂度

Question

我只是想看看我对罗素和诺维格的算法和计算的理解是否正确。

我用传教士和食人族作为一个问题来测试时间和空间的复杂性。计算深度没什么大不了的。我总是在11深度找到解决方案，但我不能把头绕在头上的是分支因子。

拉塞尔和诺维格第82页说：

“在探索的集合中将有O(b^(d-1))节点，在前沿将有O(b^d)节点.”

我的程序显示了探索集中的8502节点和前沿的14006节点。

我的思维过程是这样的:如果我根据罗素和诺维格取节点数并取d根，我应该得到分支因子是什么。现在我不知道我的想法是否正确。我刚想出来的。

我取8502的第10 (d-1)根，得到2.47 (约)，取14006的第11 (d)根，得到2.39 (约)。所以我的结论是，分支因子b大概是2.43。

我到底是击中了目标，还是我完全错了？这是我现在正在做的事情之一。但我很想知道我是错是对。

Answer 1

您基于探索集和边界集对分支因子的估计基本上是正确的。对于较小的深度，分支因子的估计对于边界集比探索集更合理，因为探索集包含过去访问过的所有顶点，这些顶点更像1 + b + ... + b^(d-1)，而不仅仅是b^(d-1)。请注意，随着探索集的增长，您将拥有越来越多已经被探索过的相邻顶点，因此，随着深度的增加，边界集的近似b^d将变得越来越差。在极端情况下，当您探索了所有的顶点时，边框集将不包含任何顶点，因此您将b^d近似为0。但是无论如何，您的评估过程看起来很好，并且在边界集和探索集之间给出了非常一致的结果。您可能应该单独使用边界集来给出分支因子的估计。