Generated on Thu Jul 6 07:06:49 2006 for Gecode by doxygen 1.4.7

lds.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-05-17 16:00:08 +0200 (Wed, 17 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3226 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "gecode/search.hh"
00023 
00024 namespace Gecode { namespace Search {
00025 
00026   /*
00027    * Nodes for the probing engine (just remember next alternative
00028    * to try)
00029    *
00030    */
00031 
00032   forceinline
00033   ProbeEngine::ProbeNode::ProbeNode(Space* s, unsigned int a)
00034     : _space(s), _alt(a) {}
00035 
00036   forceinline Space*
00037   ProbeEngine::ProbeNode::space(void) const {
00038     return _space;
00039   }
00040 
00041   forceinline void
00042   ProbeEngine::ProbeNode::space(Space* s) {
00043     _space = s;
00044   }
00045 
00046   forceinline unsigned int
00047   ProbeEngine::ProbeNode::alt(void) const {
00048     return _alt;
00049   }
00050 
00051   forceinline void
00052   ProbeEngine::ProbeNode::alt(unsigned int a) {
00053     _alt = a;
00054   }
00055 
00056 
00057   /*
00058    * The probing engine: computes all solutions with
00059    * exact number of discrepancies (solutions with
00060    * fewer discrepancies are discarded)
00061    *
00062    */
00063 
00064   forceinline
00065   ProbeEngine::ProbeEngine(Stop* st, size_t sz) 
00066     : EngineCtrl(st,sz) {}
00067 
00068   forceinline void
00069   ProbeEngine::init(Space* s, unsigned int d0) {
00070     cur = s;
00071     d   = d0;
00072   }
00073 
00074   forceinline void
00075   ProbeEngine::reset(Space* s, unsigned int d0) {
00076     delete cur;
00077     assert(ds.empty());
00078     cur = s;
00079     d   = d0;
00080     EngineCtrl::reset(s);
00081   }
00082 
00083   forceinline size_t
00084   ProbeEngine::stacksize(void) const {
00085     return ds.size();
00086   }
00087 
00088   forceinline
00089   ProbeEngine::~ProbeEngine(void) {
00090     delete cur;
00091     while (!ds.empty())
00092       delete ds.pop().space();
00093   }
00094 
00095   forceinline Space*
00096   ProbeEngine::explore(void) {
00097     start();
00098     while (true) {
00099       if (stop(stacksize()))
00100         return NULL;
00101       if (cur == NULL) {
00102       backtrack:
00103         if (ds.empty())
00104           return NULL;
00105         unsigned int a = ds.top().alt();
00106         if (a == 0) {
00107           cur = ds.pop().space();
00108           EngineCtrl::pop(cur);
00109         } else {
00110           ds.top().alt(a-1);
00111           cur = ds.top().space()->clone();
00112           clone++;
00113         }
00114         cur->commit(a,NULL,propagate);
00115         EngineCtrl::current(cur);
00116         d++;
00117       }
00118     check_discrepancy:
00119       if (d == 0) {
00120         Space* s = cur;
00121         unsigned int alt;
00122         while (s->status(alt) == SS_BRANCH) {
00123           if (stop(stacksize()))
00124             return NULL;
00125           s->commit(0,NULL,propagate);
00126         }
00127         cur = NULL;
00128         EngineCtrl::current(NULL);
00129         if (s->failed()) {
00130           delete s;
00131           goto backtrack;
00132         }
00133         return s;
00134       }
00135       unsigned int alt;
00136       switch (cur->status(alt,propagate)) {
00137       case SS_FAILED:
00138         fail++;
00139       case SS_SOLVED:   
00140         delete cur;
00141         cur = NULL;
00142         EngineCtrl::current(NULL);
00143         goto backtrack;
00144       case SS_BRANCH:
00145         {
00146           if (alt > 1) {
00147             unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00148             Space* cc = cur->clone();
00149             EngineCtrl::push(cc);
00150             ProbeNode sn(cc,d_a-1);
00151             clone++;
00152             ds.push(sn);
00153             cur->commit(d_a,NULL,propagate);
00154             d -= d_a;
00155           } else {
00156             cur->commit(0,NULL,propagate);
00157           }
00158           commit++;
00159           goto check_discrepancy;
00160         }
00161       }
00162     }
00163   }
00164 
00165 
00166   /*
00167    * The LDS engine proper (_LDS means: all the logic but just
00168    * for space, type casts are done in LDS)
00169    *
00170    */
00171 
00172   LDS::LDS(Space* s, unsigned int d, Stop* st, size_t sz)
00173     : d_cur(0), d_max(d), no_solution(true), e(st,sz) {
00174     unsigned int alt;
00175     if (s->status(alt) == SS_FAILED) {
00176       root = NULL;
00177       e.init(NULL,0);
00178       e.fail += 1;
00179       e.current(s);
00180     } else {
00181       root = s;
00182       Space* c = (d_max == 0) ? s : s->clone();
00183       e.init(c,0);
00184       e.current(s);
00185       e.current(NULL);
00186       e.current(c);
00187     }
00188   }
00189 
00190   LDS::~LDS(void) {
00191     delete root;
00192   }
00193 
00194   Space*
00195   LDS::next(void) {
00196     while (true) {
00197       Space* s = e.explore();
00198       if (s != NULL) {
00199         no_solution = false;
00200         return s;
00201       }
00202       if (no_solution || (++d_cur > d_max))
00203         break;
00204       no_solution = true;
00205       if (d_cur == d_max) {
00206         e.reset(root,d_cur);
00207         root = NULL;
00208       } else {
00209         e.clone++;
00210         e.reset(root->clone(),d_cur);
00211       }
00212     }
00213     return NULL;
00214   }
00215 
00216   bool
00217   LDS::stopped(void) const {
00218     return e.stopped();
00219   }
00220 
00221   Statistics
00222   LDS::statistics(void) const {
00223     Statistics s = e;
00224     s.memory += e.stacksize();
00225     return e;
00226   }
00227 
00228 }}
00229 
00230 // STATISTICS: search-any