Generated on Sun Feb 17 15:24:28 2019 for Gecode by doxygen 1.6.3

bab.hpp

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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Search { namespace Seq {
00039 
00040   template<class Tracer>
00041   forceinline
00042   BAB<Tracer>::BAB(Space* s, const Options& o)
00043     : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0), mark(0), 
00044       best(NULL) {
00045     if (tracer) {
00046       tracer.engine(SearchTracer::EngineType::BAB, 1U);
00047       tracer.worker();
00048     }
00049     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00050       fail++;
00051       cur = NULL;
00052       if (!o.clone)
00053         delete s;
00054     } else {
00055       cur = snapshot(s,opt);
00056     }
00057   }
00058 
00059   template<class Tracer>
00060   forceinline Space*
00061   BAB<Tracer>::next(void) {
00062     /*
00063      * The engine maintains the following invariant:
00064      *  - If the current space (cur) is not NULL, the path always points
00065      *    to exactly that space.
00066      *  - If the current space (cur) is NULL, the path always points
00067      *    to the next space (if there is any).
00068      *
00069      * This invariant is needed so that no-goods can be extracted properly
00070      * when the engine is stopped or has found a solution.
00071      *
00072      * An additional invariant maintained by the engine is:
00073      *   For all nodes stored at a depth less than mark, there
00074      *   is no guarantee of betterness. For those above the mark,
00075      *   betterness is guaranteed.
00076      *
00077      */
00078     start();
00079     while (true) {
00080       if (stop(opt))
00081         return NULL;
00082       // Recompute and add constraint if necessary
00083       while (cur == NULL) {
00084         if (path.empty())
00085           return NULL;
00086         cur = path.recompute(d,opt.a_d,*this,*best,mark,tracer);
00087         if (cur != NULL)
00088           break;
00089         path.next();
00090       }
00091       node++;
00092       SearchTracer::EdgeInfo ei;
00093       if (tracer && (path.entries() > 0)) {
00094         typename Path<Tracer>::Edge& top = path.top();
00095         ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
00096       }
00097       unsigned int nid = tracer.nid();
00098       switch (cur->status(*this)) {
00099       case SS_FAILED:
00100         if (tracer) {
00101           SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00102                                     tracer.wid(), nid, *cur);
00103           tracer.node(ei,ni);
00104         }
00105         fail++;
00106         delete cur;
00107         cur = NULL;
00108         path.next();
00109         break;
00110       case SS_SOLVED:
00111         {
00112           if (tracer) {
00113             SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
00114                                       tracer.wid(), nid, *cur);
00115             tracer.node(ei,ni);
00116           }
00117           // Deletes all pending branchers
00118           (void) cur->choice();
00119           delete best;
00120           best = cur;
00121           cur = NULL;
00122           path.next();
00123           mark = path.entries();
00124         }
00125         return best->clone();
00126       case SS_BRANCH:
00127         {
00128           Space* c;
00129           if ((d == 0) || (d >= opt.c_d)) {
00130             c = cur->clone();
00131             d = 1;
00132           } else {
00133             c = NULL;
00134             d++;
00135           }
00136           const Choice* ch = path.push(*this,cur,c,nid);
00137           if (tracer) {
00138             SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00139                                       tracer.wid(), nid, *cur, ch);
00140             tracer.node(ei,ni);
00141           }
00142           cur->commit(*ch,0);
00143           break;
00144         }
00145       default:
00146         GECODE_NEVER;
00147       }
00148     }
00149     GECODE_NEVER;
00150     return NULL;
00151   }
00152 
00153   template<class Tracer>
00154   forceinline Statistics
00155   BAB<Tracer>::statistics(void) const {
00156     return *this;
00157   }
00158 
00159   template<class Tracer>
00160   forceinline void
00161   BAB<Tracer>::constrain(const Space& b) {
00162     if (best != NULL) {
00163       // Check whether b is in fact better than best
00164       best->constrain(b);
00165       if (best->status(*this) != SS_FAILED)
00166         return;
00167       else
00168         delete best;
00169     }
00170     best = b.clone();
00171     if (cur != NULL)
00172       cur->constrain(b);
00173     mark = path.entries();
00174   }
00175 
00176   template<class Tracer>
00177   forceinline void
00178   BAB<Tracer>::reset(Space* s) {
00179     tracer.round();
00180     delete best;
00181     best = NULL;
00182     path.reset();
00183     d = 0;
00184     mark = 0;
00185     delete cur;
00186     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00187       delete s;
00188       cur = NULL;
00189     } else {
00190       cur = s;
00191     }
00192     Worker::reset();
00193   }
00194 
00195   template<class Tracer>
00196   forceinline NoGoods&
00197   BAB<Tracer>::nogoods(void) {
00198     return path;
00199   }
00200 
00201   template<class Tracer>
00202   forceinline
00203   BAB<Tracer>::~BAB(void) {
00204     tracer.done();
00205     path.reset();
00206     delete best;
00207     delete cur;
00208   }
00209 
00210 }}}
00211 
00212 // STATISTICS: search-seq