On Wed, Jun 24, 2009 at 7:53 PM, Martin Hofmann <span dir="ltr"><<a href="mailto:martin.hofmann@uni-bamberg.de">martin.hofmann@uni-bamberg.de</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I am looking for a good (preferably lazy) way to implement some kind of<br>
best-first search.</blockquote><div><br>Here's what I came up with.<br><br><span style="font-family: courier new,monospace;">bestFirst :: (Ord o) => (a -> o) -> (a -> [a]) -> [a] -> [a]</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">bestFirst rate edges = go</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> where</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> go [] = []</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> go (x:xs) = x : go (mergeOn rate (edges x) xs)</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mergeOn :: (Ord o) => (a -> o) -> [a] -> [a] -> [a]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mergeOn f [] ys = ys</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">mergeOn f xs [] = xs</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mergeOn f (x:xs) (y:ys)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> | f x <= f y = x : mergeOn f xs (y:ys)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> | otherwise = y : mergeOn f (x:xs) ys</span><br>
<br>The preconditions for bestFirst rate edges xs are: map rate xs must be nondecreasing, and for all x, map rate (edges x) must be nondecreasing, and all no less than x. Then I believe this is A*. At least in spirit it is, though there might be "too many merges" making the complexity worse. I'm not terribly good at analyzing those things.<br>
<br>Luke<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
<br>
The problem is, the expansion of the 'best' node in the search space<br>
forces other 'inferior' nodes to expand too. So my function<br>
<br>
expand :: Node -> ([Node],(Node -> [Node]))<br>
<br>
does not only return some successor nodes, but also a function to expand<br>
other Nodes with certain characteristics.<br>
<br>
So in fact, after one expansion, I need to fold over my complete search<br>
space, maybe updating other nodes and recompute the value of the cost<br>
function for the affected nodes.<br>
<br>
At the moment I am using StateT monad transformers, and retrieving the<br>
affected Nodes from a map (to avoid going through whole space), but this<br>
is not very elegant and I doubt whether it is efficient, too.<br>
<br>
I have already read through Spivey's paper "Algebras for combinatorial<br>
search". Unfortunately, he only proposes the use of heuristics and<br>
best-first search in combination with his framework for future work.<br>
Does anybody now some further papers on this topic?<br>
<br>
Thanks a lot in advance,<br>
<br>
Martin<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">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>
</blockquote></div><br>