[gecode-users] Best-first search

[Guido Tack]

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