[Haskell-cafe] lazy A-star search

[Ryan Ingram]

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>