GATE DA 2025 | Question: 34

Question

​​​​​​The state graph shows the action cost along the edges and the heuristic function $\text{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?

• A. $\mathrm{S}, \mathrm{A}, \mathrm{E}, \mathrm{C}, \mathrm{B}, \mathrm{D}, \mathrm{G}$
• B. $\mathrm{S}, \mathrm{E}, \mathrm{A}, \mathrm{C}, \mathrm{B}, \mathrm{D}, \mathrm{G}$
• C. $\mathrm{S}, \mathrm{A}, \mathrm{E}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{G}$
• D. $\mathrm{S}, \mathrm{A}, \mathrm{B}, \mathrm{E}, \mathrm{C}, \mathrm{D}, \mathrm{G}$

Answer 1

Shortest path searched by A* is $S,E,C,D,G$
Node visit order: $S, A, E, B, C, D, G$ 
option (C)

Edit: Please refer to my comment, earlier in haste I wrote answer d which was inaccurate.

 

Comments

Note that, here,
After S, A, B, C algo will come back to B (since F(B)<F(C) and B is in openList) but since F(C) thru B is greater than F(C) thru E, Algo will mark B closed and continue its path thru E.

---

I think the correct answer is option C.Can you once check it.

 

---

Yes you are correct. Node order is asked,
I had answered first and added the comment later.
And hence Option (C) would be correct. Apologies for the mistake