Questions: A* Search Algorithm

Question 1

An A* implementation uses a heuristic that occasionally overestimates the true remaining cost to the goal. What is the consequence?

• A. A* will still find the optimal path, but will explore more nodes than necessary
• B. A* may return a suboptimal path, because the inadmissible heuristic can cause it to prematurely expand a non-optimal node
• C. A* will fail to find any path, because an overestimating heuristic causes the priority queue to malfunction
• D. A* will find the optimal path faster, because overestimation pushes it more aggressively toward the goal

Answer: (B)

Admissibility — never overestimating the true remaining cost — is the property that guarantees A* finds the optimal path. When h(n) overestimates, A* may expand a node on the optimal path before it has found the cheapest route to that node, causing it to commit to a suboptimal solution. Option D describes the appeal of inadmissible heuristics (they're faster), but the tradeoff is lost optimality. Option A is incorrect: an inadmissible heuristic doesn't just slow A* down, it can derail it entirely.

Question 2

You set h(n) = 0 for every node and run A*. What does A* become in this case?

• A. Breadth-first search, expanding nodes in order of depth from the start
• B. Greedy best-first search, expanding the node closest to the goal
• C. Dijkstra's algorithm, expanding the node with the lowest accumulated path cost g(n)
• D. An exhaustive depth-first search with backtracking

Answer: (C)

With h(n) = 0 everywhere, the evaluation function reduces to f(n) = g(n) + 0 = g(n). A* then always expands the node with the smallest accumulated cost from the start — exactly what Dijkstra's algorithm does. The heuristic contributes nothing and the search expands uniformly in all directions, unguided by any estimate of where the goal lies. Setting g(n) = 0 instead would give greedy best-first search (option B), which chases the heuristic without accounting for cost already spent.

Question 3

A heuristic that is consistent (monotone) is also guaranteed to be admissible.

• T. True
• F. False

Answer: True

Consistency requires that h(n) ≤ cost(n, n') + h(n') for every edge from n to n'. This means h can never 'jump up' along any path in a way that would require overestimating the true cost to the goal. By induction from any goal node (where h = 0), a consistent heuristic can be shown to satisfy h(n) ≤ true cost to goal for all n — the definition of admissibility. Consistency is the stronger condition; every consistent heuristic is admissible, but not every admissible heuristic is consistent.

Question 4

A* with a perfect heuristic (h(n) equals the true remaining cost exactly) may still need to explore many nodes it doesn't ultimately include in the final path.

• T. True
• F. False

Answer: False

With a perfect heuristic, f(n) = g(n) + h*(n) = true total path cost through n. Every node on the optimal path has the same f value (the optimal path length), and every node NOT on the optimal path has a strictly higher f value. A* with a perfect heuristic expands only the nodes along the optimal path — zero wasted exploration. This is why heuristic quality matters so much: the closer h is to the true remaining cost (without exceeding it), the fewer nodes A* explores.

Question 5

What does it mean for a heuristic to be admissible, and why is admissibility the critical property that makes A* optimal rather than merely fast?

Model answer: An admissible heuristic never overestimates the true cost to reach the goal from any node: h(n) ≤ h*(n) for all n, where h*(n) is the true optimal remaining cost. Admissibility is critical because A* expands nodes in order of f(n) = g(n) + h(n). If h overestimates, a node on the true optimal path may appear to have a higher f value than a node on a suboptimal path, causing A* to commit to the cheaper-looking (but actually worse) route. Admissibility ensures this never happens: the true optimal path can never be made to look worse than a suboptimal alternative.

The intuition is a guarantee: if h never lies about the future cost, A* will never give up on a promising path too soon. Without admissibility, the heuristic can misdirect the search in ways that are impossible to detect without already knowing the optimal solution — defeating the purpose of using a heuristic at all.