A heuristic function bounded above by the minimum remaining goal cost . When no goal is reachable, take . Admissibility is a lower-bound guarantee, rather than a statement that the estimate is usually numerically accurate. Ignoring constraints can produce a relaxation heuristic because it enlarges the available solution set.
If , their pointwise minimum, pointwise maximum and each convex combination with are admissible heuristics. Each inequality follows directly by comparison with . The maximum has heuristic dominance over the minimum and every such convex combination.
A sum need not be an admissible heuristic: two exact estimates of the same cost-one remaining action sum to two. A sufficient condition for a valid additive construction is separate nonnegative action-cost allocations with , and estimates bounded by the corresponding optimal allocated costs. Every goal-reaching graph path then costs at least under its original costs. Taking the minimum proves admissibility without counting the same work twice.
If are consistent heuristics, their maximum, minimum and fixed convex combinations are also consistent heuristics. For the maximum, choose an index attaining it at the source and bound its successor by the successor maximum. For the minimum, choose an index attaining it at the successor and bound the source minimum by that component. For a convex combination, multiply the two consistency inequalities by their nonnegative weights and add them. All these combinations vanish at goals when the inputs do.
Articles by others on the same topic
In the context of an A* search, a heuristic function is said to be admissible if it does not overestimate the cost to reach the goal. Such functions can also be viewed as being "optimistic".
When using an admissible heuristic, A* is guaranteed to return a cost-optimal solution, i.e. the best path. Let's prove it by contradiction:
Assume that the algorithm returned a path, the cost of which is greater than that of the optimal path . Let's call the cost of the path that was followed, and the cost of , noting that . First, we can safely assume that at least one node in was not expanded during the algorithm's execution (if all nodes of were expanded, then would have been chosen instead since that would lead to a lower path cost). Without loss of generallity, let's take the first occurance of such unexpanded node and name it "n". Let's call the actual cost from n to the destination and define as the cost of the optimal path starting from the origin all the way to n. Remember that A* is a best-first search on the value of , so for all unexpanded nodes. Here's what we've got:
Now note that is equal to "the cost to reach n following the optimal path" + "the cost to reach the goal starting from n, following the optimal path". That's just equal to the total cost of the optimal path! So, both and hold simultaneously which obviously constitutes a contradiction.
[1]: Remember than (our heuristic) is just a hint to prioritize certain expansions over others. When everything is expanded however, is the sole metric that will be considered, which will always lead to the optimal path being selected, that being .