需要有关广度优先搜索生成的节点数的更多信息
More info needed on number of nodes generated by Breadth First Search
我是 AI 的新手，正在阅读 Peter Norvig 的书。我已经研究过这个问题 What is the number of nodes generated by breadth-first search?。
它说如果我们在选择扩展时对每个节点应用目标测试，那么我们有 nodes = 1 + b + b^2 + b^3 + ... + b^d + (b^ (d+1) - b)
但是，如果我的目标状态是最终深度的叶节点怎么办。所以在进球之后根本没有深度。那么b^(d+1)怎么求值呢。例如：在最大深度为 3 的树中，如果我的目标位于深度 3，那么当根本没有第 4 层时我将如何评估 b^(3+1)？请解开我的疑惑。提前致谢！
请注意，您链接的答案提到，这是在 最坏情况 中将 生成 的节点数量。
Generated 表示并非所有这些节点都经过测试以查看它们是否是目标；它们只是简单地生成和存储，以便最终可以将它们与目标进行比较，以防尚未找到目标。
最坏情况 有两个重要的含义。尝试想象广度优先搜索从左到右，然后下降一级，然后再次从左到右，然后下降，等等。在最坏的情况下，我们假设，在任何深度级别 d 目标位于，目标是最后（最右边）的节点。这意味着它左侧的所有节点都将与目标节点进行比较，并且还会生成其中的任何 successors/children。
现在，我知道你说在你的案例中没有深度级别低于 d 的节点，但是第二个最坏情况的含义是我们确实假设基本上有无限多的深度级别。
确实，对于你的情况，这个等式并不完全正确，但这只是因为你没有最坏的情况 .在您的情况下，搜索过程确实不必生成方程的最后 (b^(d+1) - b) 个节点。
关于您使用的术语的最后说明：您询问如何 b^(d+1)（例如，b^(3+1)如果没有低于 d = 3 的深度级别，则可以评估 。从数学上评估该术语仍然没有问题。即使在您的情况下也没有深度级别 4 , 我们仍然可以在数学上评估 b^(3+1) 项。在你的情况下这样做是没有意义的，因为它是不正确的，但我们仍然可以评估任期刚刚好。
我是 AI 的新手，正在阅读 Peter Norvig 的书。我已经研究过这个问题 What is the number of nodes generated by breadth-first search?。 它说如果我们在选择扩展时对每个节点应用目标测试，那么我们有 nodes = 1 + b + b^2 + b^3 + ... + b^d + (b^ (d+1) - b) 但是，如果我的目标状态是最终深度的叶节点怎么办。所以在进球之后根本没有深度。那么b^(d+1)怎么求值呢。例如：在最大深度为 3 的树中，如果我的目标位于深度 3，那么当根本没有第 4 层时我将如何评估 b^(3+1)？请解开我的疑惑。提前致谢！
请注意，您链接的答案提到，这是在 最坏情况 中将 生成 的节点数量。
Generated 表示并非所有这些节点都经过测试以查看它们是否是目标；它们只是简单地生成和存储，以便最终可以将它们与目标进行比较，以防尚未找到目标。
最坏情况 有两个重要的含义。尝试想象广度优先搜索从左到右，然后下降一级，然后再次从左到右，然后下降，等等。在最坏的情况下，我们假设，在任何深度级别 d 目标位于，目标是最后（最右边）的节点。这意味着它左侧的所有节点都将与目标节点进行比较，并且还会生成其中的任何 successors/children。
现在，我知道你说在你的案例中没有深度级别低于 d 的节点，但是第二个最坏情况的含义是我们确实假设基本上有无限多的深度级别。
确实，对于你的情况，这个等式并不完全正确，但这只是因为你没有最坏的情况 .在您的情况下，搜索过程确实不必生成方程的最后 (b^(d+1) - b) 个节点。
关于您使用的术语的最后说明：您询问如何 b^(d+1)（例如，b^(3+1)如果没有低于 d = 3 的深度级别，则可以评估 。从数学上评估该术语仍然没有问题。即使在您的情况下也没有深度级别 4 , 我们仍然可以在数学上评估 b^(3+1) 项。在你的情况下这样做是没有意义的，因为它是不正确的，但我们仍然可以评估任期刚刚好。