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