[Haskell-cafe] lazy A-star search
wren ng thornton
wren at freegeek.org
Mon Oct 31 01:49:57 CET 2011
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. 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.
 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
More information about the Haskell-Cafe