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 | |
Stop-objects for stopping search | |
Classes | |
class | Gecode::Search::Statistics |
Search engine statistics More... | |
class | Gecode::DFS< T > |
Depth-first search engine. More... | |
class | Gecode::LDS< T > |
Limited discrepancy search engine. More... | |
class | Gecode::BAB< T > |
Depth-first branch-and-bound search engine. More... | |
class | Gecode::Restart< T > |
Depth-first 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 depth-first search engine. | |
template<class T> | |
T * | Gecode::lds (T *s, unsigned int d, Search::Stop *st=NULL) |
Invoke limited-discrepancy 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 depth-first branch-and-bound search. |
Function Documentation
|
Invoke depth-first search engine.
|
|
Invoke limited-discrepancy search.
|
|
Perform depth-first branch-and-bound search.
|