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

bab-reco.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-28 14:06:57 +0200 (Sun, 28 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2243 $
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 
00023 
00024 #include "search/bab-reco.hh"
00025 
00026 namespace Gecode { namespace Search {
00027 
00028   /*
00029    * The invarinat maintained by the engine is:
00030    *   For all nodes stored at a depth less than mark, there
00031    *   is no guarantee of betterness. For those above the mark,
00032    *   betterness is guaranteed.
00033    *
00034    * The engine maintains the path on the stack for the current
00035    * node to be explored.
00036    *
00037    */
00038 
00039   BabReCoEngine::~BabReCoEngine(void) {
00040     ds.reset();
00041     delete best;
00042     delete cur;
00043   }
00044 
00045   size_t
00046   BabReCoEngine::stacksize(void) const {
00047     return ds.size();
00048   }
00049 
00050   bool
00051   BabReCoEngine::explore(Space*& s1, Space*& s2) {
00052     /*
00053      * Upon entry, cur can be either NULL (after a solution
00054      * has been returned) or set to a space that has been
00055      * requested to be constrained.
00056      * When a solution is found, the solution is returned in s1
00057      * and true is returned.
00058      * When a space is requested to be constrained, the space
00059      * to be constrained is returned in s1 and s2 refers to the
00060      * currently best solution. In this case false is returned.
00061      *
00062      */
00063     while (true) {
00064       if (cur == NULL) {
00065         if (!ds.next(*this)) {
00066           s1 = NULL;
00067           return true;
00068         }
00069         cur = ds.recompute(d,*this);
00070         FullStatistics::current(cur);
00071         if (ds.entries() <= mark) {
00072           // Next space needs to be constrained
00073           mark = ds.entries();
00074           d  = 0; // Force copy!
00075           s1 = cur;
00076           s2 = best;
00077           return false;
00078         }
00079       }
00080       unsigned int alt;
00081       switch (cur->status(alt,propagate)) {
00082       case SS_FAILED:
00083         fail++;
00084         delete cur;
00085         cur = NULL;
00086         FullStatistics::current(NULL);
00087         break;
00088       case SS_SOLVED:
00089         delete best;
00090         best = cur;
00091         mark = ds.entries();
00092         s1 = best->clone();
00093         clone++;
00094         cur = NULL;
00095         FullStatistics::current(NULL);
00096         return true;
00097       case SS_BRANCH:
00098         {
00099           Space* c;
00100           if ((d == 0) || (d >= c_d)) {
00101             c = cur->clone();
00102             clone++;
00103             d = 1;
00104           } else {
00105             c = NULL;
00106             if (alt > 1)
00107               d++;
00108           }
00109           BranchingDesc* desc = ds.push(cur,c,alt);
00110           FullStatistics::push(c,desc);
00111           cur->commit(0,desc,propagate);
00112           commit++;
00113           break;
00114         }
00115       }
00116     }
00117     return true;
00118   }
00119 
00120 }}
00121         
00122 // STATISTICS: search-any