GATE 2024 DA Q.44: solution and answer

GATE 2024 · DAQ.44 · 2 marks · MCQ

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.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Both BFS and DFS expand the same number of states (option C).

Official answer: CSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

The question fixes the order in which the unexpanded list is processed: always the smallest state number first. BFS normally takes the oldest entry (a queue) and DFS the newest (a stack), but here that choice is overridden by the ascending-number rule, so both searches pick the same state at every step.
Start: expand $1$ . Successors $2$ and $3$ , so the unexpanded list is ${2, 3}$ .
Expand $2$ (smallest). Successors $3$ and $4$ . State $3$ is already waiting in the list, so the list is ${3, 4}$ .
Expand $3$ . Successors $4$ and $5$ . State $4$ is already waiting, so the list is ${4, 5}$ .
Expand $4$ . Successors $5$ and $6$ , so the list is ${5, 6}$ .
Expand $5$ . Successors $6$ and $7$ , so the list is ${6, 7}$ . The smallest state is now $6$ , the goal, and it is selected next.
The expansion sequence is $1, 2, 3, 4, 5$ , then the goal $6$ is reached. This sequence was produced using only the ascending-order rule, so it is exactly the same for BFS and for DFS. Even if a state were listed twice, expanding the smallest number first and never re-expanding an expanded state gives the same sequence for both.
Hence BFS and DFS expand the same states ( $1$ to $5$ , five expansions) before reaching $6$ . Options (A) and (B) are false because neither expands more than the other, and (D) is false because both reach $6$ . The correct option is (C).

KEY IDEA

When the question dictates the expansion order (smallest number first), that rule overrides the usual queue or stack behaviour of BFS and DFS. With the same order, both searches expand the same states and reach the goal after the same number of expansions.

WATCH OUT FOR

Applying the textbook behaviour of BFS (level by level) and DFS (deepest first) and concluding they differ, without noticing that the question forces the ascending-number order on both. Another slip is to count the goal itself as an expansion for one search and not the other.

From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 7 Search questions, with notes

GATE 2024 DA Q.44: solution and answer

Answer and solution

More Search questions