34#ifndef GECODE_SEARCH_HEURISTIC_HH
35#define GECODE_SEARCH_HEURISTIC_HH
43#ifdef GECODE_HAS_EXPERIMENTAL
129 std::sort(&(*
this)[0],&(*
this)[0]+
entries(),
130 [&](
const Entry& a,
const Entry& b) {
return p(b,a); });
151 [
this](
const Entry& a,
const Entry& b) { return p(b,a); });
157 [
this](
const Entry& a,
const Entry& b) { return p(b,a); });
205 unsigned long int _width;
207 std::optional<std::int64_t> discarded;
210 int index(std::size_t k)
const {
211 return static_cast<int>((k ^ (k >> 16)) & (n_bucket-1));
215 int b = index(slot[s].e.key);
216 slot[s].prev = -1; slot[s].next = bucket[b];
218 slot[bucket[b]].prev = s;
225 slot[x.prev].next = x.next;
227 bucket[index(x.e.key)] = x.next;
229 slot[x.next].prev = x.prev;
232 bool above(
int a,
int b)
const {
233 return p(slot[b].e,slot[a].e);
236 void place(
int i,
int s) {
237 pq[i] = s; slot[s].pos = i;
242 while ((i > 0) && above(s,pq[(i-1)/2])) {
243 place(i,pq[(i-1)/2]); i = (i-1)/2;
247 if ((c+1 < n) && above(pq[c+1],pq[c]))
251 place(i,pq[c]); i = c;
256 void add(
const Entry& e) {
259 s = free; free = slot[s].next;
267 for (
int b=0; b<n_bucket; b++)
269 for (
int i=0; i<n; i++)
280 delete slot[s].e.space;
283 slot[s].pos = -1; slot[s].next = free; free = s;
285 place(i,pq[n]); repair(i);
289 bool comparable(
const Entry& e,
int s)
const {
290 return (slot[s].pos >= 0) && ((n_bucket == 0) || (slot[s].e.key == e.key));
293 int chain_first(
const Entry& e)
const {
294 return (n_bucket > 0) ? bucket[index(e.key)] : 0;
297 int chain_next(
int s)
const {
300 return (s+1 < n_slot) ? s+1 : -1;
305 : slot(
heap), n_slot(0), free(-1), pq(
heap), n(0), bucket(
heap),
306 n_bucket(keyed ? 16 : 0), p(p0), _width(1) {
307 for (
int b=0; b<n_bucket; b++)
313 int size(
void)
const {
return n; }
315 bool empty(
void)
const {
return n == 0; }
318 return discarded && i.
improves(*discarded);
322 if ((_width > ULONG_MAX/2) || ((m > 0UL) && (2*_width > m)))
324 _width *= 2; discarded.reset();
337 for (
int s=chain_first(e); s>=0; s=chain_next(s))
343 for (
int s=chain_first(e); s>=0; ) {
344 int t = chain_next(s);
346 remove(s); victim =
true;
355 if (
static_cast<unsigned long int>(n) == _width) {
356 const Entry& worst = slot[pq[0]].e;
357 bool replace = p(e,worst);
358 std::int64_t b = replace ? worst.
bound : e.
bound;
359 if (!discarded ||
better(p.sense,b,*discarded))
362 remove(pq[0]); add(e);
375 for (
int i=0; i<n; i++)
376 l.
push(slot[pq[i]].e);
377 n = 0; n_slot = 0; free = -1;
378 for (
int b=0; b<n_bucket; b++)
383 for (
int i=0; i<n; i++)
384 delete slot[pq[i]].e.space;
385 n = 0; n_slot = 0; free = -1;
386 for (
int b=0; b<n_bucket; b++)
388 _width = 1; discarded.reset();
Heap memory management class
Beam(const Priority &p0, bool keyed)
Initialize with priority p, using keys for dominance if keyed.
Offer offer(const Entry &e, const HeuristicGuidance &g, bool room)
Offer entry e.
void clear(void)
Delete all entries and reset width.
void release(Entries &l)
Move all entries to l.
bool improving(const Incumbent &i) const
Whether discarded entries could improve an incumbent i.
bool empty(void) const
Whether there are no entries.
Offer
Result of offering an entry.
@ TAKEN
The entry has been added or deleted.
@ FULL
The entry needs a new slot but there is no room.
bool widen(unsigned long int m)
Double the width up to m (zero for no limit), false if not possible.
~Beam(void)
Delete all entries.
int size(void) const
Return the number of entries.
Stack of entries owning their spaces.
void sort(const Priority &p)
Sort such that the preferred entry is on top.
~Entries(void)
Release memory.
void clear(void)
Delete all entries.
Open node of a heuristic search engine.
Space * space
The stable space (owned by the container holding the entry).
std::size_t key
Dominance key of the space.
unsigned long long int revision
Incumbent revision the space has been constrained with.
unsigned long long int order
Creation order, for breaking ties.
unsigned long int depth
Depth of the node.
std::int64_t bound
Bound and rank of the space.
Guidance for heuristic search engines (experimental).
Sense
Objective direction.
std::function< bool(const Space &, const Space &)> dominates
Whether the first space dominates the second (optional).
Best solution found so far.
void reset(void)
Remove incumbent.
std::int64_t bound
Its objective value.
std::unique_ptr< Space > space
The solution (if any).
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
unsigned long long int revision
Incremented for every new incumbent.
void update(Space *s, std::int64_t b)
Make s with objective value b the incumbent.
HeuristicGuidance::Sense sense
Objective direction.
Incumbent(HeuristicGuidance::Sense s)
Initialize without incumbent.
Order of open nodes: whether a is preferred to b.
HeuristicGuidance::Sense sense
Objective direction.
bool operator()(const Entry &a, const Entry &b) const
Test whether a is preferred to b.
bool rank_only
Whether to order by rank only (CABS with rank).
Queue(const Priority &p0)
Initialize with priority p.
bool empty(void) const
Whether the queue is empty.
void push(const Entry &e)
Add entry e.
void clear(void)
Delete all entries.
Entries entries
The entries as a binary heap with the preferred entry first.
Entry pop(void)
Remove and return the preferred entry.
Array with arbitrary number of elements.
Stack with arbitrary number of elements.
void push(const T &x)
Push element x on top of stack.
DynamicStack(Heap &a, int n=64)
Heap heap
The single global heap.
bool better(HeuristicGuidance::Sense s, std::int64_t a, std::int64_t b)
Whether bound a is better than bound b for objective direction s.
Support algorithms and datastructures
Gecode toplevel namespace