GATE DA Search Previous Year Questions

GATE DA 2025 | Question 44

MCQ · 2 marks · −0.66

The state graph shows the action cost along the edges and the heuristic function h associated with each state.

Directed state graph with edges S to A (cost 4), S to E (cost 1), A to B (cost 2), B to C (cost 2), E to C (cost 2), C to D (cost 3) and D to G (cost 3). The heuristic values are h=2 for A, h=2 for B, h=6 for C, h=2 for D, h=6 for E and h=0 for G, and no value is shown for S.

Suppose \(A^{*}\) algorithm is applied on this state graph using priority queue to store the frontier. In what sequence are the nodes expanded?

S,A,E,C,B,D,G S,E,A,C,B,D,G S,A,E,B,C,D,G S,A,B,E,C,D,G

Explanation

Answer: (C)

A* always expands the frontier node with the smallest \(f = g + h\), where \(g\) is the path cost from S.

Expand S: frontier A (\(4 + 2 = 6\)) and E (\(1 + 6 = 7\)).
Expand A (6): add B (\(6 + 2 = 8\)).
Expand E (7): add C (\(3 + 6 = 9\)).
Expand B (8): reaching C through B costs 8, worse than 3, so C keeps \(f = 9\).
Expand C (9): add D (\(6 + 2 = 8\)).
Expand D (8): add G (\(9 + 0 = 9\)), and finally expand G.

The order is S, A, E, B, C, D, G. Option A expands C (9) before B (8), and ordering by \(h\) alone would put B before E, as in option D.

Answer: C

GATE DA 2024 | Question 23

MCQ · 1 mark · −0.33

Let \(h_{1}\) and \(h_{2}\) be two admissible heuristics used in \(A^{*}\) search.

Which ONE of the following expressions is always an admissible heuristic?

\(h_{1} + h_{2}\) \(h_{1} \times h_{2}\) \(h_{1}/h_{2}, (h_{2} \neq 0)\) \(|h_{1} - h_{2}|\)

Explanation

Answer: (D)

A heuristic is admissible when \(0 \leq h(n) \leq h^{*}(n)\) for every node \(n\), where \(h^{*}(n)\) is the true cost of reaching the goal. Because both values are non-negative,

\[|h_{1}(n) - h_{2}(n)| \leq \max(h_{1}(n), h_{2}(n)) \leq h^{*}(n),\]

so option D never overestimates.

The other expressions can overestimate. With \(h^{*}(n) = 5\) and \(h_{1}(n) = h_{2}(n) = 5\), both admissible, the sum is 10 and the product is 25. With \(h_{1}(n) = 5\) and \(h_{2}(n) = 0.1\), the ratio is 50.

Answer: D

GATE DA 2024 | Question 44

MCQ · 2 marks · −0.66

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?

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

Explanation

Answer: (C)

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