CODEWITHSUNDEEP
haskell
ashta
ashta

Reputation: 31

How to implement a best-first search in Haskell?

Is there a way to do a best-first search efficiently in Haskell? I want to maintain a dynamic tree. I have a heuristic function which can compute a number for each node and a successor function which will return a list of children of a node.

At every step, I want to take the leaf-node with the best heuristic and replace it with its children. This process is repeated until I get a node which is 'good enough'.

For this, I need to maintain a priority queue of the leaves. But is there a way by which I can go from a leaf in the priority queue to its position in the tree efficiently so that I can modify the tree?

Upvotes: 3

Views: 409

Answers (3)

luqui
luqui

Reputation: 60503

Check out the weighted-search package, which implements a priority search monad. It allows you to express the solutions you want, adding weight along the way to indicate when you know that a solution has increased in expense, and the package will find the least-weight solutions first. In your case, create the whole tree (possibly infinite) you want to search, and then use weighted-search to construct all the paths through that tree and give weights to them. Then you will get the least-weight paths first.

Upvotes: 1

GarethR
GarethR

Reputation: 724

You shouldn't need an explicit tree for a best first search. Just the priority queue should do. Make the nodes of the queue carry as much context as necessary to compute the successor nodes and cost function. If you really need the tree, then as others have said, zippers are the way to go. You'd keep zippers in your priority queue rather than just tree nodes. Since the priority queue holds all the leaves, you shouldn't need to modify a shared tree.

Upvotes: 2

J. Abrahamson
J. Abrahamson

Reputation: 74364

One possible answer is to use Haskell's sneakiest form of mutability: laziness. If you lazily generate the entire tree (even if it's infinite) then repeatedly view different points in the tree according to your priority queue then you will only ever produce as much of the tree as is needed to perform your best-first search.

You'll still pay for repeated traversals of the lower branches of the tree, but perhaps you can change the structure of your search somehow to do better.

Upvotes: 6

Related Questions