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?

  1. Option A: S,A,E,C,B,D,G
  2. Option B: S,E,A,C,B,D,G
  3. Option C: S,A,E,B,C,D,G (correct)
  4. Option D: S,A,B,E,C,D,G

Answer

(C)

Explanation

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