An A* algorithm is a heuristic search technique which
2014
An A* algorithm is a heuristic search technique which
- A.
is like a depth-first search where most promising child is selected for expansion
- B.
generates all successor nodes and computes an estimate of distance (cost) from start node to a goal node through each of the successors. It then chooses the successor with shortest cost.
- C.
saves all path lengths (costs) from start node to all generated nodes and chooses shortest path for further expansion.
- D.
none of the above
Attempted by 90 students.
Show answer & explanation
Correct answer: B
Key idea: A* selects nodes by minimizing f(n) = g(n) + h(n), where g(n) is the exact cost from the start to n and h(n) is a heuristic estimate from n to the goal.
Initialize an open set (priority queue) with the start node: g(start)=0, f(start)=h(start).
Repeat: remove the node with lowest f(n) from the open set. If it is a goal node, reconstruct and return the path.
For each successor, compute tentative g = g(current) + cost(current, successor), then f = tentative g + h(successor). If this path to the successor is better than any previously recorded, update its g and f and add or update it in the open set.
Continue until the goal is expanded or the open set is empty (no path).
Notes:
g(n) is the true cost from the start to n; h(n) is a heuristic estimate to the goal; f(n) guides the search.
If the heuristic h is admissible (never overestimates), A* is guaranteed to find an optimal path.
If the heuristic is consistent (monotone), nodes do not need to be reopened and the algorithm is more efficient.
Contrast with other searches: greedy best-first uses only h(n) (may be fast but not optimal); uniform-cost/Dijkstra uses only g(n) (optimal without heuristic). A* combines both to balance optimality and efficiency.