lds.hh
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef __GECODE_SEARCH_SEQUENTIAL_LDS_HH__
00039 #define __GECODE_SEARCH_SEQUENTIAL_LDS_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044
00045 namespace Gecode { namespace Search { namespace Sequential {
00046
00048 class Probe : public Worker {
00049 protected:
00051 class Node {
00052 private:
00054 Space* _space;
00056 const Choice* _choice;
00058 unsigned int _alt;
00059 public:
00061 Node(void);
00063 Node(Space* s, const Choice* c, unsigned int a);
00065 Space* space(void) const;
00067 const Choice* choice(void) const;
00069 unsigned int alt(void) const;
00071 void next(void);
00072 };
00074 Support::DynamicStack<Node,Heap> ds;
00076 Space* cur;
00078 unsigned int d;
00080 bool exhausted;
00081 public:
00083 Probe(size_t s);
00085 void init(Space* s, unsigned int d);
00087 void reset(Space* s, unsigned int d);
00089 Statistics statistics(void) const;
00091 ~Probe(void);
00093 Space* explore(const Options& o);
00095 bool done(void) const;
00096 };
00097
00099 class LDS : public Engine {
00100 protected:
00102 Options opt;
00104 Probe e;
00106 Space* root;
00108 unsigned int d;
00110 bool no_solution;
00111 public:
00113 LDS(Space* s, size_t sz, const Options& o);
00115 virtual Space* next(void);
00117 virtual Statistics statistics(void) const;
00119 virtual bool stopped(void) const;
00121 virtual ~LDS(void);
00122 };
00123
00124
00125
00126
00127
00128
00129
00130 forceinline
00131 Probe::Node::Node(void) {}
00132
00133 forceinline
00134 Probe::Node::Node(Space* s, const Choice* c, unsigned int a)
00135 : _space(s), _choice(c), _alt(a) {}
00136
00137 forceinline Space*
00138 Probe::Node::space(void) const {
00139 return _space;
00140 }
00141
00142 forceinline const Choice*
00143 Probe::Node::choice(void) const {
00144 return _choice;
00145 }
00146
00147 forceinline unsigned int
00148 Probe::Node::alt(void) const {
00149 return _alt;
00150 }
00151
00152 forceinline void
00153 Probe::Node::next(void) {
00154 _alt--;
00155 }
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165 forceinline
00166 Probe::Probe(size_t sz)
00167 : Worker(sz), ds(heap) {}
00168
00169 forceinline void
00170 Probe::init(Space* s, unsigned int d0) {
00171 cur = s;
00172 d = d0;
00173 exhausted = true;
00174 }
00175
00176 forceinline void
00177 Probe::reset(Space* s, unsigned int d0) {
00178 delete cur;
00179 assert(ds.empty());
00180 cur = s;
00181 d = d0;
00182 exhausted = true;
00183 Worker::reset(s);
00184 }
00185
00186 forceinline Statistics
00187 Probe::statistics(void) const {
00188 Statistics s = *this;
00189 s.memory += ds.size();
00190 return s;
00191 }
00192
00193 forceinline bool
00194 Probe::done(void) const {
00195 return exhausted;
00196 }
00197
00198 forceinline
00199 Probe::~Probe(void) {
00200 delete cur;
00201 while (!ds.empty())
00202 delete ds.pop().space();
00203 }
00204
00205 forceinline Space*
00206 Probe::explore(const Options& opt) {
00207 start();
00208 while (true) {
00209 if (cur == NULL) {
00210 backtrack:
00211 if (ds.empty())
00212 return NULL;
00213 if (stop(opt,ds.size()))
00214 return NULL;
00215 unsigned int a = ds.top().alt();
00216 const Choice* ch = ds.top().choice();
00217 if (a == 0) {
00218 cur = ds.pop().space();
00219 Worker::pop(cur,ch);
00220 cur->commit(*ch,0);
00221 delete ch;
00222 } else {
00223 ds.top().next();
00224 cur = ds.top().space()->clone();
00225 cur->commit(*ch,a);
00226 }
00227 Worker::current(cur);
00228 d++;
00229 }
00230 check_discrepancy:
00231 if (d == 0) {
00232 Space* s = cur;
00233 while (s->status(*this) == SS_BRANCH) {
00234 const Choice* ch = s->choice();
00235 if (ch->alternatives() > 1)
00236 exhausted = false;
00237 s->commit(*ch,0);
00238 delete ch;
00239 }
00240 cur = NULL;
00241 Worker::current(NULL);
00242 if (s->failed()) {
00243 delete s;
00244 goto backtrack;
00245 }
00246
00247 (void) s->choice();
00248 return s;
00249 }
00250 node++;
00251 switch (cur->status(*this)) {
00252 case SS_FAILED:
00253 fail++;
00254 case SS_SOLVED:
00255 delete cur;
00256 cur = NULL;
00257 Worker::current(NULL);
00258 goto backtrack;
00259 case SS_BRANCH:
00260 {
00261 const Choice* ch = cur->choice();
00262 unsigned int alt = ch->alternatives();
00263 if (alt > 1) {
00264 if (d < alt-1)
00265 exhausted = false;
00266 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00267 Space* cc = cur->clone();
00268 Worker::push(cc,ch);
00269 Node sn(cc,ch,d_a-1);
00270 ds.push(sn);
00271 cur->commit(*ch,d_a);
00272 d -= d_a;
00273 } else {
00274 cur->commit(*ch,0);
00275 delete ch;
00276 }
00277 goto check_discrepancy;
00278 }
00279 default: GECODE_NEVER;
00280 }
00281 }
00282 }
00283
00284 forceinline
00285 LDS::LDS(Space* s, size_t sz, const Options& o)
00286 : opt(o), e(sz), root(NULL), d(0) {
00287 if (s->status(e) == SS_FAILED) {
00288 e.init(NULL,0);
00289 e.fail += 1;
00290 e.current(s);
00291 } else {
00292 Space* c = snapshot(s,opt);
00293 if (opt.d > 0) {
00294 root = c->clone();
00295 }
00296 e.init(c,0);
00297 e.current(s);
00298 e.current(NULL);
00299 e.current(c);
00300 }
00301 }
00302
00303 }}}
00304
00305 #endif
00306
00307