Question:
The state graph shows the action cost along the edges and the heuristic function \( h \) associated with each state. Suppose the A algorithm is applied on this state graph using a priority queue to store the frontier. In what sequence are the nodes expanded?
The state graph shows the action cost along the edges and the heuristic function \( h \) associated with each state. Suppose the A algorithm is applied on this state graph using a priority queue to store the frontier. In what sequence are the nodes expanded?
Show Hint
When using the A algorithm, always prioritize nodes with the lowest f-cost. The f-cost is calculated as the sum of the action cost to reach a node and its heuristic value. Use a priority queue to efficiently select the node with the lowest f-cost.
Updated On: Feb 3, 2026
- S, A, E, C, B, D, G
- S, E, A, C, B, D, G
- S, A, E, B, C, D, G
- S, A, B, E, C, D, G
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
We are given the state graph and the heuristic values \( h \). The A* algorithm expands nodes based on the f-cost, where:
\[ f(n) = g(n) + h(n) \] where \( g(n) \) is the cost to reach node \( n \) and \( h(n) \) is the heuristic value.
The f-cost calculations are:
\( f(S) = 2 \), \( f(A) = 4 \), \( f(E) = 10 \), \( f(B) = 6 \), \( f(C) = 10 \), \( f(D) = 9 \), \( f(G) = 10 \).
The order of expansion of nodes is based on their f-cost values. Thus, the nodes are expanded in the following order:
\( S, A, E, B, C, D, G \)
Thus, the correct answer is Option (C).
\[ f(n) = g(n) + h(n) \] where \( g(n) \) is the cost to reach node \( n \) and \( h(n) \) is the heuristic value.
The f-cost calculations are:
\( f(S) = 2 \), \( f(A) = 4 \), \( f(E) = 10 \), \( f(B) = 6 \), \( f(C) = 10 \), \( f(D) = 9 \), \( f(G) = 10 \).
The order of expansion of nodes is based on their f-cost values. Thus, the nodes are expanded in the following order:
\( S, A, E, B, C, D, G \)
Thus, the correct answer is Option (C).
Was this answer helpful?
0
0
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions