bab.hh
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 constrain(const Space& b);
00077 void reset(Space* s);
00079 NoGoods& nogoods(void);
00081 ~BAB(void);
00082 };
00083
00084 forceinline
00085 BAB::BAB(Space* s, const Options& o)
00086 : opt(o), path(opt.nogoods_limit), d(0), mark(0), best(NULL) {
00087 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00088 fail++;
00089 cur = NULL;
00090 if (!o.clone)
00091 delete s;
00092 } else {
00093 cur = snapshot(s,opt);
00094 }
00095 }
00096
00097 forceinline Space*
00098 BAB::next(void) {
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115 start();
00116 while (true) {
00117 if (stop(opt))
00118 return NULL;
00119
00120 while (cur == NULL) {
00121 if (path.empty())
00122 return NULL;
00123 cur = path.recompute(d,opt.a_d,*this,*best,mark);
00124 if (cur != NULL)
00125 break;
00126 path.next();
00127 }
00128 node++;
00129 switch (cur->status(*this)) {
00130 case SS_FAILED:
00131 fail++;
00132 delete cur;
00133 cur = NULL;
00134 path.next();
00135 break;
00136 case SS_SOLVED:
00137
00138 (void) cur->choice();
00139 delete best;
00140 best = cur;
00141 cur = NULL;
00142 path.next();
00143 mark = path.entries();
00144 return best->clone();
00145 case SS_BRANCH:
00146 {
00147 Space* c;
00148 if ((d == 0) || (d >= opt.c_d)) {
00149 c = cur->clone();
00150 d = 1;
00151 } else {
00152 c = NULL;
00153 d++;
00154 }
00155 const Choice* ch = path.push(*this,cur,c);
00156 cur->commit(*ch,0);
00157 break;
00158 }
00159 default:
00160 GECODE_NEVER;
00161 }
00162 }
00163 GECODE_NEVER;
00164 return NULL;
00165 }
00166
00167 forceinline Statistics
00168 BAB::statistics(void) const {
00169 return *this;
00170 }
00171
00172 forceinline void
00173 BAB::constrain(const Space& b) {
00174 if (best != NULL) {
00175
00176 best->constrain(b);
00177 if (best->status(*this) != SS_FAILED)
00178 return;
00179 else
00180 delete best;
00181 }
00182 best = b.clone();
00183 if (cur != NULL)
00184 cur->constrain(b);
00185 mark = path.entries();
00186 }
00187
00188 forceinline void
00189 BAB::reset(Space* s) {
00190 delete best;
00191 best = NULL;
00192 path.reset();
00193 d = 0;
00194 mark = 0;
00195 delete cur;
00196 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00197 delete s;
00198 cur = NULL;
00199 } else {
00200 cur = s;
00201 }
00202 Worker::reset();
00203 }
00204
00205 forceinline NoGoods&
00206 BAB::nogoods(void) {
00207 return path;
00208 }
00209
00210 forceinline
00211 BAB::~BAB(void) {
00212 path.reset();
00213 delete best;
00214 delete cur;
00215 }
00216
00217 }}}
00218
00219 #endif
00220
00221