[Haskell-cafe] lazy data structure for best-first search

[Luke Palmer]

On Wed, Jun 24, 2009 at 7:53 PM, Martin Hofmann <
martin.hofmann at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090624/7af498a3/attachment.html