I know that an admissible heuristic function underestimates the actual cost to a goal, but I want to conclude that a heuristic function h3 which is sum of two admissible heuristic functions(h1 and h2) can both be admissible and not if no further information on h1 and h2 is given.
Do you think that is the right claim?
An admissible heuristic is one that never overestimates the cost of the minimum cost path from a node to the goal node. So, a heuristic is specific to a particular state space, and also to a particular goal state in that state space. It must be admissible for all states in that search space.
To help remember whether it is “never overestimates” or “never underestimates”, just remember that an admissible heuristic is too optimistic. It will lead A* to search paths that turn out to be more costly that the optimal path. It will not prevent A* from expanding a node that is on the optimal path by producing a heuristic h value that is too high.
A stronger requirement on a heuristic is that it is consistent, sometimes called monotonic. A heuristic h is consistent if its value is nondecreasing along a path. Mathematically, a heuristic h is consistent if for every node n of a parent node p,
Asked in February 2016Viewed 3,666 timesVoted 6Answered 1 times