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(void);
00085 void init(Space* s);
00087 void reset(Space* s, unsigned int d);
00089 Statistics statistics(void) const;
00091 ~Probe(void);
00093 Space* next(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, const Options& o);
00115 virtual Space* next(void);
00117 virtual Statistics statistics(void) const;
00119 void constrain(const Space& b);
00121 void reset(Space* s);
00123 virtual bool stopped(void) const;
00125 virtual ~LDS(void);
00126 };
00127
00128
00129
00130
00131
00132
00133
00134 forceinline
00135 Probe::Node::Node(void) {}
00136
00137 forceinline
00138 Probe::Node::Node(Space* s, const Choice* c, unsigned int a)
00139 : _space(s), _choice(c), _alt(a) {}
00140
00141 forceinline Space*
00142 Probe::Node::space(void) const {
00143 return _space;
00144 }
00145
00146 forceinline const Choice*
00147 Probe::Node::choice(void) const {
00148 return _choice;
00149 }
00150
00151 forceinline unsigned int
00152 Probe::Node::alt(void) const {
00153 return _alt;
00154 }
00155
00156 forceinline void
00157 Probe::Node::next(void) {
00158 _alt--;
00159 }
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169 forceinline
00170 Probe::Probe(void)
00171 : ds(heap) {}
00172
00173 forceinline void
00174 Probe::init(Space* s) {
00175 cur = s; d = 0U; exhausted = true;
00176 }
00177
00178 forceinline void
00179 Probe::reset(Space* s, unsigned int d0) {
00180 delete cur;
00181 while (!ds.empty())
00182 delete ds.pop().space();
00183 cur = s; d = d0; exhausted = true;
00184 Worker::reset(0);
00185 }
00186
00187 forceinline Statistics
00188 Probe::statistics(void) const {
00189 return *this;
00190 }
00191
00192 forceinline bool
00193 Probe::done(void) const {
00194 return exhausted;
00195 }
00196
00197 forceinline
00198 Probe::~Probe(void) {
00199 delete cur;
00200 while (!ds.empty())
00201 delete ds.pop().space();
00202 }
00203
00204 forceinline Space*
00205 Probe::next(const Options& opt) {
00206 start();
00207 while (true) {
00208 if (cur == NULL) {
00209 backtrack:
00210 if (ds.empty())
00211 return NULL;
00212 if (stop(opt))
00213 return NULL;
00214 unsigned int a = ds.top().alt();
00215 const Choice* ch = ds.top().choice();
00216 if (a == 0) {
00217 cur = ds.pop().space();
00218 cur->commit(*ch,0);
00219 delete ch;
00220 } else {
00221 ds.top().next();
00222 cur = ds.top().space()->clone();
00223 cur->commit(*ch,a);
00224 }
00225 node++;
00226 d++;
00227 }
00228 check_discrepancy:
00229 if (d == 0) {
00230 Space* s = cur;
00231 while (s->status(*this) == SS_BRANCH) {
00232 if (stop(opt)) {
00233 cur = s;
00234 return NULL;
00235 }
00236 const Choice* ch = s->choice();
00237 if (ch->alternatives() > 1)
00238 exhausted = false;
00239 s->commit(*ch,0);
00240 node++;
00241 delete ch;
00242 }
00243 cur = NULL;
00244 if (s->failed()) {
00245 fail++;
00246 delete s;
00247 goto backtrack;
00248 }
00249
00250 (void) s->choice();
00251 return s;
00252 }
00253 node++;
00254 switch (cur->status(*this)) {
00255 case SS_FAILED:
00256 fail++;
00257 case SS_SOLVED:
00258 delete cur;
00259 cur = NULL;
00260 goto backtrack;
00261 case SS_BRANCH:
00262 {
00263 const Choice* ch = cur->choice();
00264 unsigned int alt = ch->alternatives();
00265 if (alt > 1) {
00266 if (d < alt-1)
00267 exhausted = false;
00268 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00269 Space* cc = cur->clone();
00270 Node sn(cc,ch,d_a-1);
00271 ds.push(sn);
00272 stack_depth(static_cast<unsigned long int>(ds.entries()));
00273 cur->commit(*ch,d_a);
00274 d -= d_a;
00275 } else {
00276 cur->commit(*ch,0);
00277 node++;
00278 delete ch;
00279 }
00280 goto check_discrepancy;
00281 }
00282 default: GECODE_NEVER;
00283 }
00284 }
00285 }
00286
00287 forceinline
00288 LDS::LDS(Space* s, const Options& o)
00289 : opt(o), root(NULL), d(0) {
00290 e.node = 1;
00291 if (s->status(e) == SS_FAILED) {
00292 e.fail++;
00293 e.init(NULL);
00294 } else {
00295 Space* c = snapshot(s,opt);
00296 if (opt.d_l > 0) {
00297 root = c->clone();
00298 }
00299 e.init(c);
00300 }
00301 }
00302
00303 forceinline void
00304 LDS::reset(Space* s) {
00305 delete root; root=NULL; d=0;
00306 e.node = 1;
00307 if ((s == NULL) || (s->status(e) == SS_FAILED)) {
00308 delete s;
00309 e.fail++;
00310 e.reset(NULL,0);
00311 } else {
00312 if (opt.d_l > 0) {
00313 root = s->clone();
00314 }
00315 e.reset(s,0);
00316 }
00317 }
00318
00319 forceinline void
00320 LDS::constrain(const Space& b) {
00321 (void) b;
00322 assert(false);
00323 }
00324
00325 }}}
00326
00327 #endif
00328
00329