Tree Search algorithm (remove front node from the fringe/queue – goal test – expand)

Question

1. How many nodes are visited (chosen from the queue) in the worst case using Breadth-First search, when the solution is at depth d, and the branching factor is b, and the depth of the maximum branch is m?
   Give a formula.

2. How many nodes are generated (added to the queue as a result of expanding the parent) in the worst case using Breadth-First search, when the solution is at depth d, and the branching factor is b, and the depth of the maximum branch is m?
   Give a formula.

3. What is the minimum possible size of the queue using Depth-First search, when the solution is at depth d, and the branching factor is b, and the depth of the maximum branch is m? Explain your answer on a small search tree.

Answer 1

1. 1 + b + b² + ... + b^d that is O(b^d)

2. 1 + b + b² + ... + b^d+1 - b that is O(b^d+1)

3. b * m

Note: fringe in the DFS is stack not queue (or you may call it a LIFO queue).

1, 2 : look at the following figure as an example with b = 3 in which I've shown the goal state by a red circle.

For this tree all the nodes in the purple box get visited while all of these nodes + nodes in the orange box get added to the fringe.

3 : In the following figure all the nodes inside the circuit (really poor designed ;D ) get added to the fringe.