The GATE Grind

GATE 2024 DA – Question 44

Artificial Intelligence · Search: informed, uninformed and adversarial · 2 marks · Multiple choice

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?

  1. BFS expands more states than DFS.
  2. DFS expands more states than BFS.
  3. Both BFS and DFS expand equal number of states.
  4. Both BFS and DFS do not reach the goal state number 6.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Both BFS and DFS expand equal number of states.

Explanation

Since the unexpanded states are always expanded in ascending order of their numbers, the next state to expand is always the smallest number in the list, whether the search is BFS or DFS. The expansion order is then 1, 2, 3, 4, ... for both. The goal 6 is generated when state 4 is expanded, so both expand the same states (1, 2, 3, 4) before reaching the goal.