DataTerminology.comNEW
A heuristic that never overestimates the true cost to reach a goal, ensuring optimality for A-star search.
DESCRIPTION
In search algorithms, an admissible heuristic h(n) is optimistic: it never exceeds the actual minimal remaining cost from n to a goal. A* with an admissible heuristic guarantees optimal solutions when other assumptions (e.g., nonnegative costs) hold. Many heuristics are constructed from relaxed versions of the problem to ensure admissibility. Consistency (monotonicity) is a stronger property that also simplifies implementation. Overly weak admissible heuristics slow search due to poor guidance.
ALTERNATIVE DEFINITIONS
Wikipedia
A heuristic is admissible if it never overestimates the cost of reaching the goal.
Concise statement emphasizing non-overestimation.
Artificial Intelligence: A Modern Approach
An admissible heuristic is one that is optimistic, in the sense that it never overestimates the cost to reach the goal.
Introduces the term ‘optimistic’ to intuitively explain the property.
RELATED TERMS
A-star Search Consistent Heuristic Heuristic Best-First Search Heuristic Search Shortest Path Graph Search
COMPETING TERMS
Inadmissible Heuristic
RELATIONS
- Broader: Heuristic
KNOWLEDGE AREAS
TARGET AUDIENCE
AI Engineer Data Scientist Software Developer
EXTERNAL SOURCES
- Wikipedia - Admissible heuristic
- AIMA (Russell & Norvig) - Canonical AI search textbook
- Amit Patel - Practical heuristics for A*
TOP QUESTIONS
Why use an Admissible Heuristic in A* search?
It guarantees optimal solutions while pruning the search space, balancing correctness and efficiency.
Category: Benefits
How to construct an Admissible Heuristic?
Use relaxed problem constraints or exact solutions on simplified versions (e.g., Manhattan distance in grids).
Category: Best practices
What is the difference between Admissible and Consistent heuristics?
Consistency implies admissibility and ensures non-decreasing f-values, simplifying A* implementation.
Category: Concepts
Can an Admissible Heuristic be uninformative?
Yes; h(n)=0 is admissible but reduces A* to Dijkstra’s algorithm, slowing search.
Category: Misunderstanding
What risks arise with non-admissible heuristics?
They may be faster but can yield suboptimal solutions, violating correctness guarantees.
Category: Risks
When to relax admissibility in practice?
When near-optimal solutions suffice and speed is critical; use weighted A* or inflated heuristics.
Category: Opinion
How to test admissibility empirically?
Verify h(n) ≤ true remaining cost for sampled states, using exact solutions on small instances.
Category: Testing
Where are Admissible Heuristics used?
Robotics path planning, puzzle solvers, and route navigation systems.
Category: Use cases
Do Admissible Heuristics guarantee speed?
No; they guarantee optimality, but informativeness determines speed improvements.
Category: Misunderstanding