Question:
Consider the following graph with heuristic values:
Which of the following represents the correct order of node expansion using the A* search algorithm?
Consider the following graph with heuristic values:
Which of the following represents the correct order of node expansion using the A* search algorithm?
Show Hint
A* search uses a combination of actual cost (\( g(n) \)) and heuristic (\( h(n) \)) to find the most optimal path efficiently.
Updated On: Feb 15, 2025
- S, E, A, C, B, D, G
- S, A, B, E, C, D, G
- S, A, E, B, C, D, G
- S, A, E, C, B, D, G
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
A* search algorithm follows the path with the lowest cost function:
\[
f(n) = g(n) + h(n)
\]
where:
- \( g(n) \) is the cost from the start node to \( n \).
- \( h(n) \) is the heuristic estimate from \( n \) to the goal.
Steps:
1. Start from \( S \), expand node with the lowest \( f(n) \).
2. Expand \( A \) (cost 4) and \( E \) (cost 1).
3. Since \( E \) has the lower \( f(n) \), expand \( E \) first.
4. Continue expanding the node with the best \( f(n) \) until reaching \( G \).
Following these rules, the correct expansion order is S, A, E, B, C, D, G. Conclusion: The correct answer is (3) S, A, E, B, C, D, G based on A* search expansion.
- \( g(n) \) is the cost from the start node to \( n \).
- \( h(n) \) is the heuristic estimate from \( n \) to the goal.
Steps:
1. Start from \( S \), expand node with the lowest \( f(n) \).
2. Expand \( A \) (cost 4) and \( E \) (cost 1).
3. Since \( E \) has the lower \( f(n) \), expand \( E \) first.
4. Continue expanding the node with the best \( f(n) \) until reaching \( G \).
Following these rules, the correct expansion order is S, A, E, B, C, D, G. Conclusion: The correct answer is (3) S, A, E, B, C, D, G based on A* search expansion.
Was this answer helpful?
0
0
Top Questions on Algorithm
- Consider the following algorithm:
What will be the output (O/P) of this algorithm? - Which of the following data structures supports binary search in \( O(\log n) \) time complexity?
- When does the worst case of binary search occur?
- 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 \).
- Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is:
View More Questions
Questions Asked in GATE DA exam
- Given the table facts: \[ \text{facts (D1, D2, val)} \] with the following data:
Consider the following SQL query:
What is the total number of rows produced? - Given the equation: \[ 3^{x^2} = 27 \times 9^x \] Find the value of: \[ \frac{2^{x^2}}{(2^x)^2} \]
- GATE DA - 2025
- Algebra
- Consider the following sets: \[ A = \{"this", "that"\}, \quad B = \{"that", "other"\}, \quad C = \{"other", "this"\} \]
Which of the following sets remain non-empty at the end?- GATE DA - 2025
- Programming in Python
- Consider the given graph and shortest paths: The shortest paths given are: \[ a - b - c - d, \quad e - f - g - h, \quad a - f - c - h \] Which of the following cannot be an edge in the original graph?
- GATE DA - 2025
- Graph Theory
- Consider the following database schema: \[ \text{Person (aadhar CHAR(12) PK, name VARCHAR(32))} \] \[ \text{Customer (name VARCHAR(32), email VARCHAR(32) PK, phone CHAR, aadhar CHAR(12) FK(aadhar))} \] Which of the following statements is/are correct?
- GATE DA - 2025
- Database Concepts
View More Questions