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: Jan 30, 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
- 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
- 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:
\[ \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
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
Consider the following tables, Loan and Borrower, of a bank.
Query: \[ \pi_{\text{branchname}, \text{customername}} (\text{Loan} \bowtie \text{Borrower}) \div \pi_{\text{branchname}}(\text{Loan}) \] where \( \bowtie \) denotes natural join. The number of tuples returned by the above relational algebra query is (Answer in integer).- GATE DA - 2025
- Relational Algebra
- Let \( D = \{ x^{(1)}, x^{(2)}, \dots, x^{(n)} \} \) be a dataset of \( n \) observations where each \( x^{(i)} \in \mathbb{R}^{100} \). It is given that \[ \sum_{i=1}^{n} x^{(i)} = 0. \] The covariance matrix computed from \( D \) has eigenvalues \( \lambda_i = 100^2 - i \), for \( 1 \leq i \leq 100 \). Let \( u \in \mathbb{R}^{100} \) be the direction of maximum variance with \( u^T u = 1 \). The value of \[ \frac{1}{n} \sum_{i=1}^{n} \left( u^T x^{(i)} \right)^2 = \underline{\hspace{2cm}} \quad \text{(Answer in integer)} \]
- GATE DA - 2025
- Matrix algebra
- The naive Bayes classifier is used to solve a two-class classification problem with class-labels \( y_1, y_2 \). Suppose the prior probabilities are \( P(y_1) = \frac{1}{3} \) and \( P(y_2) = \frac{2}{3} \). Assuming a discrete feature space with \[ P(x | y_1) = \frac{3}{4} \quad \text{and} \quad P(x | y_2) = \frac{1}{4} \] for a specific feature vector \( x \). The probability of misclassifying \( x \) is: (Round off to two decimal places)
- GATE DA - 2025
- Machine Learning
- Given data \( \{(-1, 1), (2, -5), (3, 5)\} \) of the form \( (x, y) \), we fit a model \( y = wx \) using linear least-squares regression. The optimal value of \( w \) is:
(Round off to three decimal places)- GATE DA - 2025
- Linear Algebra
View More Questions