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

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?

• 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? Apr 26, 2021 at 19:08

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

• 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. Apr 27, 2021 at 2:54
• @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.
– D.W.
Apr 27, 2021 at 4:45

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

• 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? Apr 27, 2021 at 18:55
• 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. Apr 27, 2021 at 19:49