lds.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Nodes for the probing engine (just remember next alternative 00126 * to try) 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 * The probing engine: computes all solutions with 00160 * exact number of discrepancies (solutions with 00161 * fewer discrepancies are discarded) 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 // Deletes all pending branchings 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 // STATISTICS: search-sequential