Generated on Tue May 22 09:40:12 2018 for Gecode by doxygen 1.6.3

lds.hpp

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, 2016
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Search { namespace Seq {
00035 
00036   /*
00037    * Nodes for the probing engine (just remember next alternative
00038    * to try)
00039    *
00040    */
00041 
00042   template<class Tracer>
00043   forceinline
00044   Probe<Tracer>::Node::Node(void) {}
00045 
00046   template<class Tracer>
00047   forceinline
00048   Probe<Tracer>::Node::Node(Space* s, const Choice* c, unsigned int a,
00049                             unsigned int nid)
00050     : _space(s), _choice(c), _alt(a), _nid(nid) {}
00051 
00052   template<class Tracer>
00053   forceinline Space*
00054   Probe<Tracer>::Node::space(void) const {
00055     return _space;
00056   }
00057 
00058   template<class Tracer>
00059   forceinline const Choice*
00060   Probe<Tracer>::Node::choice(void) const {
00061     return _choice;
00062   }
00063 
00064   template<class Tracer>
00065   forceinline unsigned int
00066   Probe<Tracer>::Node::alt(void) const {
00067     return _alt;
00068   }
00069 
00070   template<class Tracer>
00071   forceinline unsigned int
00072   Probe<Tracer>::Node::nid(void) const {
00073     return _nid;
00074   }
00075 
00076   template<class Tracer>
00077   forceinline void
00078   Probe<Tracer>::Node::next(void) {
00079     _alt--;
00080   }
00081 
00082 
00083   /*
00084    * The probing engine: computes all solutions with
00085    * exact number of discrepancies (solutions with
00086    * fewer discrepancies are discarded)
00087    *
00088    */
00089 
00090   template<class Tracer>
00091   forceinline
00092   Probe<Tracer>::Probe(const Options& opt)
00093     : tracer(opt.tracer), ds(heap) {
00094     tracer.engine(SearchTracer::EngineType::LDS, 1U);
00095     tracer.worker();
00096   }
00097 
00098   template<class Tracer>
00099   forceinline void
00100   Probe<Tracer>::init(Space* s) {
00101     cur = s; d = 0U; exhausted = true;
00102     if (tracer)
00103       tracer.ei()->invalidate();
00104   }
00105 
00106   template<class Tracer>
00107   forceinline void
00108   Probe<Tracer>::reset(Space* s, unsigned int d0) {
00109     tracer.round();
00110     delete cur;
00111     while (!ds.empty())
00112       delete ds.pop().space();
00113     cur = s; d = d0; exhausted = true;
00114     if (tracer)
00115       tracer.ei()->invalidate();
00116     Worker::reset(0);
00117   }
00118 
00119   template<class Tracer>
00120   forceinline Statistics
00121   Probe<Tracer>::statistics(void) const {
00122     return *this;
00123   }
00124 
00125   template<class Tracer>
00126   forceinline bool
00127   Probe<Tracer>::done(void) const {
00128     return exhausted;
00129   }
00130 
00131   template<class Tracer>
00132   forceinline
00133   Probe<Tracer>::~Probe(void) {
00134     tracer.done();
00135     delete cur;
00136     while (!ds.empty())
00137       delete ds.pop().space();
00138   }
00139 
00140   template<class Tracer>
00141   forceinline Space*
00142   Probe<Tracer>::next(const Options& opt) {
00143     start();
00144     while (true) {
00145       if (cur == NULL) {
00146       backtrack:
00147         if (ds.empty())
00148           return NULL;
00149         if (stop(opt))
00150           return NULL;
00151         unsigned int a = ds.top().alt();
00152         const Choice* ch = ds.top().choice();
00153         unsigned int nid = ds.top().nid();
00154         if (a == 0) {
00155           cur = ds.pop().space();
00156           if (tracer)
00157             tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
00158           cur->commit(*ch,0);
00159           delete ch;
00160         } else {
00161           ds.top().next();
00162           cur = ds.top().space()->clone();
00163           if (tracer)
00164             tracer.ei()->init(tracer.wid(), nid, a, *cur, *ch);
00165           cur->commit(*ch,a);
00166         }
00167         node++;
00168         d++;
00169       }
00170     check_discrepancy:
00171       if (d == 0) {
00172         Space* s = cur;
00173         while (s->status(*this) == SS_BRANCH) {
00174           if (stop(opt)) {
00175             cur = s;
00176             return NULL;
00177           }
00178           const Choice* ch = s->choice();
00179           if (ch->alternatives() > 1)
00180             exhausted = false;
00181           if (tracer) {
00182             unsigned int nid = tracer.nid();
00183             SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00184                                       tracer.wid(), nid, *s, ch);
00185             tracer.node(*tracer.ei(),ni);
00186             if (tracer)
00187               tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
00188           }
00189           s->commit(*ch,0);
00190           node++;
00191           delete ch;
00192         }
00193         cur = NULL;
00194         if (s->failed()) {
00195           if (tracer) {
00196             SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00197                                       tracer.wid(), tracer.nid(), *s);
00198             tracer.node(*tracer.ei(),ni);
00199           }
00200           fail++;
00201           delete s;
00202           goto backtrack;
00203         } else {
00204           if (tracer) {
00205             SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
00206                                       tracer.wid(), tracer.nid(), *s);
00207             tracer.node(*tracer.ei(),ni);
00208           }
00209           // Deletes all pending branchings
00210           (void) s->choice();
00211           return s;
00212         }
00213       } else {
00214         node++;
00215         switch (cur->status(*this)) {
00216         case SS_FAILED:
00217           if (tracer) {
00218             SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00219                                       tracer.wid(), tracer.nid(), *cur);
00220             tracer.node(*tracer.ei(),ni);
00221           }
00222           fail++;
00223           delete cur;
00224           cur = NULL;
00225           goto backtrack;
00226         case SS_SOLVED:
00227           if (tracer) {
00228             tracer.skip(*tracer.ei());
00229           }
00230           delete cur;
00231           cur = NULL;
00232           goto backtrack;
00233         case SS_BRANCH:
00234           {
00235             const Choice* ch = cur->choice();
00236             unsigned int alt = ch->alternatives();
00237             unsigned int nid = tracer.nid();
00238             if (tracer) {
00239               SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00240                                         tracer.wid(), nid, *cur, ch);
00241               tracer.node(*tracer.ei(),ni);
00242             }
00243             if (alt > 1) {
00244               if (d < alt-1)
00245                 exhausted = false;
00246               unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00247               Space* cc = cur->clone();
00248               Node sn(cc,ch,d_a-1,nid);
00249               ds.push(sn);
00250               stack_depth(static_cast<unsigned long int>(ds.entries()));
00251               if (tracer)
00252                 tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
00253               cur->commit(*ch,d_a);
00254               d -= d_a;
00255             } else {
00256               if (tracer)
00257                 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
00258               cur->commit(*ch,0);
00259               node++;
00260               delete ch;
00261             }
00262             goto check_discrepancy;
00263           }
00264         default: GECODE_NEVER;
00265         }
00266       }
00267     }
00268   }
00269 
00270   template<class Tracer>
00271   forceinline
00272   LDS<Tracer>::LDS(Space* s, const Options& o)
00273     : opt(o), e(opt), root(NULL), d(0) {
00274     e.node = 1;
00275     if (s->status(e) == SS_FAILED) {
00276       e.fail++;
00277       e.init(NULL);
00278     } else {
00279       Space* c = snapshot(s,opt);
00280       if (opt.d_l > 0) {
00281         root = c->clone();
00282       }
00283       e.init(c);
00284     }
00285   }
00286 
00287   template<class Tracer>
00288   Space*
00289   LDS<Tracer>::next(void) {
00290     while (true) {
00291       Space* s = e.next(opt);
00292       if (s != NULL)
00293         return s;
00294       if (((s == NULL) && e.stopped()) || (++d > opt.d_l) || e.done())
00295         break;
00296       if (d == opt.d_l) {
00297         if (root != NULL)
00298           e.reset(root,d);
00299         root = NULL;
00300       } else if (root != NULL) {
00301         e.reset(root->clone(),d);
00302       }
00303     }
00304     return NULL;
00305   }
00306 
00307   template<class Tracer>
00308   bool
00309   LDS<Tracer>::stopped(void) const {
00310     return e.stopped();
00311   }
00312 
00313   template<class Tracer>
00314   Statistics
00315   LDS<Tracer>::statistics(void) const {
00316     return e.statistics();
00317   }
00318 
00319 
00320   template<class Tracer>
00321   forceinline void
00322   LDS<Tracer>::reset(Space* s) {
00323     delete root; root=NULL; d=0;
00324     e.node = 1;
00325     if ((s == NULL) || (s->status(e) == SS_FAILED)) {
00326       delete s;
00327       e.fail++;
00328       e.reset(NULL,0);
00329     } else {
00330       if (opt.d_l > 0) {
00331         root = s->clone();
00332       }
00333       e.reset(s,0);
00334     }
00335   }
00336 
00337   template<class Tracer>
00338   forceinline void
00339   LDS<Tracer>::constrain(const Space& b) {
00340     (void) b;
00341     assert(false);
00342   }
00343 
00344   template<class Tracer>
00345   LDS<Tracer>::~LDS(void) {
00346     delete root;
00347   }
00348 
00349 }}}
00350 
00351 // STATISTICS: search-seq