GATE 2025 DA – Question 44
The state graph shows the action cost along the edges and the heuristic function $h$ associated with each state.
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.
More Search: informed, uninformed and adversarial questions
- GATE 2024 DA Q23
- GATE 2024 DA Q25
- GATE 2024 DA Q44
- GATE 2026 DA Q13
- GATE 2026 DA Q30
- GATE 2025 DA Q43
All Search: informed, uninformed and adversarial questions →