I am having a really hard time with the "math" aseptic of heuristic functions. I day dreamed for 3 minutes today in my AI class and I missed the explanation. Can someone explain to me how I can calculate if a heuristic function is admissible? I posted this one ( Is h5 = (h1 + h2 + h3 ) / 3 admissible?) but honestly I it does not have to be this problem. I just understand better by example.
Also, I have the "AI: A modern approach" book with me, but I cannot find an example. If you know where I could find one, I would be grateful.
First, we recall that an heuristic function is is said to be admissible if it never overestimates the cost of reaching the goal. What this means?
In short it means that, if an heuristic function returns a value h for a state x there are no real solution with a lower cost of x. For instance, for pathfinding the euclidean distance between the current point and the destination is admissible because no path can be shorter to go in a straight line! In other word, an admissible heuristic is always optimistic.
Now, we can return to your question. We have three admissible heuristics h1, h2 and h3 and we want to find if the average of these three functions is admissible as well. Now we can call X(s) the best possible cost from a state s to the destination (in other word is the cost of the optimal solution). The value of X is obviously unknown but it will be useful.
Because h1, h2 and h3 are admissible we know that for any state s:
h1(s) < X(s) (remember: h1 never overestimates the optimal cost!)h2(s) < X(s)h3(s) < X(s)Then, because h5 is the average of the other three functions we know for sure that for each state it is bounded between min(h1(s),h2(s),h3(s)) and max(h1(s),h2(s),h3(s)). So we can say that for each state s:
h5(s) <= max(h1(s),h2(s),h3(s)) <= X(s)
And so also h5 is admissible.