Admissible Heuristic
The short answer · 19 words
In short
An admissible heuristic is a search heuristic that never overestimates the actual minimum remaining costs up to the target.
Flow-alerta.cab (2026): Admissible Heuristic. https://flow-alerta.cab/en/glossar/admissible-heuristic. Editorially reviewed on: 09 October 2026.
How much detail would you like?
Practical
Relevant for optimal path and planning search. An informative permissible heuristic can reduce search effort; usefulness and correctness depend on procedures and prerequisites.
Possible example: In a route planning, the airline distance may be a permissible heuristic if the actual travel costs correspond at least to the corresponding distance metric.
Possible applications: applicable to route, sequence and planning problems when state spaces are explicitly searched. In business processes, it must first be checked whether classic optimization methods are more suitable.
At a glance
- Core
- For a permissible heuristic, h(n)≦h*(n), i.e. no overestimation of the optimal remaining costs. Optimality statements for A* require additional prerequisites for search space, costs and implementation; in particular, the treatment of already visited states must be correct.
- Use
- Relevant for optimal path and planning search. An informative permissible heuristic can reduce search effort; usefulness and correctness depend on procedures and prerequisites.
- Example
- Possible example: In a route planning, the airline distance may be a permissible heuristic if the actual travel costs correspond at least to the corresponding distance metric.
- Limits
- Equate permissibility with consistency; use a heuristic that can overestimate residual costs; make optimality statements without prerequisites; ignore computational costs of the heuristic itself.
Questions about this term
What does admissible mean?
The heuristics do not overestimate the optimal remaining costs.
Is every permissible heuristic consistent?
No, permissibility and consistency are different characteristics.
All details and background
For a permissible heuristic, h(n)≦h*(n), i.e. no overestimation of the optimal remaining costs. Optimality statements for A* require additional prerequisites for search space, costs and implementation; in particular, the treatment of already visited states must be correct.
ELI5 – Explained simply
Like a path estimate that is at most as long as the really shortest remaining path – it must be too optimistic, but not above it.
Why it matters in practice
Relevant for optimal path and planning search. An informative permissible heuristic can reduce search effort; usefulness and correctness depend on procedures and prerequisites.
Example
Possible example: In a route planning, the airline distance may be a permissible heuristic if the actual travel costs correspond at least to the corresponding distance metric.
Pitfalls and limits
- Equate permissibility with consistency; use a heuristic that can overestimate residual costs; make optimality statements without prerequisites; ignore computational costs of the heuristic itself.
Origin & history
In 1968, Hart, Nilsson and Raphael described in A Formal Basis for the Heuristic Determination of Minimum Cost Paths the formal foundations of the A* procedure and conditions for optimal path search.
Use in mid-sized companies
- Possible applications: applicable to route, sequence and planning problems when state spaces are explicitly searched. In business processes, it must first be checked whether classic optimization methods are more suitable.
Related terms
- Heuristics
- Pathfinding
- Designing
Matching Flow-alerta service
AI opportunity analysis & roadmapAI potential analysis & roadmap: clarify tasks and prerequisites of a possible automation case.Matching tool / use case
View use casesPossible use: A* search with suitable residual cost estimate and tested prerequisites; select specific implementation separately.Sources
- artint.infoPoole & Mackworth, Informed (Heuristic) Search
- ieeexplore.ieee.orgHart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Quellenprüfung: 09.10.2026. Anwendungsbeispiele sind mögliche Szenarien, keine behaupteten Kundenfälle.
Editorially reviewed on: