Heuristic consistency definition for undirected graph

user_19677889 0
Viewed 28

In the A* path search algorithm the general definition for an consistent heuristic is h(m)<=h(n)+d(m,n) for any edge (m,n).

Is this true also for an undirected graph? In an undirected graph (m,n)=(n,m) and d(m,n)=d(n,m) and will also be true that h(n)<=h(m)+d(n,m), this means that h(n)=h(m) for all m and n. But this seams to be absurd.

Where am I doing wrong? Maybe in an undirected graph the consistency of a heuristic is h(m)<=h(n)+d(m,n) for m successor of n?

a-star heuristics algorithm
1 Answers

From what I understand, your reasoning is correct but your maths are not.

Yes, for an undirected graph you get two inequalities:

h(m) <= h(n) + d(m, n)

h(n) <= h(m) + d(m, n)

This does not imply that h(n) = h(m). If you flip the d term over in the latter, equation, you get

h(n) - d(m, n) <= h(m)

so you get

h(n) - d(m, n) <= h(n) + d(m, n)

so

-d(m, n) <= d(m, n).

The only way in which this implies h(n) = h(m) is if d(m, n) = 0.

user_105591420
Related