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

bab-copy.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Bugfixes provided by:
00006  *     Grégoire Dooms <dooms@info.ucl.ac.be>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2005-08-09 21:44:53 +0200 (Tue, 09 Aug 2005) $ by $Author: schulte $
00013  *     $Revision: 2192 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  See the file "LICENSE" for information on usage and
00020  *  redistribution of this file, and for a
00021  *     DISCLAIMER OF ALL WARRANTIES.
00022  *
00023  */
00024 
00025 #include "search/bab-copy.hh"
00026 
00027 namespace Gecode { namespace Search {
00028 
00029   /*
00030    * The invarinat maintained by the engine is:
00031    *   For all nodes stored at a depth less than mark, there
00032    *   is no guarantee of betterness. For those above the mark,
00033    *   betterness is guaranteed.
00034    *
00035    * The engine maintains the path on the stack for the next
00036    * node to be explored.
00037    *
00038    */
00039 
00040   BabCopyEngine::~BabCopyEngine(void) {
00041     ds.reset();
00042     delete b;
00043     delete cur;
00044   }
00045 
00046   size_t
00047   BabCopyEngine::stacksize(void) const {
00048     return ds.size();
00049   }
00050 
00051   bool
00052   BabCopyEngine::explore(Space*& s1, Space*& s2) {
00053     /*
00054      * Upon entry, cur can be either NULL (after a solution
00055      * has been returned) or set to a space that has been
00056      * requested to be constrained.
00057      * When a solution is found, the solution is returned in s1
00058      * and true is returned.
00059      * When a space is requested to be constrained, the space
00060      * to be constrained is returned in s1 and s2 refers to the
00061      * currently best solution. In this case false is returned.
00062      *
00063      */
00064     while (true) {
00065       if (cur == NULL) {
00066       backtrack:
00067         if (ds.empty()) {
00068           s1 = NULL;
00069           return true;
00070         }
00071         // Get the next alternative and space from the stack.
00072         if (ds.top().rightmost()) {
00073           unsigned int alt = ds.top().alt();
00074           cur = ds.pop().space();
00075           FullStatistics::pop(cur);
00076           cur->commit(alt,NULL,propagate);
00077           FullStatistics::current(cur);
00078           commit++;
00079           // Next space needs to be constrained?
00080           if (ds.entries()+1 <= mark) {
00081             mark--;
00082             s1 = cur;
00083             s2 = b;
00084             return false;
00085           }
00086         } else {
00087           cur = ds.top().space()->clone(true,propagate);
00088           cur->commit(ds.top().alt(),NULL,propagate);
00089           FullStatistics::current(cur);
00090           ds.top().next();
00091           clone++; commit++;
00092           // Next space needs to be constrained?
00093           if (ds.entries() <= mark) {
00094             s1 = cur;
00095             s2 = b;
00096             return false;
00097           }
00098         }
00099       }
00100       while (true) {
00101         unsigned int alt;
00102         switch (cur->status(alt,propagate)) {
00103         case SS_FAILED:
00104           fail++;
00105           delete cur;
00106           cur = NULL;
00107           FullStatistics::current(NULL);
00108           goto backtrack;
00109         case SS_SOLVED:
00110           delete b;
00111           b = cur;
00112           mark = ds.entries();
00113           s1 = b->clone(true,propagate);
00114           cur = NULL;
00115           FullStatistics::current(NULL);
00116           return true;
00117         case SS_BRANCH:
00118           if (alt > 1) {
00119             clone++;
00120             ds.push(cur,alt);
00121             FullStatistics::push(ds.top().space());
00122           }
00123           commit++;
00124           cur->commit(0,NULL,propagate);
00125           break;
00126         }
00127       }
00128     }
00129     return true;
00130   }
00131 
00132 }}
00133         
00134 // STATISTICS: search-any