Question

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.

Answer 1

Answer: (C)

Both BFS and DFS expand equal number of states.

Answer 2

The correct option is (C) : Both BFS and DFS expand equal number of states..