[gecode-users] Best-first search

[Malcolm Ryan]

After some more reading of the DFS and LDS code I think I've got it  
more or less worked out. It doesn't need to be terribly efficient. It  
is the 'conventional approach' in an experiment which aims to show  
that another approach is superior, so I'm not going out of my way to  
optimise it cleverly.

It could, however, be worth implementing an RCS-style system in  
general. The value would depend on how good your heuristic is. A good  
heuristic should result in behaviour very similar to DFS. A bad  
heuristic could cause search to behave more like BFS which would make  
RCS fairly useless, I think.

Malcolm

On 04/09/2009, at 5:30 PM, Guido Tack wrote:

> 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