Consider a state space where the start state is number 1. The successor…
2024
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?
- A.
BFS expands more states than DFS.
- B.
DFS expands more states than BFS.
- C.
Both BFS and DFS expand equal number of states.
- D.
Both BFS and DFS do not reach the goal state number 6.
Attempted by 100 students.
Show answer & explanation
Correct answer: C
Key insight: the rule that the unexpanded states are always expanded in ascending order makes both searches choose the same next state.
Start by expanding 1 → adds 2 and 3 to the unexpanded list.
Next pick the smallest-numbered unexpanded state each time. That yields the expansion order: 1, 2, 3, 4, 5, 6.
Because both BFS and DFS follow that same selection order under the given rule (and previously expanded states are not re-added), they expand exactly the same states up to the goal.
Conclusion: Both searches expand the same number of states (they expand states 1 through 6) to reach the goal.