Guidance for heuristic search engines (experimental). More...
#include <gecode/search.hh>
Public Types | |
| enum | Sense { MINIMIZE , MAXIMIZE } |
| Objective direction. More... | |
| typedef std::function< std::int64_t(const Space &)> | Evaluate |
| Function evaluating a stable space. | |
Public Member Functions | |
| HeuristicGuidance (Sense s, Evaluate b, Evaluate r=Evaluate()) | |
| Initialize guidance. | |
Public Attributes | |
| Sense | sense |
| Objective direction. | |
| Evaluate | bound |
| Optimistic objective bound (required). | |
| Evaluate | rank |
| Node rank (optional, lower first). | |
| std::function< bool(const Space &, const Space &)> | dominates |
| Whether the first space dominates the second (optional). | |
| std::function< std::size_t(const Space &)> | dominance_key |
| Dominance key (optional). | |
Detailed Description
Guidance for heuristic search engines (experimental).
The bound is an optimistic objective value for a stable space: a lower bound when minimizing, an upper bound when maximizing, and the exact objective for a solution. It must agree with the model's constrain function. The optional rank orders nodes (lower first) but is never used for pruning.
The optional dominance predicate returns whether every completion of the second space is matched by a completion of the first that is not worse. It must be transitive. CABS uses it to prune nodes in the same layer. If a dominance key is given, only nodes with equal keys are compared. Without a key, every node offered to the beam is compared with every node already in it.
A* and CABS clone and propagate every child of every node they expand, also close to the root where domains are large. The cost of a node is thus a clone plus propagation at shallow depth, so models should use propagators that stay cheap there.
Callbacks must only read the space passed to them. With several threads they can run concurrently.
Member Typedef Documentation
◆ Evaluate
| typedef std::function<std::int64_t(const Space&)> Gecode::Search::HeuristicGuidance::Evaluate |
Member Enumeration Documentation
◆ Sense
Constructor & Destructor Documentation
◆ HeuristicGuidance()
Member Data Documentation
◆ sense
| Sense Gecode::Search::HeuristicGuidance::sense |
◆ bound
| Evaluate Gecode::Search::HeuristicGuidance::bound |
◆ rank
| Evaluate Gecode::Search::HeuristicGuidance::rank |
◆ dominates
◆ dominance_key
| std::function<std::size_t(const Space&)> Gecode::Search::HeuristicGuidance::dominance_key |
The documentation for this class was generated from the following file:
- gecode/search.hh
