0
$\begingroup$

The following graph has consistent heuristic. enter image description here

An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found before AC?

$\endgroup$
5
  • 2
    $\begingroup$ Why do you think that? Have you tried running A* by hand to see what it does? $\endgroup$
    – D.W.
    May 9, 2018 at 3:26
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    May 9, 2018 at 8:35
  • $\begingroup$ @BlueRaja-DannyPflughoeft By definition consistent heuristic is, when h(n) <= c(n,n')+h(n').. In this case 5 <= 1+8, which is true, so its not overestimated. $\endgroup$
    – toto8080
    May 9, 2018 at 9:12
  • $\begingroup$ I don't understand your question: A* doesn't guess paths. Look up the pseudocode for A* (e.g., in your textbook or on Wikipedia) and see for yourself what it really does on that graph. $\endgroup$ May 9, 2018 at 14:29
  • $\begingroup$ @DavidRicherby Because A* is greedy, and C's F value is lower than B's the algorithm will choose C first. So there will be a step 'in its runtime', when A* thinks the shortest path will go through C. Thats not true, and A* will also fix the path. My question is about, that I thought consistent heuristic means that the algorithm wont consider any misleading path's in its 'run'. $\endgroup$
    – toto8080
    May 9, 2018 at 14:55

1 Answer 1

1
$\begingroup$

A* isn't finished until all nodes with $f(n) < f(goal)$ are expanded.

So even though you have added $D$ to the open set you still need to expand $B$ because $f(B) = 11 < f(D) = 17$ after which $f(D)$ will become $12$

$\endgroup$
6
  • $\begingroup$ If I know it correctly, with consistent heuristic it should always choose the node which is on the shortest path. If I'm wrong, what's for the consistency? $\endgroup$
    – toto8080
    May 9, 2018 at 9:09
  • 1
    $\begingroup$ But you will see each node as a neighbour of it's predecessor before it is picked. And only when the goal is picked is the algorithm done because that is when you know that any other path will have a higher cost. $\endgroup$ May 9, 2018 at 9:12
  • $\begingroup$ If I have consistency, that also means the algorithm will never reopen its closed list. Does that mean that when D get updated C (its first parent)wont removed, and will stay there 'forever'? $\endgroup$
    – toto8080
    May 9, 2018 at 9:16
  • $\begingroup$ No because when B is explored D is still in the open list and any node in the open list is allowed to change (though only when the new f is smaller than the old one). It's half the point of the open list. $\endgroup$ May 9, 2018 at 9:23
  • 1
    $\begingroup$ Closed means don't explore this node any more, the best path to it is known. You frankly don't even need the explicit list for it. You can just add a boolean to each node isClosed. $\endgroup$ May 9, 2018 at 9:37

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.