On 10/30/11 11:44 AM, Anton Kholomiov wrote:
I'm misunderstanding astar. I've thought that 'whole route'-heuristic
will prevent algorithm from going in circles. The more you circle around
the more the whole route distance is. Thank you for showing this.
There are multiple things involved in A*.
Part of it is having the admissible heuristic in order to do
forward-chaining in a way which accounts for things you haven't
seen/handled yet.[1] Using an admissible heuristic isn't sufficient to
prevent looping. Just consider a path which has a loop with zero cost or
negative cost (if we're adding costs).
A different part of it is the fact that we can implement A* as a dynamic
programming algorithm in order to reduce the complexity of
forward-chaining. This is the insight from Dijkstra's algorithm (and
Prim's, and Kruskal's, and Warshall's,...), which also uses dynamic
programming to reduce complexity.
[1] Or dually, you could use an admissible heuristic to do
backwards-chaining in a way that accounts for things you haven't
seen/handled yet. But everyone seems to mean the forward-chaining
variant when they talk about A* (perhaps because the backward-chaining
variant would be better called B*, given the standard variable-naming
convention).
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
