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?

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: Apr 4, 2025

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

Hide 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).

Was this answer helpful?

Questions Asked in GATE DA exam

Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0 < j - i \leq 2, \text{ for all } i,j \in V \}. \] Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is:
- GATE DA - 2025
- Data Structures
View Solution

Consider the following pseudocode.

Create empty stack S
Set x = 0, flag = 0, sum = 0
Push x onto S
while (S is not empty){
    if (flag equals 0){
        Set x = x + 1
        Push x onto S
    }
    if (x equals 8):
        Set flag = 1
    if (flag equals 1){
        x = Pop(S)
        if (x is odd):
            Pop(S)
        Set sum = sum + x
    }
}
Output sum

The value of \( sum \) output by a program executing the above pseudocode is:

GATE DA - 2025
Data Structures

View Solution

Consider the following Python code snippet.

def f(a, b):
    if (a == 0):
        return b
    if (a % 2 == 1):
        return 2 * f((a - 1) / 2, b)
    return b + f(a - 1, b)

print(f(15, 10))

The value printed by the code snippet is 160 (Answer in integer).

GATE DA - 2025
Recursion