A* Interview Questions: Admissible Heuristics, Reopening Nodes, and Optimality

Your A* heuristic never overestimates the remaining cost. You mark each expanded node permanently closed, return a route, and still miss a cheaper answer. The estimate can be admissible while the implementation discards the improvement that optimality requires.

A* interview questions need three explanations together: the heuristic's bound, the handling of better paths to a known state, and the stopping rule. Writing f = g + h establishes the priority expression. It does not settle those other conditions.

The technical reference facts below come from Berkeley CS188, Poole and Mackworth's textbook, and official library documentation, checked September 30, 2026. All numbered graphs, traces and checks are original. Preparation recommendations are inference; no candidate reports establish an employer's question frequency or interview format.

Define the moves and cost model before choosing a heuristic.

What do admissibility, g, h and f mean?

Reference fact: Berkeley describes g(n) as the cost accumulated to the current node, h(n) as an estimate of the remaining goal cost, and f(n) = g(n) + h(n) as the frontier priority. Its admissibility definition requires 0 ≤ h(n) ≤ h*(n), where h* is the true least remaining cost. CS188 informed search

In the examples here, the graph is finite, edge costs are nonnegative, the heuristic is fixed for each complete state, and the goal's heuristic is zero. g is the best discovered cost, which may improve; it is not automatically the true shortest cost when the state first appears.

An estimate of zero is admissible under these assumptions. It provides no goal-directed advantage and reduces the priority to accumulated cost. An estimate that looks geographically plausible still needs a lower-bound argument in the problem's actual units.

For an original dimensional check, suppose edges measure travel time. A straight-line distance in kilometers cannot be added directly to g in seconds. A justified optimistic time estimate would require a compatible speed bound and the stated movement model. Better-looking numbers are not evidence of a valid heuristic.

How is consistency stronger than admissibility?

Reference fact: Poole and Mackworth explain the monotone restriction h(u) ≤ cost(u,v) + h(v) on each edge. With the appropriate goal condition, this consistency property supports pruning later paths to an already expanded state without losing an optimum. Multiple-path pruning and consistency

For an original derivation, moving along an edge gives:

new_f = g(u) + cost(u,v) + h(v)
old_f = g(u) + h(u)
consistency implies new_f ≥ old_f

This local condition controls how estimates change across neighboring states. Admissibility instead compares an estimate with the true remaining optimum. A heuristic can obey the second bound while violating the first inequality.

Use precise verbs. “Discovered” means a path has generated a state. “Expanded” means a current frontier entry was selected and its outgoing transitions examined. Even consistency does not justify permanently rejecting every alternative immediately upon discovery. A cheaper path can arrive before the state's first expansion.

If you cannot establish consistency, retain improvements and permit a state to be expanded again after a cheaper path is found. Explain that policy explicitly instead of relying on a generic visited set.

Can admissible A* really need to reopen a node?

Consider this original directed graph:

S → A: 3       A → G: 3
S → B: 1       B → A: 1
               B → G: 100

Choose these fixed heuristic values:

State	h	True remaining cost
S	0	5
A	0	3
B	4	4
G	0	0

Every estimate is admissible. However, B→A violates consistency: 4 > 1 + 0. Starting from S creates A with g=3,f=3 and B with g=1,f=5. A is expanded first, creating G with cost 6.

B is then selected before G because 5 is less than 6. B finds a route to A with cost 2. If A is permanently closed, that improvement is discarded. The implementation eventually returns S→A→G, cost 6.

With reopening, update A to g=2,f=2 and push a fresh frontier entry. Expand A again, improving G to cost 5. The selected route is S→B→A→G, cost 5. Notice that the expansion priorities decrease from B's 5 to A's 2; that is compatible with this inconsistent heuristic.

Our original Python fixture executes both variants. Permanent closure returns 6; reopening returns 5, with expansion sequence S, A, B, A, G. A separate Bellman–Ford calculation confirms the optimum. These are local algorithm checks, not a claim about a deployed pathfinding service.

Reference boundary: Berkeley also explains that graph search must account for a cheaper path to an already reached state. The original numbers above were constructed for this article rather than copied from its example. CS188 graph-search discussion

Why should the goal be selected rather than merely generated?

Use this second original counterexample, with all heuristic values zero:

S → G: 10
S → B: 1
B → G: 1

Expanding S generates G at cost 10. Stopping immediately returns the expensive route before B has been examined. Leaving both entries in the frontier permits B's cost-one expansion and improves G to cost 2. The current goal entry then selected from the frontier has the optimal cost.

For an original optimality argument, let C* be an optimal route cost. With admissible estimates and better paths retained, an unfinished prefix of that route provides a frontier bound no greater than C*. A suboptimal goal has f=g>C* because its heuristic is zero. It cannot be the next minimum-priority valid entry while that cheaper route's prefix remains available.

The argument depends on retaining the relevant prefix. Discarding improved states, using an overestimating heuristic or changing the graph during the run can invalidate it. Reject stale queue entries before interpreting them as current goal candidates.

Reference scope: Poole and Mackworth state sufficient completeness conditions for their search formulation, including bounded branching and edge costs bounded above zero by a positive lower bound. Our fixtures use a finite stored graph and strict cost improvements, so their zero-cost-cycle check is a narrower implementation case, not a claim of completeness for arbitrary infinite spaces. A* assumptions and proof

