GATE 2025 DA – Question 44
The state graph shows the action cost along the edges and the heuristic function $h$ associated with each state.
[Figure: A directed state graph. S goes to A (cost 4) and to E (cost 1). A goes to B (cost 2). B goes to C (cost 2). E goes to C (cost 2). C goes to D (cost 3). D goes to G (cost 3). The heuristic values are h(A) = 2, h(B) = 2, h(C) = 6, h(D) = 2, h(E) = 6 and h(G) = 0.]
Suppose $A^*$ algorithm is applied on this state graph using priority queue to store the frontier. In what sequence are the nodes expanded?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) S,A,E,B,C,D,G
Explanation
A* expands the node with the smallest $f = g + h$. From S, A has $f = 4 + 2 = 6$ and E has $f = 1 + 6 = 7$, so A is expanded first. A gives B with $f = 6 + 2 = 8$, so the frontier is E (7) and B (8), and E is expanded. E gives C with $g = 3$ and $f = 3 + 6 = 9$, so the frontier is B (8) and C (9), and B is expanded. B offers C a worse cost ($g = 8$, $f = 14$), so C stays at 9 and is expanded next. C gives D with $g = 6$ and $f = 8$, then D gives G with $f = 9$. The order is S, A, E, B, C, D, G.