我只是想看看我对罗素和诺维格给出的算法和计算的理解是否正确。
我用传教士和食人族作为一个问题来测试时间和空间的复杂性。计算深度没什么大不了的。我总是在深度11找到答案我不能把我的头包起来的是分支因素。
罗素和诺维格第82页说：
“在探索的集合中将有O(b^(d-1))节点和O(b^d)节点
在边疆……”
我的程序显示了探索集中的8502节点和边界中的14006节点。
我的思维过程是这样的：如果我根据Russell和Norvig取节点数并取d根，我应该得到分支因子是什么现在我不知道我的想法是否正确。我刚想到的。
因此，取的第十（d-1）根，得到8502（近似），取的第十一（d）根，得到2.47（近似）。所以我的结论是分支因子b大致是14006。
我到底是成功了还是完全错了？这是我现在正在做的事情之一。但我想知道我是错是对的。
最佳答案
基于探索集和边界集对分支因子的估计基本上是正确的。对于小深度，分支因子的估计对于边界集比探索集更为合理，因为探索集包含过去访问过的所有顶点，这更像是1 + b + ... + b^(d-1)，而不仅仅是b^(d-1)请注意，随着探索集的增长，将有越来越多的邻居顶点已经被探索，因此对于边框集的近似b^d随着深度的增加将变得越来越不好。在极端情况下，当您已经探索了所有顶点时，边框集都不包含顶点，所以您将近似为ccc>为0。但是无论如何，你的估计过程看起来很好，并且在边界集和探索集之间给出了高度一致的结果。您可能应该单独使用边界集来估计分支因子。
关于algorithm - 广度优先搜索的时空复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21054959/