Search engines
[Interfacing to Gecode]
Collaboration diagram for Search engines:
Detailed Description
Defines search engines. All search engines (but Gecode::LDS, where it is not needed) support recomputation. The behaviour of recomputation can be controlled by two parameters: c_d as minimal recomputation distance: this guarantees that a path between two nodes in the search tree for which copies are stored has at least length c_d. That is, in order to recompute a node in the search tree, c_d recomputation steps are needed. The minimal recomputation distance yields a guarantee on saving memory compared to full copying: it stores c_d times less nodes than full copying.
 a_d as adaptive recomputation distance: when a node needs to be recomputed and the path is longer than a_d, an intermediate copy is created (approximately in the middle of the path) to speed up future recomputation. Note that small values of a_d can increase the memory consumption considerably.
Full copying corresponds to a maximal recomputation distance c_d of 1.
All recomputation performed is based on batch recomputation: batch recomputation performs propagation only once for an entire path used in recomputation.
Requires
#include "gecode/search.hh"
Namespaces  
namespace  Gecode::Search::Config 
Search configuration  
Modules  
Stopobjects for stopping search  
Classes  
class  Gecode::Search::Statistics 
Search engine statistics More...  
class  Gecode::DFS< T > 
Depthfirst search engine. More...  
class  Gecode::LDS< T > 
Limited discrepancy search engine. More...  
class  Gecode::BAB< T > 
Depthfirst branchandbound search engine. More...  
class  Gecode::Restart< T > 
Depthfirst restart best solution search engine. More...  
Functions  
template<class T>  
T *  Gecode::dfs (T *s, unsigned int c_d=Search::Config::c_d, unsigned int a_d=Search::Config::a_d, Search::Stop *st=NULL) 
Invoke depthfirst search engine.  
template<class T>  
T *  Gecode::lds (T *s, unsigned int d, Search::Stop *st=NULL) 
Invoke limiteddiscrepancy search.  
template<class T>  
T *  Gecode::bab (T *s, unsigned int c_d=Search::Config::c_d, unsigned int a_d=Search::Config::a_d, Search::Stop *st=NULL) 
Perform depthfirst branchandbound search. 
Function Documentation

Invoke depthfirst search engine.


Invoke limiteddiscrepancy search.


Perform depthfirst branchandbound search.
