bab.cc
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 #include "gecode/search.hh"
00023
00024 namespace Gecode { namespace Search {
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 BabEngine::ExploreStatus
00038 BabEngine::explore(Space*& s1, Space*& s2) {
00039 start();
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053 while (true) {
00054 assert((es == ES_SOLUTION) || (cur == NULL));
00055 if (stop(stacksize())) {
00056 s1 = NULL;
00057 return ES_SOLUTION;
00058 }
00059 if (cur == NULL) {
00060 if (es == ES_CONSTRAIN) {
00061 es = ES_SOLUTION;
00062 goto same;
00063 }
00064 do {
00065 if (!rcs.next(*this)) {
00066 s1 = NULL;
00067 return ES_SOLUTION;
00068 }
00069 {
00070 int l = rcs.lc(s1);
00071 if (l < mark) {
00072 es = ES_CONSTRAIN;
00073 mark = l;
00074 s2 = best;
00075 return ES_CONSTRAIN;
00076 }
00077 }
00078 same:
00079 cur = rcs.recompute<true>(d,*this);
00080 } while (cur == NULL);
00081 EngineCtrl::current(cur);
00082 }
00083 switch (cur->status(propagate)) {
00084 case SS_FAILED:
00085 fail++;
00086 delete cur;
00087 cur = NULL;
00088 EngineCtrl::current(NULL);
00089 break;
00090 case SS_SOLVED:
00091 delete best;
00092 best = cur;
00093 mark = rcs.entries();
00094 s1 = best->clone(true,propagate);
00095 clone++;
00096 cur = NULL;
00097 EngineCtrl::current(NULL);
00098 return ES_SOLUTION;
00099 case SS_BRANCH:
00100 {
00101 Space* c;
00102 if ((d == 0) || (d >= c_d)) {
00103 c = cur->clone(true,propagate);
00104 clone++;
00105 d = 1;
00106 } else {
00107 c = NULL;
00108 d++;
00109 }
00110 const BranchingDesc* desc = rcs.push(cur,c);
00111 EngineCtrl::push(c,desc);
00112 cur->commit(desc,0);
00113 commit++;
00114 break;
00115 }
00116 default:
00117 GECODE_NEVER;
00118 }
00119 }
00120 return ES_SOLUTION;
00121 }
00122
00123
00124
00125
00126 BAB::BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz)
00127 : e(c_d,a_d,st,sz) {
00128 unsigned long int p = 0;
00129 Space* c = (s->status(p) == SS_FAILED) ? NULL : s->clone(true,p);
00130 e.init(c);
00131 e.propagate += p;
00132 e.current(s);
00133 e.current(NULL);
00134 e.current(c);
00135 if (c == NULL)
00136 e.fail += 1;
00137 }
00138
00139 bool
00140 BAB::stopped(void) const {
00141 return e.stopped();
00142 }
00143
00144 Statistics
00145 BAB::statistics(void) const {
00146 Statistics s = e;
00147 s.memory += e.stacksize();
00148 return s;
00149 }
00150
00151 }}
00152
00153