40#ifdef GECODE_HAS_EXPERIMENTAL
42#ifdef GECODE_HAS_THREADS
50 bool open(
void)
const override {
51 return !
queue.empty();
96#ifdef GECODE_HAS_THREADS
108 : opt(o), guidance(*o.guidance), queue(
Priority{guidance.sense,false}),
109 order(0), status(
SS_FAILED), depth(0), revision(0), counted(false),
110 best(guidance.sense) {
111 initialize(s,o.
clone);
115 AStar::initialize(
Space* s,
bool clone) {
120 status = s->
status(*
this);
127 expansion.
select(std::unique_ptr<Space>(clone ? s->
clone() : s));
131 AStar::enqueue(std::unique_ptr<Space> s,
unsigned long int d) {
132 std::int64_t b = guidance.
bound(*s);
137 std::int64_t
r = guidance.rank ? guidance.rank(*s) : 0;
138 queue.push({s.release(),
b,
r,0,
d,order++,best.revision});
142 AStar::publish(std::unique_ptr<Space> s) {
145 std::int64_t
b = guidance.bound(*s);
146 if (!best.improves(b))
148 Space* copy = s->clone();
149 best.update(s.release(),b);
162 Entry e = queue.pop();
163 std::unique_ptr<Space> s(e.
space);
164 if (!best.improves(e.
bound)) {
168 expansion.select(std::move(s));
179 if (
Space* s = publish(expansion.take()))
183 if (!best.improves(guidance.bound(expansion.space()))) {
190 best.space.get(),best.revision);
193 switch (step.status) {
198 if (
Space* s = publish(std::move(step.space)))
202 enqueue(std::move(step.space),depth+1);
217 std::int64_t b = guidance.bound(s);
218 if (best.improves(b))
219 best.update(s.
clone(),b);
224 std::unique_ptr<Space> replacement(s);
235 (void) replacement.release();
No-goods recorded from restarts.
static NoGoods eng
Empty no-goods.
Search engine implementation interface
Open node of a heuristic search engine.
Space * space
The stable space (owned by the container holding the entry).
unsigned long long int revision
Incumbent revision the space has been constrained with.
unsigned long int depth
Depth of the node.
std::int64_t bound
Bound and rank of the space.
Evaluate bound
Optimistic objective bound (required).
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
bool clone
Whether engines create a clone when being initialized.
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Options expand(void) const
Expand with real number of threads.
SearchTracer * tracer
Tracer object for tracing search.
double threads
Number of threads to use.
Entry select(void) override
Remove and return the next open node.
bool open(void) const override
Whether there are open nodes.
void clear(void) override
Delete all open nodes.
~AStar(void) override
Destructor.
AStar(Space *s, const Options &o)
Initialize for space s with options o.
bool advance(void) override
Called when all work is done, return whether there is new work.
void submit(const Entry &e, bool) override
Add child e, or delete it; leased tells whether its parent is still leased.
unsigned long long int order
Number of created entries.
Search::Statistics stat
Statistics.
void terminate(void)
Stop all workers (must be called by subclass destructors).
HeuristicGuidance guidance
Guidance.
void initialize(Space *s, bool clone)
Start search from root s.
Incumbent best
Best solution so far.
Frontier(const Options &o)
Initialize with options o.
Order of open nodes: whether a is preferred to b.
Priority queue of open nodes for A*.
Space * next(void)
Return next better solution (nullptr if none or stopped).
NoGoods & nogoods(void)
Return no-goods (none).
Statistics statistics(void) const
Return statistics.
void constrain(const Space &b)
Constrain future solutions to be better than b.
AStar(Space *s, const Options &o)
Initialize for space s with options o.
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
unsigned long long int fail
Number of failed nodes in search tree.
unsigned long long int node
Number of nodes expanded.
Exception: Missing guidance for heuristic search
Exception: Search engine does not support tracing
Virtualize a worker to an engine.
void start(void)
Reset stop information.
bool stop_seq(Options &o)
Check stop and wait for admission of a sequential worker.
void stack_depth(unsigned long int d)
Record stack depth d.
void reset(void)
Reset information.
Space * clone(void) const
Clone space.
SpaceStatus status(StatusStatistics &stat)
Query space status.
@ SS_BRANCH
Space must be branched (at least one brancher left)
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
Engine * astarengine(Space *s, const Options &o)
Create A* engine.
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
#define GECODE_NEVER
Assert that this command is never executed.