What state does a correct heap-based implementation retain?

Our original implementation stores best discovered g by state, predecessor links, and heap entries containing (f, serial, queued_g, state). A popped entry whose queued cost differs from the current best cost is obsolete. Skip it, then test whether a current entry is the goal.

For every successor, compute candidate_g = current_g + edge_cost. Only a strict improvement replaces its best cost and predecessor and inserts a fresh entry. The reopening variant has no rule forbidding this insertion merely because the state was expanded earlier.

Official implementation advice: Python's documented priority-queue pattern uses a unique entry counter to avoid comparing task objects when priorities tie. Python heapq priority queues

That counter is useful when states are tuples, objects or mixed identifiers without a shared ordering. Tie behavior can change which optimal route is returned, so compare cost and validity unless the output contract specifies a particular route.

The strict-improvement rule also prevents repeated equal-cost insertion around a zero-cost cycle in our finite examples. Validate the nonnegative-cost contract at the boundary. Applying this implementation unchanged to negative edges abandons the reasoning used here.

Reconstruction needs the same full state identities as cost storage. Do not repair a missing path by following arbitrary parent pointers. Check that the returned transitions exist and that their costs sum to the returned objective.

How should you derive and challenge a heuristic?

Reference principle: solving a relaxed problem supplies a lower bound when every legal solution of the original remains available in the relaxation at no greater cost. Poole and Mackworth discuss constructing heuristics through simpler problems. Heuristic construction

For an original grid check, Manhattan distance is an admissible bound for four-direction moves of unit cost: removing walls gives the optimistic number of horizontal and vertical steps. Walls can increase the actual distance; they do not create a shorter permitted move.

Change the moves, and the argument changes. From (0,0) to (1,1), Manhattan distance is 2. If a diagonal move costs 1, the true route costs 1, so the old estimate overstates it. This tiny counterexample exposes the contract failure before a large maze hides it.

If every orthogonal move costs at least c, scaling Manhattan distance by c can support a cost bound for that model. A zero minimum gives a valid but potentially uninformative zero bound. Teleports, discounted edges and time-dependent transitions need separate consideration.

Adding two valid lower bounds can double-count the same necessary work. Taking their maximum preserves a lower bound when both estimate the same remaining objective. Use an addition only after proving that the underlying obligations or costs are separable.

Official library limitation: NetworkX warns that an inadmissible heuristic may produce a non-shortest path and that its API caches the first heuristic calculation for a node, so it does not support changing that node's heuristic during a run. NetworkX astar_path

When is a location insufficient as the search state?

For an original key-and-door exercise, arrival at location X without a key costs zero; arrival at X with a key costs one. Only the keyed state can take a cost-one transition to G. The valid route therefore costs two.

If the visited map stores only X, the cheap unkeyed arrival can suppress the useful keyed arrival. Store (location, has_key) instead. Our local fixture finds cost two using these distinct states. Obstacle-removal budgets, battery levels and time slots can create the same modeling issue.

A heuristic may deliberately ignore the key to form a relaxation. The search's identity map cannot ignore it when it changes legal successors. State equivalence and heuristic abstraction serve different purposes.

What evidence establishes correctness and useful performance?

Our original reopening implementation matches an independent Bellman–Ford oracle on 200 seeded six-vertex graphs with nonnegative integer costs and randomly chosen admissible estimates. A zero-heuristic run matches the same oracle. Separate checks cover unreachable goals, start equal to goal, zero-cost cycles, the key state and both worked counterexamples.

The harness checks route endpoints and recomputes returned transition costs. It does not execute NetworkX, prove every input correct or measure production latency. A deliberate permanent-closure failure is retained as evidence that the main fixture distinguishes implementations.

For performance, measure expanded states, re-expansions, heap entries, peak memory and heuristic computation time on representative inputs. A more informative bound can cost more to compute. Do not claim A* is universally faster than uniform-cost search from one successful maze.

Multiplying h by a factor above one can destroy admissibility. If proposing weighted A*, state the changed objective and prove any approximation guarantee under its own assumptions. Do not attach the ordinary optimality argument to an altered priority expression.

Practice the state and bound together

The A* follow-ups are original extensions, not predictions of an employer's exact round.

Question	A* follow-up
Shortest Path in a Grid with Blocked Cells	Derive the bound from permitted moves
Shortest Path in a Grid with Limited Obstacle Removal	Preserve remaining budget in the state
Explore an Unknown Grid and Return a Robot Path	Separate graph discovery from a fixed-graph search
Find optimal commute mode in a city graph	Keep travel-time estimates in the correct units
Shortest Distance in an Unweighted Adjacency-Matrix Graph	Explain when simpler BFS is sufficient

Return to the blocked-grid exercise. Explain the full state, one heuristic proof and the cost-six versus cost-five reopening trace.

Sources and Further Reading

• Berkeley CS188: informed search, admissibility and graph search
• Poole and Mackworth: A* assumptions and heuristic construction
• Poole and Mackworth: multiple-path pruning and consistency
• NetworkX astar_path API and heuristic limitations
• Python heapq documentation: priority-queue implementation notes