Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where
But, in the following case (picture), how is the value of $h(n)$ calculated?
In the picture, $h(n)$ is the straight-line distance from $n$ to the goal node. But how do we calculate it?
The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y coordinates for all the nodes in your graph, that would be extremely easy to compute. The straight-line distance also fits the requirements of an admissible heuristic, in that it will never overestimate the distance. The travel-distance between two points can never be shorter than the straight-line distance (unless you start involving things like... teleportation).
From an image like that, the straight-line distance might be difficult to figure out yourself, which is probably why they gave you the straight-line distances on the right-hand side of the image. If the image is perfectly consistent, I suppose you could theoretically figure out by inspecting some of the roads in detail how much distance is covered per pixel. Then, you can also figure out how many pixels the figure has along the straight-line paths you're interested in, and compute the straight-line distances yourself. I have no idea if the figure was actually drawn in a 100% consistent manner though.
