Generated on Mon May 10 06:46:44 2010 for Gecode by doxygen 1.6.3

bab.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Guido Tack <tack@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2004
00011  *     Guido Tack, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2009-08-26 21:10:00 +0200 (Wed, 26 Aug 2009) $ by $Author: schulte $
00015  *     $Revision: 9632 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #ifndef __GECODE_SEARCH_SEQUENTIAL_BAB_HH__
00043 #define __GECODE_SEARCH_SEQUENTIAL_BAB_HH__
00044 
00045 #include <gecode/search.hh>
00046 #include <gecode/search/support.hh>
00047 #include <gecode/search/worker.hh>
00048 #include <gecode/search/sequential/path.hh>
00049 
00050 namespace Gecode { namespace Search { namespace Sequential {
00051 
00053   class BAB : public Worker {
00054   private:
00056     Options opt;
00058     Path path;
00060     Space* cur;
00062     unsigned int d;
00064     int mark;
00066     Space* best;
00067   public:
00069     BAB(Space* s, size_t sz, const Options& o);
00071     Space* next(void);
00073     Statistics statistics(void) const;
00075     ~BAB(void);
00076   };
00077 
00078   forceinline 
00079   BAB::BAB(Space* s, size_t sz, const Options& o)
00080     : Worker(sz), opt(o), d(0), mark(0), best(NULL) {
00081     cur = (s->status(*this) == SS_FAILED) ? NULL : snapshot(s,opt);
00082     current(s);
00083     current(NULL);
00084     current(cur);
00085     if (cur == NULL)
00086       fail++;
00087   }
00088 
00089   forceinline Space*
00090   BAB::next(void) {
00091     /*
00092      * The invariant maintained by the engine is:
00093      *   For all nodes stored at a depth less than mark, there
00094      *   is no guarantee of betterness. For those above the mark,
00095      *   betterness is guaranteed.
00096      *
00097      * The engine maintains the path on the stack for the current
00098      * node to be explored.
00099      *
00100      */
00101     start();
00102     while (true) {
00103       while (cur) {
00104         if (stop(opt,path.size()))
00105           return NULL;
00106         node++;
00107         switch (cur->status(*this)) {
00108         case SS_FAILED:
00109           fail++;
00110           delete cur;
00111           cur = NULL;
00112           Worker::current(NULL);
00113           break;
00114         case SS_SOLVED:
00115           // Deletes all pending branchers
00116           (void) cur->choice();
00117           delete best;
00118           best = cur;
00119           cur = NULL;
00120           mark = path.entries();
00121           Worker::current(NULL);
00122           return best->clone();
00123         case SS_BRANCH:
00124           {
00125             Space* c;
00126             if ((d == 0) || (d >= opt.c_d)) {
00127               c = cur->clone();
00128               d = 1;
00129             } else {
00130               c = NULL;
00131               d++;
00132             }
00133             const Choice* ch = path.push(*this,cur,c);
00134             Worker::push(c,ch);
00135             cur->commit(*ch,0);
00136             break;
00137           }
00138         default:
00139           GECODE_NEVER;
00140         }
00141       }
00142       // Recompute and add constraint if necessary
00143       do {
00144         if (!path.next(*this))
00145           return NULL;
00146         cur = path.recompute(d,opt.a_d,*this,best,mark);
00147       } while (cur == NULL);
00148       Worker::current(cur);
00149     }
00150     GECODE_NEVER;
00151     return NULL;
00152   }
00153 
00154   forceinline Statistics
00155   BAB::statistics(void) const {
00156     Statistics s = *this;
00157     s.memory += path.size();
00158     return s;
00159   }
00160 
00161   forceinline 
00162   BAB::~BAB(void) {
00163     path.reset();
00164     delete best;
00165     delete cur;
00166   }
00167 
00168 }}}
00169 
00170 #endif
00171 
00172 // STATISTICS: search-sequential