lds.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 forceinline
00033 ProbeEngine::ProbeNode
00034 ::ProbeNode(Space* s, const BranchingDesc* d, unsigned int a)
00035 : _space(s), _desc(d), _alt(a) {}
00036
00037 forceinline Space*
00038 ProbeEngine::ProbeNode::space(void) const {
00039 return _space;
00040 }
00041
00042 forceinline const BranchingDesc*
00043 ProbeEngine::ProbeNode::desc(void) const {
00044 return _desc;
00045 }
00046
00047 forceinline unsigned int
00048 ProbeEngine::ProbeNode::alt(void) const {
00049 return _alt;
00050 }
00051
00052 forceinline void
00053 ProbeEngine::ProbeNode::next(void) {
00054 _alt--;
00055 }
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065 forceinline
00066 ProbeEngine::ProbeEngine(Stop* st, size_t sz)
00067 : EngineCtrl(st,sz) {}
00068
00069 forceinline void
00070 ProbeEngine::init(Space* s, unsigned int d0) {
00071 cur = s;
00072 d = d0;
00073 }
00074
00075 forceinline void
00076 ProbeEngine::reset(Space* s, unsigned int d0) {
00077 delete cur;
00078 assert(ds.empty());
00079 cur = s;
00080 d = d0;
00081 EngineCtrl::reset(s);
00082 }
00083
00084 forceinline size_t
00085 ProbeEngine::stacksize(void) const {
00086 return ds.size();
00087 }
00088
00089 forceinline
00090 ProbeEngine::~ProbeEngine(void) {
00091 delete cur;
00092 while (!ds.empty())
00093 delete ds.pop().space();
00094 }
00095
00096 forceinline Space*
00097 ProbeEngine::explore(void) {
00098 start();
00099 while (true) {
00100 if (stop(stacksize()))
00101 return NULL;
00102 if (cur == NULL) {
00103 backtrack:
00104 if (ds.empty())
00105 return NULL;
00106 unsigned int a = ds.top().alt();
00107 const BranchingDesc* desc = ds.top().desc();
00108 if (a == 0) {
00109 cur = ds.pop().space();
00110 EngineCtrl::pop(cur,desc);
00111 cur->commit(desc,a);
00112 delete desc;
00113 } else {
00114 ds.top().next();
00115 cur = ds.top().space()->clone(true,propagate);
00116 clone++;
00117 cur->commit(desc,a);
00118 }
00119 EngineCtrl::current(cur);
00120 d++;
00121 }
00122 check_discrepancy:
00123 if (d == 0) {
00124 Space* s = cur;
00125 while (s->status(propagate) == SS_BRANCH) {
00126 if (stop(stacksize()))
00127 return NULL;
00128 const BranchingDesc* desc = s->description();
00129 s->commit(desc,0);
00130 delete desc;
00131 }
00132 cur = NULL;
00133 EngineCtrl::current(NULL);
00134 if (s->failed()) {
00135 delete s;
00136 goto backtrack;
00137 }
00138 return s;
00139 }
00140 switch (cur->status(propagate)) {
00141 case SS_FAILED:
00142 fail++;
00143 case SS_SOLVED:
00144 delete cur;
00145 cur = NULL;
00146 EngineCtrl::current(NULL);
00147 goto backtrack;
00148 case SS_BRANCH:
00149 {
00150 const BranchingDesc* desc = cur->description();
00151 unsigned int alt = desc->alternatives();
00152 if (alt > 1) {
00153 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00154 Space* cc = cur->clone(true,propagate);
00155 EngineCtrl::push(cc,desc);
00156 ProbeNode sn(cc,desc,d_a-1);
00157 clone++;
00158 ds.push(sn);
00159 cur->commit(desc,d_a);
00160 d -= d_a;
00161 } else {
00162 cur->commit(desc,0);
00163 delete desc;
00164 }
00165 commit++;
00166 goto check_discrepancy;
00167 }
00168 default: GECODE_NEVER;
00169 }
00170 }
00171 }
00172
00173
00174
00175
00176
00177
00178
00179
00180 LDS::LDS(Space* s, unsigned int d, Stop* st, size_t sz)
00181 : d_cur(0), d_max(d), no_solution(true), e(st,sz) {
00182 if (s->status(e.propagate) == SS_FAILED) {
00183 root = NULL;
00184 e.init(NULL,0);
00185 e.fail += 1;
00186 e.current(s);
00187 } else {
00188 root = s;
00189 Space* c = (d_max == 0) ? s : s->clone(true,e.propagate);
00190 e.init(c,0);
00191 e.current(s);
00192 e.current(NULL);
00193 e.current(c);
00194 }
00195 }
00196
00197 LDS::~LDS(void) {
00198 delete root;
00199 }
00200
00201 Space*
00202 LDS::next(void) {
00203 while (true) {
00204 Space* s = e.explore();
00205 if (s != NULL) {
00206 no_solution = false;
00207 return s;
00208 }
00209 if (no_solution || (++d_cur > d_max))
00210 break;
00211 no_solution = true;
00212 if (d_cur == d_max) {
00213 e.reset(root,d_cur);
00214 root = NULL;
00215 } else {
00216 e.clone++;
00217 e.reset(root->clone(true,e.propagate),d_cur);
00218 }
00219 }
00220 return NULL;
00221 }
00222
00223 bool
00224 LDS::stopped(void) const {
00225 return e.stopped();
00226 }
00227
00228 Statistics
00229 LDS::statistics(void) const {
00230 Statistics s = e;
00231 s.memory += e.stacksize();
00232 return e;
00233 }
00234
00235 }}
00236
00237