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

bab.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-06-05 12:14:42 +0200 (Mon, 05 Jun 2006) $ by $Author: schulte $
00010  *     $Revision: 3264 $
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    * The invariant maintained by the engine is:
00028    *   For all nodes stored at a depth less than mark, there
00029    *   is no guarantee of betterness. For those above the mark,
00030    *   betterness is guaranteed.
00031    *
00032    * The engine maintains the path on the stack for the current
00033    * node to be explored.
00034    *
00035    */
00036 
00037   bool
00038   BabEngine::explore(Space*& s1, Space*& s2) {
00039     start();
00040     /*
00041      * Upon entry, cur can be either NULL (after a solution
00042      * has been returned) or set to a space that has been
00043      * requested to be constrained.
00044      * When a solution is found, the solution is returned in s1
00045      * and true is returned.
00046      * When a space is requested to be constrained, the space
00047      * to be constrained is returned in s1 and s2 refers to the
00048      * currently best solution. In this case false is returned.
00049      *
00050      */
00051     while (true) {
00052       if (stop(stacksize())) {
00053         s1 = NULL;
00054         return true;
00055       }
00056       if (cur == NULL) {
00057         if (!ds.next(*this)) {
00058           s1 = NULL;
00059           return true;
00060         }
00061         cur = ds.recompute(d,*this);
00062         EngineCtrl::current(cur);
00063         if (ds.entries() <= mark) {
00064           // Next space needs to be constrained
00065           mark = ds.entries();
00066           d  = 0; // Force copy!
00067           s1 = cur;
00068           s2 = best;
00069           return false;
00070         }
00071       }
00072       unsigned int alt;
00073       switch (cur->status(alt,propagate)) {
00074       case SS_FAILED:
00075         fail++;
00076         delete cur;
00077         cur = NULL;
00078         EngineCtrl::current(NULL);
00079         break;
00080       case SS_SOLVED:
00081         delete best;
00082         best = cur;
00083         mark = ds.entries();
00084         s1 = best->clone();
00085         clone++;
00086         cur = NULL;
00087         EngineCtrl::current(NULL);
00088         return true;
00089       case SS_BRANCH:
00090         {
00091           Space* c;
00092           if ((d == 0) || (d >= c_d)) {
00093             c = cur->clone();
00094             clone++;
00095             d = 1;
00096           } else {
00097             c = NULL;
00098             if (alt > 1)
00099               d++;
00100           }
00101           BranchingDesc* desc = ds.push(cur,c,alt);
00102           EngineCtrl::push(c,desc);
00103           cur->commit(0,desc,propagate);
00104           commit++;
00105           break;
00106         }
00107       }
00108     }
00109     return true;
00110   }
00111 
00112 
00113 
00114 
00115   BAB::BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz) 
00116     : e(c_d,a_d,st,sz) {
00117     unsigned int alt;
00118     unsigned long int p = 0;
00119     Space* c = (s->status(alt,p) == SS_FAILED) ? NULL : s->clone();
00120     e.init(c);
00121     e.propagate += p;
00122     e.current(s);
00123     e.current(NULL);
00124     e.current(c);
00125     if (c == NULL)
00126       e.fail += 1;
00127   }
00128 
00129   bool
00130   BAB::stopped(void) const {
00131     return e.stopped();
00132   }
00133 
00134   Statistics
00135   BAB::statistics(void) const {
00136     Statistics s = e;
00137     s.memory += e.stacksize();
00138     return s;
00139   }
00140 
00141 }}
00142 
00143 // STATISTICS: search-any