Admissible heuristic
An admissible heuristic is a heuristic that never overestimates the minimum cost of reaching a goal from a given state.
Optimization Algorithms: AI techniques for design, planning, and control problems
An admissible heuristic estimates remaining cost without exceeding the true minimum remaining cost.
- How it is used
- Guides A* route search toward promising nodes and supports search-space pruning in hierarchical routing.
- How deep it goes
- Defines the lower-bound condition and works through A* routing choices, but does not prove admissibility for a particular cost model.
- Examples
- Uses an eight-point road network, straight-line distances to the goal and a Python A* routing listing.
- What you can do after
- Build it from scratch in Python using NetworkX and optalgotools nodes, supplying heuristic and edge-cost functions for routing.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
An admissible heuristic is a heuristic that never overestimates the cost of reaching the goal.
- How it is used
- Guides A* maze search toward a shortest path while preserving its optimal-path guarantee.
- How deep it goes
- Defines the no-overestimation rule and implements distance estimates, but defers a proof of optimality.
- Examples
- Uses a four-direction grid maze and Swift functions for Euclidean and Manhattan distance.
- What you can do after
- Apply it via A* search by supplying a distance heuristic that does not overestimate remaining maze cost.
Advanced Algorithms and Data Structures
An admissible heuristic is a heuristic that never overestimates the cost of reaching a goal from a given state.
- How it is used
- Guides A* toward promising goal paths while preserving optimality when paired with consistency.
- How deep it goes
- Defines optimism, contrasts consistency, and notes tree sufficiency without developing a formal proof.
- Examples
- Uses delivery routing, straight-line distance, and an inflated vertex estimate that produces a non-optimal A* path.
- What you can do after
- Apply it via A* by checking that a heuristic does not overestimate and, for graphs, is also consistent.
Read how Advanced Algorithms and Data Structures explains admissible heuristic →
Related concepts
- A-star algorithmconfigures · A* is an informed graph-search algorithm that prioritizes paths or states by combining the cost incurred so far with a heuristic estimate of the remaining cost to a goal.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.