0
$\begingroup$

The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where

  • $g(n)$ = cost of the path from the start node to node $n$
  • $h(n)$ = estimated cost of the cheapest path from $n$ to the goal node

But, in the following case (picture), how is the value of $h(n)$ calculated?

Image

In the picture, $h(n)$ is the straight-line distance from $n$ to the goal node. But how do we calculate it?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.