1. 在最坏情况下，使用广度优先搜索，当解决方案位于深度d，分支因子为b，最大分支的深度为m时，访问了多少个节点（从队列中选择）？
   给出一个公式。

2. 在最坏情况下，使用广度优先搜索，当解决方案位于深度d，分支因子为b，最大分支的深度为m时，生成了多少个节点（由于扩展父节点而添加到队列中）？
   给出一个公式。

3. 使用深度优先搜索，当解决方案位于深度d，分支因子为b，最大分支的深度为m时，队列的最小可能大小是多少？请在一个小型搜索树上解释你的答案。

回答：

1. 1 + b + b² + … + b^d，即O(b^d)

2. 1 + b + b² + … + b^d+1 – b，即O(b^d+1)

3. b * m

注意：DFS中的边缘是堆栈而不是队列（或者你可以称之为LIFO队列）。

1, 2：看下面的图表作为一个例子，其中b = 3，我用红圈标出了目标状态。

对于这棵树，紫色框中的所有节点都被访问，而这些节点 + 橙色框中的节点都被添加到边缘中。

3：在下面的图中，电路内（设计得真差；D） 的所有节点都被添加到边缘中。