Consider a state space where the start state is number 1. The successor function for the state numbered \(n\) returns two states numbered \(n+1\) and \(n+2\). Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.
Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?
Answer
(C)
Explanation
Successors come out as \(n+1\) and then \(n+2\), and the smaller number always goes first.
- BFS: expanding 1 queues 2 and 3; expanding 2 adds 4 (3 is already waiting); expanding 3 adds 5; expanding 4 adds 6; expanding 5 adds 7. Then 6 leaves the queue. Expanded: 1, 2, 3, 4, 5.
- DFS: it always dives into the smaller child \(n+1\), so it expands 1, 2, 3, 4, 5 and then reaches 6.
Both searches expand the same five states before reaching the goal (or four each if the goal is tested when it is generated, since both then stop while expanding 4). State 6 is reachable, so option D is false.
Answer: C