How to prove heuristic compatibility can be a valid heuristic in the A * search algorithm
a compatible heuristic (h) is one that has the following conditions:
h (n) <= c (n, a, n ') + h (n')
****************************************************
a valid heuristic (h) is one that has the condition below:
0 <= h (n) <= h * (n)
h * (n) - actual distance from node n
togoal
If a heuristic is compatible, how can you prove it is valid?
Many thanks.
source to share
Suppose that h (n) is invalid, so there is some vertex n such that h (n)> h * (n).
But due to the compatibility of h (n), we know that for all n`, h (n) <= c (n, a, n ') + h (n').
Now let us combine these two predicates when n 'is a vertex of G to deduce a contradiction, thereby proving the required reduction lemma ad absurdum.
source to share
If you add an extra condition on h (namely, h (target) = 0), you can prove it by induction on the minimum cost path from n to the target state.
For the base case, the minimum cost path is 0 when n = target. Then h (target) = 0 = h * (target).
In general, let n be a node and n 'be the next node on the minimum path from n to the target. Then h * (n) = c (n, n ') + h * (n')> = c (n, n ') + h (n')> = h (n), using the induction hypothesis to get the first inequality and definition of compatibility for the second.
source to share