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
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).
\[ 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 Questions on Searching, Sorting and Hashing
- For which of the following inputs does binary search take time \( O(\log n) \) in the worst case?
- GATE DA - 2025
- Programming and Data Structures
- Searching, Sorting and Hashing
- Suppose that insertion sort is applied to the array \( [1, 3, 5, 7, 9, 11, x, 15, 13] \) and it takes exactly two swaps to sort the array. Select all possible values of \( x \).
- GATE DA - 2025
- Programming and Data Structures
- Searching, Sorting and Hashing
Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.
For what ranges of \( x \) and \( y \), the right child of node B and the right child of node E will be pruned by the alpha-beta pruning algorithm?- GATE DA - 2025
- Programming and Data Structures
- Searching, Sorting and Hashing
- The pseudocode of a function \( fun() \) is given below:
fun(int A[0, ..., n-1]) { for i = 0 to n-2 for j = 0 to n - i - 2 if (A[j] > A[j+1]) then swap A[j] and A[j+1] }Let \( A[0, \ldots, 29] \) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function \( fun() \) is called with \( A[0, \ldots, 29] \) as argument, is __________ (Answer in integer).- GATE CS - 2025
- Programming and Data Structures
- Searching, Sorting and Hashing
- The pseudocode of a function \( fun() \) is given below:
\[ \text{fun(int A[0, \ldots, n-1])} \{ \] \[ \text{for } i = 0 \text{ to } n-2 \] \[ \text{for } j = 0 \text{ to } n - i - 2 \] \[ \text{if } (A[j] > A[j+1]) \text{ then swap } A[j] \text{ and } A[j+1] \] \[ \} \]
Let \( A[0, \ldots, 29] \) be an array storing 30 distinct integers in descending order.
The number of swap operations that will be performed, if the function \( fun() \) is called with \( A[0, \ldots, 29] \) as argument, is ______ (Answer in integer).- GATE CS - 2025
- Programming and Data Structures
- Searching, Sorting and Hashing
Questions Asked in GATE DA exam
- Which of the following statements is/are correct?
- GATE DA - 2025
- Linear Algebra
- Choose the most appropriate word to complete the analogy:
Courage : Bravery :: Yearning :- GATE DA - 2025
- Analogies
- When does the worst case of binary search occur?
- GATE DA - 2025
- Algorithm
- Suppose that insertion sort is applied to the array \([1,2,3,5,7,9,11,x,15,13]\) and it takes exactly 2 swaps to sort the array. Select all possible values of \( x \).
- GATE DA - 2025
- Algorithm
- Given the lists: \[ A = [1,2,3], \quad B = [4,5,6] \] Which of the following statements will result in \[ A = [1,2,3,4,5,6]? \]
- GATE DA - 2025
- Programming in Python
View More Questions