Generated on for Gecode by doxygen 1.17.0
astar.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34
35#include <gecode/search.hh>
39
40#ifdef GECODE_HAS_EXPERIMENTAL
41
42#ifdef GECODE_HAS_THREADS
43namespace Gecode { namespace Search { namespace Par {
44
46 class AStar : public Frontier {
47 protected:
50 bool open(void) const override {
51 return !queue.empty();
52 }
53 Entry select(void) override {
54 return queue.pop();
55 }
56 void submit(const Entry& e, bool) override {
57 if (!best.improves(e.bound)) {
58 stat.fail++;
59 delete e.space;
60 return;
61 }
62 Entry f = e;
63 f.order = order++;
64 queue.push(f);
65 }
66 bool advance(void) override {
67 return false;
68 }
69 void clear(void) override {
70 queue.clear();
71 }
72 public:
74 AStar(Space* s, const Options& o)
75 : Frontier(o), queue(Priority{guidance.sense,false}) {
76 initialize(s,o.clone);
77 }
78
79 ~AStar(void) override {
80 terminate();
81 }
82 };
83
84}}}
85#endif
86
87namespace Gecode { namespace Search {
88
89 Engine*
90 astarengine(Space* s, const Options& o) {
91 Options e = o.expand();
92 if (e.tracer != nullptr)
93 throw UnsupportedTracer("AStar::AStar");
94 if ((e.guidance == nullptr) || !e.guidance->bound)
95 throw UninitializedGuidance("AStar::AStar");
96#ifdef GECODE_HAS_THREADS
97 if (e.threads > 1.0)
98 return new Par::AStar(s,e);
99#endif
100 return new WorkerToEngine<Seq::AStar>(s,e);
101 }
102
103}}
104
105namespace Gecode { namespace Search { namespace Seq {
106
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);
112 }
113
114 void
115 AStar::initialize(Space* s, bool clone) {
116 if (s == nullptr) {
117 fail++;
118 return;
119 }
120 status = s->status(*this);
121 if (status == SS_FAILED) {
122 fail++;
123 if (!clone)
124 delete s;
125 return;
126 }
127 expansion.select(std::unique_ptr<Space>(clone ? s->clone() : s));
128 }
129
130 void
131 AStar::enqueue(std::unique_ptr<Space> s, unsigned long int d) {
132 std::int64_t b = guidance.bound(*s);
133 if (!best.improves(b)) {
134 fail++;
135 return;
136 }
137 std::int64_t r = guidance.rank ? guidance.rank(*s) : 0;
138 queue.push({s.release(),b,r,0,d,order++,best.revision});
139 }
140
141 Space*
142 AStar::publish(std::unique_ptr<Space> s) {
143 // Delete exhausted branchers before cloning the solution
144 (void) s->choice();
145 std::int64_t b = guidance.bound(*s);
146 if (!best.improves(b))
147 return nullptr;
148 Space* copy = s->clone();
149 best.update(s.release(),b);
150 return copy;
151 }
152
153 Space*
155 start();
156 while (true) {
157 if (stop_seq(opt))
158 return nullptr;
159 if (!expansion) {
160 if (queue.empty())
161 return nullptr;
162 Entry e = queue.pop();
163 std::unique_ptr<Space> s(e.space);
164 if (!best.improves(e.bound)) {
165 fail++;
166 continue;
167 }
168 expansion.select(std::move(s));
169 depth = e.depth;
170 revision = e.revision;
171 counted = true;
172 }
173 if (!counted) {
174 // The root
175 node++;
176 stack_depth(depth);
177 counted = true;
178 if (status == SS_SOLVED) {
179 if (Space* s = publish(expansion.take()))
180 return s;
181 continue;
182 }
183 if (!best.improves(guidance.bound(expansion.space()))) {
184 fail++;
185 expansion.reset();
186 continue;
187 }
188 }
189 ExpansionStep step = expansion.next(*this,depth+1,revision,
190 best.space.get(),best.revision);
191 if (step.state == ExpansionStep::EXHAUSTED)
192 continue;
193 switch (step.status) {
194 case SS_FAILED:
195 fail++;
196 break;
197 case SS_SOLVED:
198 if (Space* s = publish(std::move(step.space)))
199 return s;
200 break;
201 case SS_BRANCH:
202 enqueue(std::move(step.space),depth+1);
203 break;
204 default:
206 }
207 }
208 }
209
211 AStar::statistics(void) const {
212 return *this;
213 }
214
215 void
217 std::int64_t b = guidance.bound(s);
218 if (best.improves(b))
219 best.update(s.clone(),b);
220 }
221
222 void
224 std::unique_ptr<Space> replacement(s);
225 expansion.reset();
226 queue.clear();
227 best.reset();
228 order = 0;
229 revision = 0;
230 depth = 0;
231 counted = false;
233 initialize(s,false);
234 // The root is owned by the engine after initialize returns
235 (void) replacement.release();
236 }
237
238 NoGoods&
240 return NoGoods::eng;
241 }
242
243}}}
244
245#endif
246
247// STATISTICS: search-other
No-goods recorded from restarts.
Definition core.hpp:1606
static NoGoods eng
Empty no-goods.
Definition core.hpp:1628
Search engine implementation interface
Definition search.hh:1063
Open node of a heuristic search engine.
Definition heuristic.hh:53
Space * space
The stable space (owned by the container holding the entry).
Definition heuristic.hh:56
unsigned long long int revision
Incumbent revision the space has been constrained with.
Definition heuristic.hh:66
unsigned long int depth
Depth of the node.
Definition heuristic.hh:62
std::int64_t bound
Bound and rank of the space.
Definition heuristic.hh:58
Evaluate bound
Optimistic objective bound (required).
Definition search.hh:1268
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
Definition heuristic.hh:101
Search engine options
Definition search.hh:848
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:851
const HeuristicGuidance * guidance
Guidance for heuristic search (AStar and CABS, not copied).
Definition search.hh:882
Options expand(void) const
Expand with real number of threads.
Definition options.cpp:43
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
double threads
Number of threads to use.
Definition search.hh:853
Parallel A* search.
Definition astar.cpp:46
Entry select(void) override
Remove and return the next open node.
Definition astar.cpp:53
bool open(void) const override
Whether there are open nodes.
Definition astar.cpp:50
Queue queue
Open nodes.
Definition astar.cpp:49
void clear(void) override
Delete all open nodes.
Definition astar.cpp:69
~AStar(void) override
Destructor.
Definition astar.cpp:79
AStar(Space *s, const Options &o)
Initialize for space s with options o.
Definition astar.cpp:74
bool advance(void) override
Called when all work is done, return whether there is new work.
Definition astar.cpp:66
void submit(const Entry &e, bool) override
Add child e, or delete it; leased tells whether its parent is still leased.
Definition astar.cpp:56
unsigned long long int order
Number of created entries.
Definition frontier.hh:96
Search::Statistics stat
Statistics.
Definition frontier.hh:108
void terminate(void)
Stop all workers (must be called by subclass destructors).
Definition frontier.cpp:135
HeuristicGuidance guidance
Guidance.
Definition frontier.hh:90
void initialize(Space *s, bool clone)
Start search from root s.
Definition frontier.cpp:74
Incumbent best
Best solution so far.
Definition frontier.hh:92
Frontier(const Options &o)
Initialize with options o.
Definition frontier.cpp:58
Order of open nodes: whether a is preferred to b.
Definition heuristic.hh:70
Priority queue of open nodes for A*.
Definition heuristic.hh:135
Space * next(void)
Return next better solution (nullptr if none or stopped).
Definition astar.cpp:154
NoGoods & nogoods(void)
Return no-goods (none).
Definition astar.cpp:239
Statistics statistics(void) const
Return statistics.
Definition astar.cpp:211
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition astar.cpp:216
AStar(Space *s, const Options &o)
Initialize for space s with options o.
Definition astar.cpp:107
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
Search engine statistics
Definition search.hh:155
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
Exception: Missing guidance for heuristic search
Definition exception.hpp:85
Exception: Search engine does not support tracing
Definition exception.hpp:91
Virtualize a worker to an engine.
Definition support.hh:47
void start(void)
Reset stop information.
Definition worker.hh:76
bool stop_seq(Options &o)
Check stop and wait for admission of a sequential worker.
Definition worker.hh:89
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:114
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
Space * clone(void) const
Clone space.
Definition core.hpp:3384
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Engine * astarengine(Space *s, const Options &o)
Create A* engine.
Definition astar.cpp:90
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
Gecode::IntSet d(v, 7)
const int r[4][2]
Definition dom.cpp:152
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56