On Wed, Jun 24, 2009 at 7:53 PM, Martin Hofmann < martin.hofmann@uni-bamberg.de> wrote:
I am looking for a good (preferably lazy) way to implement some kind of best-first search.
Here's what I came up with. bestFirst :: (Ord o) => (a -> o) -> (a -> [a]) -> [a] -> [a] bestFirst rate edges = go where go [] = [] go (x:xs) = x : go (mergeOn rate (edges x) xs) mergeOn :: (Ord o) => (a -> o) -> [a] -> [a] -> [a] mergeOn f [] ys = ys mergeOn f xs [] = xs mergeOn f (x:xs) (y:ys) | f x <= f y = x : mergeOn f xs (y:ys) | otherwise = y : mergeOn f (x:xs) ys 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. Luke
The problem is, the expansion of the 'best' node in the search space forces other 'inferior' nodes to expand too. So my function
expand :: Node -> ([Node],(Node -> [Node]))
does not only return some successor nodes, but also a function to expand other Nodes with certain characteristics.
So in fact, after one expansion, I need to fold over my complete search space, maybe updating other nodes and recompute the value of the cost function for the affected nodes.
At the moment I am using StateT monad transformers, and retrieving the affected Nodes from a map (to avoid going through whole space), but this is not very elegant and I doubt whether it is efficient, too.
I have already read through Spivey's paper "Algebras for combinatorial search". Unfortunately, he only proposes the use of heuristics and best-first search in combination with his framework for future work. Does anybody now some further papers on this topic?
Thanks a lot in advance,
Martin
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe