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.
|