Admissible heuristic
term_id: admissible_heuristic
Category: basic_concepts
Definition
In pathfinding and search problems, an admissible heuristic provides a lower bound on the actual cost to reach the target node. By guaranteeing that the estimated cost is always less than or equal to the real cost, algorithms like A* can ensure they find the shortest path if one exists. This property is critical for maintaining solution optimality while still leveraging heuristics to prune the search space efficiently, balancing speed and accuracy in complex graph traversals.
Summary
A heuristic function in search algorithms that never overestimates the true cost to reach the goal, ensuring optimality.
Key Concepts
- Lower bound
- Optimality guarantee
- A* search
- Cost estimation
Use Cases
- GPS navigation route planning
- Puzzle solving (e.g., 8-puzzle)
- Robot motion planning in obstacle-rich environments