**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.