GATE 2025 DA Q.44: solution and answer

GATE 2025 · DAQ.44 · 2 marks · MCQ

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?

GATE 2025 DA question 44: Directed graph. — Figure from the GATE 2025 DA paper. It is part of the question.

(A)
S,A,E,C,B,D,G
(B)
S,E,A,C,B,D,G
(C)
S,A,E,B,C,D,G
(D)
S,A,B,E,C,D,G

Answer and solution

ANSWER

The nodes are expanded in the order S, A, E, B, C, D, G, which is option (C).

Official answer: CSource: Official answer key, GATE 2025 DA (IIT Roorkee)

A* always expands the frontier node with the smallest $f (n) = g (n) + h (n)$ , where $g (n)$ is the cheapest path cost found so far from $S$ and $h (n)$ is the printed heuristic. Edge costs: $S \to A = 4$ , $S \to E = 1$ , $A \to B = 2$ , $B \to C = 2$ , $E \to C = 2$ , $C \to D = 3$ , $D \to G = 3$ .
Expand $S$ . Its successors enter the frontier: $A$ with $g = 4$ , $f = 4 + 2 = 6$ , and $E$ with $g = 1$ , $f = 1 + 6 = 7$ .
The smallest $f$ is $A$ (6), so expand $A$ . Push $B$ with $g = 4 + 2 = 6$ , $f = 6 + 2 = 8$ . Frontier: $E (7)$ , $B (8)$ .
The smallest $f$ is $E$ (7), so expand $E$ . Push $C$ with $g = 1 + 2 = 3$ , $f = 3 + 6 = 9$ . Frontier: $B (8)$ , $C (9)$ .
The smallest $f$ is $B$ (8), so expand $B$ . It reaches $C$ with $g = 6 + 2 = 8$ , $f = 8 + 6 = 14$ . This is worse than the existing entry for $C$ ( $g = 3$ , $f = 9$ ), so the entry is kept. Frontier: $C (9)$ .
Expand $C$ . Push $D$ with $g = 3 + 3 = 6$ , $f = 6 + 2 = 8$ .
Expand $D$ (8). Push $G$ with $g = 6 + 3 = 9$ , $f = 9 + 0 = 9$ .
Expand $G$ , the goal. The expansion order is $S, A, E, B, C, D, G$ , which is option (C). No ties occurred, so no tie-break rule was needed.

KEY IDEA

A* orders the frontier by $f (n) = g (n) + h (n)$ , not by $g$ alone and not by $h$ alone. Keep, for each node, the cheapest $g$ found so far, and discard a later path that is costlier.

WATCH OUT FOR

Expanding $E$ before $A$ because $E$ is cheaper to reach ( $g = 1$ against $4$ ). That ignores $h$ : $f (E) = 1 + 6 = 7$ is larger than $f (A) = 4 + 2 = 6$ . Another slip is expanding $C$ before $B$ . $C$ is reached early through $E$ , but its $f = 9$ is larger than $f (B) = 8$ .

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 7 Search questions, with notes

GATE 2025 DA Q.44: solution and answer

Answer and solution

More Search questions