Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

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: 2005-08-10 20:28:01 +0200 (Wed, 10 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2202 $
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 "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::Node::Node(Space* s, unsigned int a)
00034     : _space(s), _alt(a) {}
00035 
00036   forceinline Space*
00037   ProbeEngine::Node::space(void) const {
00038     return _space;
00039   }
00040 
00041   forceinline void
00042   ProbeEngine::Node::space(Space* s) {
00043     _space = s;
00044   }
00045 
00046   forceinline unsigned int
00047   ProbeEngine::Node::alt(void) const {
00048     return _alt;
00049   }
00050 
00051   forceinline void
00052   ProbeEngine::Node::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(size_t sz) 
00066     : FullStatistics(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     FullStatistics::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     while (true) {
00098       if (cur == NULL) {
00099       backtrack:
00100         if (ds.empty())
00101           return NULL;
00102         unsigned int a = ds.top().alt();
00103         if (a == 0) {
00104           cur = ds.pop().space();
00105           FullStatistics::pop(cur);
00106         } else {
00107           ds.top().alt(a-1);
00108           cur = ds.top().space()->clone();
00109           clone++;
00110         }
00111         cur->commit(a,NULL,propagate);
00112         FullStatistics::current(cur);
00113         d++;
00114       }
00115     check_discrepancy:
00116       if (d == 0) {
00117         Space* s = cur;
00118         cur = NULL;
00119         FullStatistics::current(NULL);
00120         unsigned int alt;
00121         while (s->status(alt) == SS_BRANCH)
00122           s->commit(0,NULL,propagate);
00123         if (s->failed()) {
00124           delete s;
00125           goto backtrack;
00126         }
00127         return s;
00128       }
00129       unsigned int alt;
00130       switch (cur->status(alt,propagate)) {
00131       case SS_FAILED:
00132         fail++;
00133       case SS_SOLVED:   
00134         delete cur;
00135         cur = NULL;
00136         FullStatistics::current(NULL);
00137         goto backtrack;
00138       case SS_BRANCH:
00139         {
00140           if (alt > 1) {
00141             unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00142             Space* cc = cur->clone();
00143             FullStatistics::push(cc);
00144             Node sn(cc,d_a-1);
00145             clone++;
00146             ds.push(sn);
00147             cur->commit(d_a,NULL,propagate);
00148             d -= d_a;
00149           } else {
00150             cur->commit(0,NULL,propagate);
00151           }
00152           commit++;
00153           goto check_discrepancy;
00154         }
00155       }
00156     }
00157   }
00158 
00159 
00160   /*
00161    * The LDS engine proper (_LDS means: all the logic but just
00162    * for space, type casts are done in LDS)
00163    *
00164    */
00165 
00166   LDS::LDS(Space* s, unsigned int d, size_t sz)
00167     : d_cur(0), d_max(d), no_solution(true), e(sz) {
00168     unsigned int alt;
00169     if (s->status(alt) == SS_FAILED) {
00170       root = NULL;
00171       e.init(NULL,0);
00172       e.fail += 1;
00173       e.current(s);
00174     } else {
00175       root = s;
00176       Space* c = (d_max == 0) ? s : s->clone();
00177       e.init(c,0);
00178       e.current(s);
00179       e.current(NULL);
00180       e.current(c);
00181     }
00182   }
00183 
00184   LDS::~LDS(void) {
00185     delete root;
00186   }
00187 
00188   Space*
00189   LDS::next(void) {
00190     while (true) {
00191       Space* s = e.explore();
00192       if (s != NULL) {
00193         no_solution = false;
00194         return s;
00195       }
00196       if (no_solution || (++d_cur > d_max))
00197         break;
00198       no_solution = true;
00199       if (d_cur == d_max) {
00200         e.reset(root,d_cur);
00201         root = NULL;
00202       } else {
00203         e.clone++;
00204         e.reset(root->clone(),d_cur);
00205       }
00206     }
00207     return NULL;
00208   }
00209 
00210   Statistics
00211   LDS::statistics(void) const {
00212     Statistics s = e;
00213     s.memory += e.stacksize();
00214     return e;
00215   }
00216 
00217 }}
00218 
00219 // STATISTICS: search-any