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 bool
00038 BabEngine::explore(Space*& s1, Space*& s2) {
00039 start();
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051 while (true) {
00052 if (stop(stacksize())) {
00053 s1 = NULL;
00054 return true;
00055 }
00056 if (cur == NULL) {
00057 if (!ds.next(*this)) {
00058 s1 = NULL;
00059 return true;
00060 }
00061 cur = ds.recompute(d,*this);
00062 EngineCtrl::current(cur);
00063 if (ds.entries() <= mark) {
00064
00065 mark = ds.entries();
00066 d = 0;
00067 s1 = cur;
00068 s2 = best;
00069 return false;
00070 }
00071 }
00072 unsigned int alt;
00073 switch (cur->status(alt,propagate)) {
00074 case SS_FAILED:
00075 fail++;
00076 delete cur;
00077 cur = NULL;
00078 EngineCtrl::current(NULL);
00079 break;
00080 case SS_SOLVED:
00081 delete best;
00082 best = cur;
00083 mark = ds.entries();
00084 s1 = best->clone();
00085 clone++;
00086 cur = NULL;
00087 EngineCtrl::current(NULL);
00088 return true;
00089 case SS_BRANCH:
00090 {
00091 Space* c;
00092 if ((d == 0) || (d >= c_d)) {
00093 c = cur->clone();
00094 clone++;
00095 d = 1;
00096 } else {
00097 c = NULL;
00098 if (alt > 1)
00099 d++;
00100 }
00101 BranchingDesc* desc = ds.push(cur,c,alt);
00102 EngineCtrl::push(c,desc);
00103 cur->commit(0,desc,propagate);
00104 commit++;
00105 break;
00106 }
00107 }
00108 }
00109 return true;
00110 }
00111
00112
00113
00114
00115 BAB::BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz)
00116 : e(c_d,a_d,st,sz) {
00117 unsigned int alt;
00118 unsigned long int p = 0;
00119 Space* c = (s->status(alt,p) == SS_FAILED) ? NULL : s->clone();
00120 e.init(c);
00121 e.propagate += p;
00122 e.current(s);
00123 e.current(NULL);
00124 e.current(c);
00125 if (c == NULL)
00126 e.fail += 1;
00127 }
00128
00129 bool
00130 BAB::stopped(void) const {
00131 return e.stopped();
00132 }
00133
00134 Statistics
00135 BAB::statistics(void) const {
00136 Statistics s = e;
00137 s.memory += e.stacksize();
00138 return s;
00139 }
00140
00141 }}
00142
00143