Home Ask Login Register

Developers Planet

Your answer is one click away!

Algo February 2016

Admissible heuristic function

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?

Thanks

Answers


Johnny HD February 2016

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,

Post Status

Asked in February 2016
Viewed 3,666 times
Voted 6
Answered 1 times

Search




Leave an answer


Quote of the day: live life