What isAdmissible Heuristic
A heuristic function in a search algorithm that never overestimates the cost to reach the goal from the current state. This ensures that the search will find the optimal solution.
An admissible heuristic is a crucial component in search algorithms, particularly those employing informed search strategies. It provides a way to estimate the cost of reaching the goal state from any given state without overestimating the actual cost.
Crucially, an admissible heuristic never overestimates the true cost. This property is essential because it guarantees that the search algorithm will find the optimal solution. If an overestimate is present, the algorithm might incorrectly discard paths that could lead to the optimal solution.
This characteristic is fundamental to the success of algorithms like A* search, which leverages heuristic functions to guide its search process. Without admissibility, the algorithm might get trapped in suboptimal branches.
Example
Consider a map with distances between cities. A heuristic function that estimates the distance between two cities using a straight-line distance (ignoring roads) is admissible if the actual distance along the road is never shorter than the straight-line distance.