3
$\begingroup$

An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter?

Say we have optimal path A (cost 100 to reach goal) and sub-optimal path Z (cost 120 to reach goal). Even if the heuristic is admissible, say it gives A a heuristic of cost 99 while it gives Z a heuristic of cost 10.

In both cases, the heuristic is admissible since it's lower than the actual cost it'll take to reach the goal, but still under this, Z is optimal since the heuristic gives a cost of 10 to Z and a cost of 99 to A.

It seems to me then it doesn't even matter that the heuristic is admissible. You still get the suboptimal solution.

What am I missing?

Improve this question
$\endgroup$
2
  • $\begingroup$ Eh, sorry, I see two answers now. Does that mean this is on topic here? $\endgroup$
    – Maarten Bodewes
    Commented Sep 12, 2015 at 15:26
  • 1
    $\begingroup$ @MaartenBodewes It's a better fit on CS.SE for sure, but the migration options are so bad that a lot of users who browse [algorithm] would rather just answer the question. $\endgroup$
    – David Eisenstat
    Commented Sep 12, 2015 at 15:41

2 Answers 2

Reset to default
6
$\begingroup$

With an admissible heuristic

The heuristic defines which nodes will be explored first, but does not change the final path found.

In your example, the heuristic will cause the path to Z to be explored first. The algorithm will discover the true (expensive) cost of 120. Then it will decide to explore the A path and discover the optimal route.

A better heuristic would guess A was the way to go immediately, find the cost of 100, and never bother exploring Z at all (e.g. if the heuristic said the cost was greater than 100).

So the heuristic changes the execution time, but not the final answer.

With an unadmissable heuristic

If the heuristic marked A as costing 130 (when the true cost is 100), it may find the route to Z (true cost 120), and instantly stop (because it "knows" the cost to A is at least 130), so return the wrong answer.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If the heuristic was non-admissible though, wouldn't it explore Z first, discover the true (expensive) cost of 120 and then explore the A path, find its true cost, and mark is as optimal? How does the fact that the heuristic is non-admissible mean that we mark Z as the optimal one and miss A? $\endgroup$
    – Laura K
    Commented Sep 12, 2015 at 15:28
  • 1
    $\begingroup$ The algorithm doesn't explore paths that it "knows" will have a higher cost - see my edit. $\endgroup$
    – Peter de Rivaz
    Commented Sep 12, 2015 at 15:33
1
$\begingroup$

A* does not guarantee to find optimal path to nodes with h(v) > 0. It only guarantees to find the optimal route to the target node, with h(v) = 0. In the process of doing so, it will find optimal path to many nodes along the way, but not all of them.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.