[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell-cafe
Subject: Re: [Haskell-cafe] lazy A-star search
From: Ryan Ingram <ryani.spam () gmail ! com>
Date: 2011-10-31 23:48:44
Message-ID: CA+XKtKiGGwSepN7Tc4TGV29L_81VOMt-CSAHjf-NMackUWyk5Q () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On Sun, Oct 30, 2011 at 8:44 AM, Anton Kholomiov
<anton.kholomiov@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.
[Attachment #5 (text/html)]
<br><br><div class="gmail_quote">On Sun, Oct 30, 2011 at 8:44 AM, Anton Kholomiov \
<span dir="ltr"><<a \
href="mailto:anton.kholomiov@gmail.com">anton.kholomiov@gmail.com</a>></span> \
wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px \
#ccc solid;padding-left:1ex;"> I'm misunderstanding astar. I've thought that \
'whole route'-heuristic <div>will prevent algorithm from going in circles. \
The more you circle around</div><div>the more the whole route distance \
is.</div></blockquote> <div><br>Sort of. Consider the tree in my example \
graph:<br><br><span style="font-family: courier new,monospace;">A -1- B -1- C -1- D \
-1- E -9- J</span><br style="font-family: courier new,monospace;"><span \
style="font-family: courier new,monospace;"> -2- F -1- C -1- D -1- E -9- J</span><br \
style="font-family: courier new,monospace;"> <span style="font-family: courier \
new,monospace;"> -2- G -1- D -1- E -9- J<br> -2- H -1- E -9- \
J<br> -2- I -1- J<br><br></span>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.<br> <br>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.<br> <br>Effectively, \
you are pruning the tree:<br><span style="font-family: courier new,monospace;">A -1- \
B -1- C -1- D -1- E -9- J ***</span><br style="font-family: courier \
new,monospace;"><span style="font-family: courier new,monospace;"> -2- F -1- C \
***</span><br style="font-family: courier new,monospace;"> <span style="font-family: \
courier new,monospace;"> -2- G -1- D ***<br> -2- H -1- E ***<br> \
-2- I -1- J GOAL<br>(*** = pruned branches)<br><br></span>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.<br> <br></div>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.<br><br></div>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic