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$
  • 2
    $\begingroup$ Why do you think that? Have you tried running A* by hand to see what it does? $\endgroup$ – D.W. May 9 '18 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 '18 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 '18 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$ – David Richerby May 9 '18 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 '18 at 14:55
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$
  • $\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 '18 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$ – ratchet freak May 9 '18 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 '18 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$ – ratchet freak May 9 '18 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$ – ratchet freak May 9 '18 at 9:37

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.