Space 广度优先搜索 (BFS) 算法的复杂性
Space Complexity in Breadth First Search (BFS) Algorithm
根据
Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig (Version 4)，space BFS 的复杂度为 O(b^d)，其中 'b' 是分支因子，'d' 是深度。
BFS的复杂度是通过这个假设获得的：我们存储所有节点直到我们到达目标节点，换句话说：1 + b + b^2 + b^3 + ... + b^d => O(b^d)
但是为什么要存储所有节点呢？我们不是用队列来实现吗？
如果我们使用队列，不需要存储所有节点，因为我们分步入队和出队一些节点，然后当我们找到目标节点时，我们可以说一些节点在队列中（但不是所有这些）。
我的理解有误吗？
在我们应用 BFS 的任何时候，队列最多有两级节点，例如，如果我们刚开始搜索深度 d，那么队列现在包含深度 d 的所有节点，并且随着我们继续queue 将在深度 d 处完成所有节点并在深度 d+1 处拥有所有节点，因此在任何时候我们都有 O(b^d) space.
还有 1+b+b^2+...+b^d = (b^(d+1)-1)/(b-1).
BFS 中的问题是您基本上并行地追求多条路径。在 depth-first 搜索中，你只取一个分支，一旦探索完，它上面的所有节点都可以出队。因此，您的队列中永远不需要超过一个分支价值的节点。
但是在 BFS 中你必须保持每个分支达到当前深度；你不能丢弃它们中的任何一个，因为它们还没有被完全探索过。因此，您需要跟踪路径的当前 'head'-节点的 'history'。在 DFS 中一次只有一条路径，但在 BFS 中有更多路径，具体取决于分支因子和当前深度。
根据 Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig (Version 4)，space BFS 的复杂度为 O(b^d)，其中 'b' 是分支因子，'d' 是深度。
BFS的复杂度是通过这个假设获得的：我们存储所有节点直到我们到达目标节点，换句话说：1 + b + b^2 + b^3 + ... + b^d => O(b^d)
但是为什么要存储所有节点呢？我们不是用队列来实现吗？
如果我们使用队列，不需要存储所有节点，因为我们分步入队和出队一些节点，然后当我们找到目标节点时，我们可以说一些节点在队列中（但不是所有这些）。
我的理解有误吗？
在我们应用 BFS 的任何时候，队列最多有两级节点，例如，如果我们刚开始搜索深度 d，那么队列现在包含深度 d 的所有节点，并且随着我们继续queue 将在深度 d 处完成所有节点并在深度 d+1 处拥有所有节点，因此在任何时候我们都有 O(b^d) space.
还有 1+b+b^2+...+b^d = (b^(d+1)-1)/(b-1).
BFS 中的问题是您基本上并行地追求多条路径。在 depth-first 搜索中，你只取一个分支，一旦探索完，它上面的所有节点都可以出队。因此，您的队列中永远不需要超过一个分支价值的节点。
但是在 BFS 中你必须保持每个分支达到当前深度；你不能丢弃它们中的任何一个，因为它们还没有被完全探索过。因此，您需要跟踪路径的当前 'head'-节点的 'history'。在 DFS 中一次只有一条路径，但在 BFS 中有更多路径，具体取决于分支因子和当前深度。