An Admissible Heuristic
An admissible heuristic is a concept in computer science that refers to a heuristic function that never overestimates the cost of reaching the goal. The cost it estimates to reach the goal is not higher than the lowest possible cost from the current state.
Areas of application
- pathfinding algorithms
- artificial intelligence
- machine learning
- decision making
- optimization problems
Example
For example, in a pathfinding algorithm, an admissible heuristic might be used to estimate the cost of reaching a goal node from a given starting node. If the heuristic function overestimates the cost, the algorithm may choose a suboptimal path to reach the goal, resulting in longer search time and less efficient use of resources. An admissible heuristic ensures that this does not happen, as it never overestimates the cost and always provides an accurate estimate.