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 GATE DA Programming and Data Structures Questions
- 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
- 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
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
- 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). 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).
Top GATE DA Searching, Sorting and Hashing Questions
- 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
- 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
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
Top GATE DA Questions
- Rishi and Swathi are students of Class 5. Pavan and Tanvi are students of Class 4. Rishi and Pavan are boys. Swathi and Tanvi are girls. These four students played a total of three games of chess. The games were played one after another. A player who lost a game did not participate in any more games. It was observed that:
1. The first game was the only game where two students of the same class played against each other.
2. The students of Class 5 won more games than the students of Class 4.
3. The boys won 2 games and the girl won 1 game.
The student who did not lose any game is:- GATE DA - 2026
- Logical Reasoning
Consider two distinct positive numbers \( m, n \) with \( m > n \). Let \[ x = n^{\log_n m}, \quad y = m^{\log_m n}. \] The relation between \( x \) and \( y \) is -
- GATE DA - 2026
- Logarithms
- Consider the supervised learning task. The objective function being minimized is \( f(w) = w \cdot x \), where \( w \in \mathbb{R} \) is the parameter. Stochastic Gradient Descent with learning rate of 0.10. Let \( w = 10.00 \) be the \( i^{\text{th}} \) iteration (\( w_i \)). The value of \( w \) at the end of iteration \( (i+1) \) is if \( x = 10 \) ________. Round off 2 decimal.
- GATE DA - 2026
- Machine Learning
- The value of \[ \sum_{j=0}^{\infty} \sum_{i=1}^{\infty} 2^{-j} 3^{-i} \] is ________.
- GATE DA - 2026
- Sequences and Series
- Consider the Ridge LRR is being used to learn prediction function \( y_{\text{pred}} = w^T x \) where \( w, x \in \mathbb{R}^2 \) & mean absolute error (MAE) is used to measure the prediction error. A weight of 0.20 is associated with the regularizer. At an intermediate step of training process assume that the parameter \( w = [-3.00, 4.00]^T \). In the next step for the I/P \( x = [1.00, 2.00]^T \), the predicted value of \( y \) is noted. Let the relation b/w \( x = [x_1, x_2]^T \) & the true value of \( y \) be \( y_{\text{true}} = x_1 + x_2 \). The value of the overall regularized loss for instance is __________ (upto 2 decimal).
- GATE DA - 2026
- Machine Learning
View More Questions