Search engines
[Interfacing to Gecode/J]
Collaboration diagram for Search engines:
|
Detailed Description
This group contains the search engines provided in Gecode/J.
Recomputation
All search engines 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.
Modules | |
| Stop-objects for stopping search | |
| Allows to specify various criteria when a search engine should stop exploration. | |
Classes | |
| class | org.gecode.BABSearch |
| Depth-first branch-and-bound search engine. More... | |
| class | org.gecode.DFSSearch |
| Depth first search engine. More... | |