Intermediate · Research
Admissible heuristic
Visual diagram · (in preparation) · Math · (in preparation) · Worked example · 3 difficulty levels.
TL;DR. An admissible heuristic never overestimates the cost to reach a goal, ensuring optimal pathfinding.
Technical Definition
An admissible heuristic never overestimates the cost to reach a goal, ensuring optimal pathfinding.
How it works
In search algorithms like A*, an admissible heuristic provides an optimistic estimate of the cost to reach the target. This property is crucial because it guarantees that the algorithm will find the shortest possible path if one exists. It's a key concept in informed search strategies.
Related Concepts
- A* search — A* search is a pathfinding algorithm that finds the shortest path between two points in a graph.
- Pathfinding — The process of automatically determining the shortest or most efficient route between two points, often in a graph or map.