Home Products Download Order Contacts

comp.graphics.algorithms

Subject: Re: Correctness of Dijkstra & A*



guanaco wrote:
> 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
followed).

/Mikkel

Reply


View All Messages in comp.graphics.algorithms

path:
Correctness of Dijkstra & A* =>Re: Correctness of Dijkstra & A* =>

Replies:

Copyright 2006 WatermarkFactory.com. All Rights Reserved.