1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What does "scale" mean exactly? For example if g is in kilometers and h is in meters, that's obviously wrong. Or are we just eyeballing the magnitudes of the values? $\endgroup$ – harold Apr 26 at 19:08
1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ I'm a bit unclearly on the first line of your answer. Perhaps I'm using the incorrect term but if your weights and heuristics are in the range of, say 1-10 for all nodes whether at near the source (where g may be 1 and h 10) or near the target (where now g may be 1 and h may be 10) arent they the same scale? The second sentence makes it clearer, so if I was graphing a flight network where the weights were the price of a flight the euclidean distance between airports would be a bat heuristic. $\endgroup$ – July Jones Apr 27 at 2:54
  • $\begingroup$ @JulyJones, Good point. Please see the updated answer. There are multiple possible meanings for what "same scale" might be; I now try to address all of them in my revised answer. $\endgroup$ – D.W. Apr 27 at 4:45
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Perhaps I am misunderstanding, when you talk about the "true value" are you talking about the sum of the edges between two points? So wouldnt that necessitate h and g being on the same "scale" or at least be measuring the same thing even if in abstract? e.g. if the weight of the edges correlates to price in a range 1-10 and the heuristic is a measure of the euclidean distance in a range 1000-10000 wouldnt that fuck it up? $\endgroup$ – July Jones Apr 27 at 18:55
  • $\begingroup$ Correct, you could say that they need to be in the same scale, although to be completely sure, I would need a formal definition. But the only important thing is that $h(n)$ is a lower bound on the "true value". I.e. $h(n)$ needs to be smaller than the sum of edges, as you say, from $n$ to goal. $\endgroup$ – Pål GD Apr 27 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.