Is an inadmissible heuristic forbidden?

No; suitability depends on the objective and guarantees required.

Can a heuristic be accurate but inadmissible?

Yes; accuracy and lower-bound validity differ.

Does inadmissibility alone prove incompleteness?

No; finding some solution and finding a cheapest solution are separate properties.

AI Glossary / Graphs and symbolic AI / Advanced

Inadmissible heuristic

Definition

An inadmissible heuristic is a search estimate that overestimates the true minimum remaining cost for at least one relevant state. It therefore lacks the never-overestimate property used in standard optimality arguments for A*. Such an estimate can still guide useful search, but it does not automatically support a claim that the first returned solution is cheapest.

What it means

A heuristic assigns a value h(n) to a state or search node. For a minimum-cost problem, let h-star(n) denote the actual cheapest remaining cost to a goal. Admissibility requires that the estimate not exceed that value. An overestimate at even one state breaks that property on the specified state space.
The distinction is about a bound, not average prediction quality. An estimate can be close to the truth on most examples yet overestimate occasionally. Conversely, a very conservative estimate may be admissible while providing weak guidance.
The label also does not mean every search result will be wrong. It means the relevant optimality guarantee cannot be obtained from admissibility of that heuristic.

How it works

A* orders its frontier by f(n) = g(n) + h(n), combining the cost already incurred with an estimate of the remaining cost. An exaggerated h-value can delay a node on the cheapest route until after a more expensive goal has been selected.
The consequence depends on the search procedure, including its stopping rule and treatment of cheaper paths to previously encountered states. Admissibility alone should not be used to justify every implementation labeled A*; graph-search details matter too.
Some algorithms deliberately trade exact optimality for other goals. Weighted A* uses g plus w times an admissible base heuristic, with w greater than 1. Under the algorithm's required conditions, a bounded-suboptimality result can limit returned cost to w times optimal cost. This does not give an arbitrary learned or hand-written overestimate the same guarantee.

Three practical examples

A route-search system predicts remaining travel cost using a learned model. Good average accuracy is useful evidence about prediction, but does not prove that predictions are lower bounds on every possible route state.
A game pathfinder emphasizes reaching a satisfactory destination quickly. Its designers may accept longer routes, provided evaluation measures both search effort and returned route cost under the intended workload.
A scheduling search assigns large penalties to states that look difficult. If those penalties are used as estimated remaining objective cost, they may overestimate and change which complete schedule is returned first.

Think of it this way

Imagine comparing two unfinished journeys after someone exaggerates the remaining distance on the shorter one. You may finish investigating the longer journey first. The estimate can change your search order without changing either journey's actual length.

Worked example

Consider a directed graph with exactly four edges: S to A costs 1, A to G costs 3, S to B costs 2, and B to G costs 5. S is the start and G the only goal. The route through A costs 4; the route through B costs 7.
Use A* that removes the smallest-f frontier node, stops when it removes a goal, and updates a frontier state's cost when a cheaper route is found. Set h(S) = 0, h(A) = 10, h(B) = 0, and h(G) = 0.
After expanding S, A has g = 1 and f = 11. B has g = 2 and f = 2. The algorithm selects B and discovers G with g = 7 and f = 7. G is selected before A, so the search returns cost 7 even though cost 4 is possible.
The cause is visible at A: its true remaining cost is 3, but its heuristic value is 10. The overestimate keeps the cheaper route waiting on the frontier. A correct goal test does not repair that ordering when the algorithm stops at the first removed goal.
For comparison, replace h(A) with 3. After B is expanded, A has f = 4 and G has f = 7. A is selected next, and its edge to G improves G's stored cost to 4. The returned solution is optimal.
Now use h(A) = 4 instead. This is still inadmissible because 4 exceeds the true remaining cost 3. Nevertheless, A's f-value is 5, which remains below the candidate goal's 7. A is expanded in time to improve G to 4, so this run also returns the optimal route.
The final variation demonstrates why inadmissibility means loss of a general guarantee, rather than inevitable failure on every instance.

Illustrative case study

Fictional Willow Routes evaluates a learned search estimate using average prediction error. Its product report then describes the returned routes as guaranteed cheapest.
A reviewer constructs the four-edge example and shows that an overestimate on one promising branch can change the result. The team separates its empirical accuracy measurements from its optimality claims.
Willow adds comparisons with exact solutions on manageable instances and reports returned cost alongside search effort. For any configuration claiming a mathematical quality bound, reviewers require the supporting algorithm assumptions and confirm that the implementation follows them.

Common misconceptions and mistakes

“Inadmissible means always suboptimal.” The h(A) = 4 variation disproves that.
“Low average error proves admissibility.” A single overestimate can violate the bound.
“Larger estimates always make search faster.” Search effort depends on the problem and ordering.
“An estimate of zero at the goal is enough.” Other states can still be overestimated.
“Weighted A* bounds apply to any heuristic.” The base heuristic and algorithm must meet the required conditions.

Business use

Decide whether the application requires exact optimality, a proven cost bound, or acceptable empirical results within a time budget. Record which of these is actually supported.
Measure solution cost, elapsed time, and search effort together. Use known-optimum examples where available, including cases designed to expose overestimates on promising branches. Passing a finite test collection does not establish a universal lower-bound property across an unrestricted state space.

Check your understanding

Why is h(A) = 10 inadmissible?

Answer: The remaining cost from A is only 3.

Why does the first run return 7?

Answer: Its goal is removed before A.

Why does h(A) = 4 still succeed here?

Answer: A's priority remains below the cost-7 goal.

Related terms

Admissible heuristic
Consistency
Frontier
A*
weighted A*
optimality
bounded suboptimality

Learn next

Trace the example while changing h(A). Identify the threshold at which tie-breaking becomes relevant, then distinguish that instance-specific observation from a general optimality theorem.

Sources

AIMA glossary, inadmissible heuristic: https://github.com/aimacode/aima-glossary/blob/master/glossary.md UC Berkeley CS188, informed search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/informed.html A*-Connect research paper, weighted and multi-heuristic search background: https://www.cs.cmu.edu/afs/cs/Web/People/maxim/files/astarconnect_icra16.pdf

Previous: In-set condition Next: Inauthentic text