The GATE Grind

GATE 2025 DA – Question 44

Artificial Intelligence · Search: informed, uninformed and adversarial · 2 marks · Multiple choice

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?

Diagram for GATE 2025 DA question 44
  1. S,A,E,C,B,D,G
  2. S,E,A,C,B,D,G
  3. S,A,E,B,C,D,G
  4. S,A,B,E,C,D,G

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

All Search: informed, uninformed and adversarial questions →