Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
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, const Options& o);
00071 Space* next(void);
00073 Statistics statistics(void) const;
00075 void reset(Space* s);
00077 NoGoods& nogoods(void);
00079 ~BAB(void);
00080 };
00081
00082 forceinline
00083 BAB::BAB(Space* s, const Options& o)
00084 : opt(o), path(static_cast<int>(opt.nogoods_limit)),
00085 d(0), mark(0), best(NULL) {
00086 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00087 fail++;
00088 cur = NULL;
00089 if (!o.clone)
00090 delete s;
00091 } else {
00092 cur = snapshot(s,opt);
00093 }
00094 }
00095
00096 forceinline Space*
00097 BAB::next(void) {
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108 start();
00109 while (true) {
00110 while (cur) {
00111 if (stop(opt))
00112 return NULL;
00113 node++;
00114 switch (cur->status(*this)) {
00115 case SS_FAILED:
00116 fail++;
00117 delete cur;
00118 cur = NULL;
00119 break;
00120 case SS_SOLVED:
00121
00122 (void) cur->choice();
00123 delete best;
00124 best = cur;
00125 cur = NULL;
00126 mark = path.entries();
00127 return best->clone();
00128 case SS_BRANCH:
00129 {
00130 Space* c;
00131 if ((d == 0) || (d >= opt.c_d)) {
00132 c = cur->clone();
00133 d = 1;
00134 } else {
00135 c = NULL;
00136 d++;
00137 }
00138 const Choice* ch = path.push(*this,cur,c);
00139 cur->commit(*ch,0);
00140 break;
00141 }
00142 default:
00143 GECODE_NEVER;
00144 }
00145 }
00146
00147 do {
00148 if (!path.next())
00149 return NULL;
00150 cur = path.recompute(d,opt.a_d,*this,best,mark);
00151 } while (cur == NULL);
00152 }
00153 GECODE_NEVER;
00154 return NULL;
00155 }
00156
00157 forceinline Statistics
00158 BAB::statistics(void) const {
00159 return *this;
00160 }
00161
00162 forceinline void
00163 BAB::reset(Space* s) {
00164 delete best;
00165 best = NULL;
00166 path.reset();
00167 d = mark = 0U;
00168 delete cur;
00169 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00170 cur = NULL;
00171 } else {
00172 cur = s;
00173 }
00174 Worker::reset();
00175 }
00176
00177 forceinline NoGoods&
00178 BAB::nogoods(void) {
00179 return path;
00180 }
00181
00182 forceinline
00183 BAB::~BAB(void) {
00184 path.reset();
00185 delete best;
00186 delete cur;
00187 }
00188
00189 }}}
00190
00191 #endif
00192
00193