Answers.Body: <p>The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, <code>x</code> and <code>y</code> 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 <em>overestimate</em> the distance. The travel-distance between two points can never be shorter than the straight-line distance (unless you start involving things like... teleportation).</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-28T08:52:07.207Z
Answers.LastActivityDate: 2018-07-28T08:52:07.207Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>The A* algorithm uses the "evaluation function" <span class="math-container">$f(n) = g(n) + h(n)$</span>, where </p>
  
  <ul>
  <li><span class="math-container">$g(n)$</span> = cost of the path from the start node to node <span class="math-container">$n$</span></li>
  <li><span class="math-container">$h(n)$</span> = estimated cost of the cheapest path from <span class="math-container">$n$</span> to the goal node</li>
  </ul>
  
  <p>But, in the following case (picture), how is the value of <span class="math-container">$h(n)$</span> calculated?</p>
  
  <p><a href="https://i.sstatic.net/Uago4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Uago4.png" alt="Image "></a></p>
  
  <p>In the picture, <span class="math-container">$h(n)$</span> is the straight-line distance from <span class="math-container">$n$</span> to the goal node. But how do we calculate it?</p>
  
Tags: <search><heuristics><a-star>
Title: How do you calculate the heuristic value in this specific case?
UserDisplayName: Surya Bhusal
ThreadText: # How do you calculate the heuristic value in this specific case?
  
  (Asked by: username_0 on 2018-07-28)
  
  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 ](https://i.sstatic.net/Uago4.png)](https://i.sstatic.net/Uago4.png)
  
  In the picture, $h(n)$ is the straight-line distance from $n$ to the goal node. But how do we calculate it?
  
  **Tags:** search, heuristics, a-star
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-07-28. Score: 2 | Accepted answer
  
  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.
  
  
  ---
  
  