Also, this wasn&#39;t clear in my message, but the edges in the graph only go one way; towards the top/right; otherwise the best path is ABCDEHIJ :)<br><br><div class="gmail_quote">On Thu, Oct 27, 2011 at 10:48 AM, Ryan Ingram <span dir="ltr">&lt;<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">You&#39;re missing one of the key insights from A-star (and simple djikstra, for that matter): once you visit a node, you don&#39;t have to visit it again.<br>
<br>Consider a 5x2 2d graph with these edge costs:<br><br><span style="font-family:courier new,monospace">B 1 C 1 D 1 E 9 J<br>
1   1   1   1   1<br>A 2 F 2 G 2 H 2 I<br><br></span>with the start node being A, the target node being J, and the heuristic being manhattan distance.  Your search will always try to take the top route, on every node along the bottom path, even though you visit every node along the top route in your first try at reaching the goal.  You need a way to mark that a node is visited and remove it from future consideration, or else you&#39;re wasting work.<br>

<br>A-star will visit the nodes in the order ABCDE FGHIJ; your algorithm visits the nodes in the order ABCDE FCDE GDE HE IJ.<br><font color="#888888"><br>  -- ryan<br><br></font><div class="gmail_quote"><div><div></div><div class="h5">
On Sat, Oct 22, 2011 at 5:28 AM, Anton Kholomiov <span dir="ltr">&lt;<a href="mailto:anton.kholomiov@gmail.com" target="_blank">anton.kholomiov@gmail.com</a>&gt;</span> wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div class="h5">Recently I was looking for an A-star search algorithm. I&#39;ve found a package <div>
but I couldn&#39;t understand the code. Then I saw some blogposts but they</div>
<div> were difficult to understand too. I thought about some easier solution that</div>
<div>relies on laziness. And I&#39;ve come to this:</div><div><br></div><div>Heuristic search is like depth-first search but solutions in sub-trees </div><div>are concatenated with <font color="#000099">mergeBy</font> function, that concatenates two </div>


<div>list by specific order:</div><div><br></div><div><div>module Search where</div><div><br></div><div>import Control.Applicative</div><div>import Data.Function(on)</div><div>import Control.Arrow(second)</div><div>import Data.Tree</div>


</div><div><br></div><div><div>-- | Heuristic search. Nodes are visited from smaller to greater.</div><div>searchBy :: (a -&gt; a -&gt; Ordering) -&gt; Tree a -&gt; [a]</div><div>searchBy  heur (Node v ts) = </div><div>    v : foldr (mergeBy heur) [] (searchBy heur &lt;$&gt; ts)</div>


<div><br></div><div>-- | Merge two lists. Elements concatenated in specified order.</div><div>mergeBy :: (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [a] -&gt; [a]</div><div>mergeBy _ a         []      = a</div><div>mergeBy _ []        b       = b</div>


<div>mergeBy p (a:as)    (b:bs)  </div><div>    | a `p` b == LT    = a : mergeBy p as (b:bs)</div><div>    | otherwise         = b : mergeBy p bs (a:as)</div></div><div><br></div><div><br></div><div>Now we can define specific heuristic search in terms of <font color="#000099">searchBy</font>:</div>


<div><br></div><div><div>-- | Heuristic is distance to goal.</div><div>bestFirst :: Ord h =&gt; (a -&gt; h) -&gt; (a -&gt; [a]) -&gt; a -&gt; [a]</div><div>bestFirst dist alts = </div><div>    searchBy (compare `on` dist) . unfoldTree (\a -&gt; (a, alts a))</div>


<div><br></div><div>-- | A-star search.</div><div>-- Heuristic is estimated length of whole path. </div><div>astar :: (Ord h, Num h) =&gt; (a -&gt; h) -&gt; (a -&gt; [(a, h)]) -&gt; a -&gt; [a]</div><div>astar dist alts s0 = fmap fst $ </div>


<div>    searchBy (compare `on` astarDist) $ unfoldTree gen (s0, 0)</div><div>    where astarDist (a, d) = dist a + d</div><div>          gen (a, d)  = d `seq` ((a, d), second (+d) &lt;$&gt; alts a)</div></div><div><br></div>


<div>I&#39;m wondering is it effective enough?</div><div><br></div><font color="#888888"><div><br></div><div>Anton</div>
</font><br></div></div><div class="im">_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></div></blockquote></div><br>
</blockquote></div><br>