[Haskell-cafe] lazy A-star search

[wren ng thornton]

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