1
$\begingroup$

The A*-Algorithm helps you find the optimal route from point A to B on a given graph plane. Let's say that I have the following problem where I have to go from Köln to Karlsruhe.

enter image description here

Without actually writing an algorithm, I tried to find the optimal route by finding the minimum distance from point A to B. I went from Köln to Frankfurt to Kaiserlautern to Ludwigshafen to Karlsruhe, where the total distance ends up being $912$ units. The quesion then asks that if a hypothetical algorithm was designed, which cities would it check? I think it should check all cities that're connected directly to the starting city (and then the cities that're on the optimal route), so Metz, Saarbrücken and Frankfurt. My answer is correct except for Metz which is not a city that the algorithm would "visit"?

So I have $3$ questions:

  1. Why would Metz not be correct?
  2. Is my distance value correct?
  3. What does the $h$-value tell us?

P.S. - I know this is basic theoretical CS stuff but I'm just in my first semester so please have mercy. :)

$\endgroup$
5
  • $\begingroup$ 3. There is more than $1$ answer what $h$ could be. $\endgroup$ Mar 9, 2018 at 13:36
  • $\begingroup$ @DietrichBurde but what does the $h$-value tell us? $\endgroup$
    – Ski Mask
    Mar 9, 2018 at 13:37
  • $\begingroup$ This is not clear from the context, and thus an ill-posed question. $\endgroup$ Mar 9, 2018 at 13:38
  • $\begingroup$ Do you know what the A* algorithm is and how it works? How did you find the Köln-Frankfurt-Kaiserlautern-Ludwigshafen-Karlsruhe route? $\endgroup$
    – user856
    Mar 9, 2018 at 13:43
  • $\begingroup$ @Rahul A* Algorithm is designed to solve a problem by finding out all the possible solutions and choosing the one that has the minimum cost, be it shortest time or distance. As for how it works, I'm a bit iffy on that - especially the formula that is used $f(n)=g(n)+h(n)$. I don't actually have to write an algorithm, only use the idea of it to find the least costly route. $\endgroup$
    – Ski Mask
    Mar 9, 2018 at 13:48

2 Answers 2

1
$\begingroup$
  • The A* algorithm uses actual distances between neighbors, along with estimated distances ($h$ values), to find the shortest path. If the estimates are good, A* is guaranteed to find the shortest path.

  • By hand, you found the shortest path between Köln to Karlsruhe. Given good estimates, A* is guaranteed to find that path (or another path of equal length). The length of your path is 430, which you can compute by adding up the lengths of the roads between cities. I believe you've added in $h$ values by mistake, but $h$ values do not affect length. They are used to guide search, but they are not included when you compute path lengths. (I explain $h$ values below.)

  • The main thing to know about A* is that it maintains a list of partial paths, and that it decides which path to consider (extend) next based on estimated total path length to the goal.

    Estimated total path length is the length of the path so far, plus the estimated distance remaining to the goal. The $h$ values tell you the estimated distance from each city to the goal.

  • Initially, A* will compute estimated total path length from Köln to its neighbors to Karlsruhe. Those estimates are:

    • Köln-Frankfurt 190 + 125 = 315
    • Köln-Saarbrücken 260 + 105 = 365
    • Köln-Metz 290 + 162 = 452
  • So naturally A* explores paths from Köln through Frankfurt, first. If the estimates are good, then paths with the smallest estimated total length will tend to have the smallest actual length when they reach the goal.

  • Next, A* computes costs for Köln-Frankfurt-Koblenz and the other neighbors. It also remembers the other paths it has computed: Köln-Saarbrücken and Köln-Metz. It will consider whichever of the paths has the shortest length among paths it has computed.
  • The reason A* never visits Metz is because the path to Köln-Metz never has the shortest estimated path length. You can see this by computing the estimated path lengths of the true shortest path:

    Köln-Frankfurt, Köln-Frankfurt-Kaiserlautern, Köln-Frankfurt-Kaiserlautern-Ludwigshafen, Köln-Frankfurt-Kaiserlautern-Ludwigshafen-Karlsruhe

    All of these have lower estimates than Köln-Metz, so the goal will be found before Köln-Metz will be visited.

$\endgroup$
3
  • $\begingroup$ Then why does the algorithm check the city of Saarbrücken? $\endgroup$
    – Ski Mask
    Mar 19, 2018 at 11:42
  • $\begingroup$ A* is guaranteed to find the shortest path, so it's required to explore anything that has a lower cost than the current path it's looking at. The path Köln-Frankfurt-Kaiserlautern has estimated length 366, while Köln-Saarbrücken has estimated length 365, and must be explored first. Köln-Metz at 452 will never need to be checked before the goal is found (shortest path: 430 < 452). $\endgroup$
    – user326210
    Mar 19, 2018 at 18:19
  • $\begingroup$ Rule: You visit any city that can be reached by a path with an estimated total path length less than the real shortest path length between the start and the goal. You don't visit any other cities. $\endgroup$
    – user326210
    Mar 19, 2018 at 18:24
1
$\begingroup$

The $h$-values are reasonable lower bounds for the distance to the final destinations. (The canonical example is distance measured along a straight line.) You do not include the $h$-values in the total cost, so the answer to your question 2 is no, your distance value is not correct. You get the actual total distance by adding together the distances between successive cities along your chosen path. The $g$-values are updated during the algorithm, and at each step, they are the shortest distances from the starting point found so far. So, once the value of $g(n)$ has been found, the value $f(n)=g(n)+h(n)$ is a lower bound for the total cost of a path going through node $n$. At each step of the algorithm, you "check" the node which has the smallest $f$-value among the nodes that haven't been checked yet. Checking a node means updating the $g$-values of its neighbors. When the destination is checked, the algorithm finishes. Metz is never checked because its $f$-value is larger than the cost of the optimal path, which equals the $f$-value of the destination.

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