Malcolm Ryan wrote: > I need a search engine for gecode that implements best-first search, > i.e. search using a priority queue sorted on an heuristic. It doesn't > look like Gecode current implements this, so I figure I'll have to > write it myself. > > Any recommendations on how I should go about it? I've been reading the > source for DFS and LDS but I'm not clear on what functions such an > engine would be expected to implement.
If you want the same interface as the built-in search engines, it should mainly provide a next method, and probably use Stop objects to further control the search. In order to get started, I'd just use an STL priority queue and implement a system with full copying, i.e., the queue stores spaces. When you dequeue a space, you determine the number of its children n, create n-1 copies, commit the original space and each copy to one alternative each, determine the cost for each child, and enqueue the resulting children. This should give you something that works, although the cost in terms of memory may be prohibitive (you'll keep an exponential number of spaces alive). So the second step would be to figure out how to combine this with recomputation. Instead of queuing spaces, you queue nodes, which may contain a space or a pointer to a parent node. You'll have to represent parts of the search tree in addition to the queue in order to make this work. Then, if you dequeue a node that doesn't have a space, you follow the parent pointers up in the tree to find a node with a space, and recompute the target node. I'm not quite sure how this works in practice, as you'll have to actually create a space for each node when you create it, to determine its priority. I guess you'd then throw away the spaces for all nodes except the best, or something similar. Cheers, Guido _______________________________________________ Gecode users mailing list us...@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users