[Haskell-cafe] lazy A-star search
Ryan Ingram
ryani.spam at gmail.com
Tue Nov 1 00:48:44 CET 2011
On Sun, Oct 30, 2011 at 8:44 AM, Anton Kholomiov
<anton.kholomiov at gmail.com>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.
>
Sort of. Consider the tree in my example graph:
A -1- B -1- C -1- D -1- E -9- J
-2- F -1- C -1- D -1- E -9- J
-2- G -1- D -1- E -9- J
-2- H -1- E -9- J
-2- I -1- J
There's no circling going on as you depth-first search this tree, even
though you are wasting time visiting the same node multiple times.
However, the thing you know with A*/djikstra is this: If I have visited a
node, there is no shorter path to that node. So any time I encounter that
node again, I must have at least as long of a path, and so any later nodes
along that path can't be any better along this path.
Effectively, you are pruning the tree:
A -1- B -1- C -1- D -1- E -9- J ***
-2- F -1- C ***
-2- G -1- D ***
-2- H -1- E ***
-2- I -1- J GOAL
(*** = pruned branches)
since the second time you visit C, you know the first path was faster, so
there is no reason to continue to visit D/E again. This is even more
noticable in graphs with multidirectional edges, as the tree is infinitely
deep at every cycle.
I wonder if there is a way to represent this more directly as
tree-pruning. It's weird, because you are pruning the tree based on
visiting other branches of the tree.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111031/b38da472/attachment.htm>
More information about the Haskell-Cafe
mailing list