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, 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 current(s);
00082 if (s->status(*this) == SS_FAILED) {
00083 fail++;
00084 cur = NULL;
00085 if (!o.clone)
00086 delete s;
00087 } else {
00088 cur = snapshot(s,opt);
00089 }
00090 current(NULL);
00091 current(cur);
00092 }
00093
00094 forceinline Space*
00095 BAB::next(void) {
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106 start();
00107 while (true) {
00108 while (cur) {
00109 if (stop(opt,path.size()))
00110 return NULL;
00111 node++;
00112 switch (cur->status(*this)) {
00113 case SS_FAILED:
00114 fail++;
00115 delete cur;
00116 cur = NULL;
00117 Worker::current(NULL);
00118 break;
00119 case SS_SOLVED:
00120
00121 (void) cur->choice();
00122 delete best;
00123 best = cur;
00124 cur = NULL;
00125 mark = path.entries();
00126 Worker::current(NULL);
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 Worker::push(c,ch);
00140 cur->commit(*ch,0);
00141 break;
00142 }
00143 default:
00144 GECODE_NEVER;
00145 }
00146 }
00147
00148 do {
00149 if (!path.next(*this))
00150 return NULL;
00151 cur = path.recompute(d,opt.a_d,*this,best,mark);
00152 } while (cur == NULL);
00153 Worker::current(cur);
00154 }
00155 GECODE_NEVER;
00156 return NULL;
00157 }
00158
00159 forceinline Statistics
00160 BAB::statistics(void) const {
00161 Statistics s = *this;
00162 s.memory += path.size();
00163 return s;
00164 }
00165
00166 forceinline
00167 BAB::~BAB(void) {
00168 path.reset();
00169 delete best;
00170 delete cur;
00171 }
00172
00173 }}}
00174
00175 #endif
00176
00177