Should your heuristic for an A* search algorithm be the same scale as your actual weights?

Question

I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the path to node $n$ from the source node. $h(n)$ is a heuristic function that estimates the cost of the cheapest path from n to the goal. (Roughly summarised from the wikipedia article on A*)

My question is should $h$ and $g$ be on the same scale? e.g. if g(n) to node n is 10 is it ok if the h(n) is 800?

I've read some conflicting takes on it where one example of using A* for plane routes had $g$ values in the range of 10-50 but $h$ values in the range 100 - 900 but elsewhere I read that they should be the same scale to avoid changing an A* search into a greedy best first search?

Answer 1

They can't possibly be on the same scale throughout the search, if by that you mean that $g(n) \approx h(n)$ for every node encountered near the search. Near the start, you'll have $g(n) \approx 0$, so $g(n) \ll h(n)$. Near the goal node, you'll likely have $h(n) \approx 0$, so $h(n) \ll g(n)$.

On the other hand, it is possible to have the range of values for $g$ (min across all nodes, to max across all nodes) to be similar to the range of values for $h$ (min across all nodes, to max across all nodes). That is a good property. In particular, the range of $g(n)$ will be from 0 to the distance to the goal; if $h(n)$ is perfect (exactly accurate), it will have the same range.

If $h(n) \ll g(n)$ throughout the search (i.e., for all nodes $n$), then the search becomes similar to Dijkstra's algorithm (in particular, if $h(n)=0$ everywhere, then it is devolves to exactly Dijkstra's algorithm).

If $g(n) \ll h(n)$ throughout the search (i.e., for all nodes $n$), then the search becomes similar to a greedy best first search using only $h(n)$ (in particular, if $g(n)=0$ everywhere, it devolves to exactly greedy best first).

Answer 2

I think you might have misunderstood the heuristic function. It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$. The closer this estimate is to the true value, the better A* will perform.

The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $n$ to $t$.

Let $\text{dist}(a, b)$ be the "true" distance from $a$ to $b$, and let $\text{dist}_0(a,b)$ be an underestimate (e.g. the Euclidean distance from $a$ to $b$ if you have a map).

If you are searching for a path from $s$ to $t$, then $g(n)$ is defined to be $\text{dist}(s, n)$, whereas $h(n)$ is $\text{dist}_0(n, t)$. So $$ \text{dist}(s, n) + \text{dist}_0(n, t) = g(n) + h(n) = f(n).$$

There is nothing about scale of $g(n)$ and $h(n)$, except that $h(n)$ must give a lower value than (or equal to) the true distance from $n$ to $t$.