Subject: Re: Correctness of Dijkstra & A*
> A* works if its heuristic is admissible, i.e. if the heuristic never
> overestimates the value of the shortest path from this node to the
> goal, then the algorithm finds the optimal solution.
> A* is very simple to understand with a figure and an example. Chapter 4
> of the Rusell and Norvig A.I. book is a very good reference.
Thanks for your answer, but I need to know WHY the optimal solution
always is found. Since I'm working with graph search, it needs to be
consistent (which at the same time means it's also admissable, but not
necessarily vice versa), so I'd like to be able to explain it with the
assumption that it's consistent (means that the triangle inequality is
View All Messages in comp.graphics.algorithms
Correctness of Dijkstra & A* =>Re: Correctness of Dijkstra & A* =>
Copyright © 2006 WatermarkFactory.com. All Rights Reserved.