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 "search.hh"
00023
00024 namespace Gecode { namespace Search {
00025
00026
00027
00028
00029
00030
00031
00032 forceinline
00033 ProbeEngine::Node::Node(Space* s, unsigned int a)
00034 : _space(s), _alt(a) {}
00035
00036 forceinline Space*
00037 ProbeEngine::Node::space(void) const {
00038 return _space;
00039 }
00040
00041 forceinline void
00042 ProbeEngine::Node::space(Space* s) {
00043 _space = s;
00044 }
00045
00046 forceinline unsigned int
00047 ProbeEngine::Node::alt(void) const {
00048 return _alt;
00049 }
00050
00051 forceinline void
00052 ProbeEngine::Node::alt(unsigned int a) {
00053 _alt = a;
00054 }
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064 forceinline
00065 ProbeEngine::ProbeEngine(size_t sz)
00066 : FullStatistics(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 FullStatistics::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 while (true) {
00098 if (cur == NULL) {
00099 backtrack:
00100 if (ds.empty())
00101 return NULL;
00102 unsigned int a = ds.top().alt();
00103 if (a == 0) {
00104 cur = ds.pop().space();
00105 FullStatistics::pop(cur);
00106 } else {
00107 ds.top().alt(a-1);
00108 cur = ds.top().space()->clone();
00109 clone++;
00110 }
00111 cur->commit(a,NULL,propagate);
00112 FullStatistics::current(cur);
00113 d++;
00114 }
00115 check_discrepancy:
00116 if (d == 0) {
00117 Space* s = cur;
00118 cur = NULL;
00119 FullStatistics::current(NULL);
00120 unsigned int alt;
00121 while (s->status(alt) == SS_BRANCH)
00122 s->commit(0,NULL,propagate);
00123 if (s->failed()) {
00124 delete s;
00125 goto backtrack;
00126 }
00127 return s;
00128 }
00129 unsigned int alt;
00130 switch (cur->status(alt,propagate)) {
00131 case SS_FAILED:
00132 fail++;
00133 case SS_SOLVED:
00134 delete cur;
00135 cur = NULL;
00136 FullStatistics::current(NULL);
00137 goto backtrack;
00138 case SS_BRANCH:
00139 {
00140 if (alt > 1) {
00141 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
00142 Space* cc = cur->clone();
00143 FullStatistics::push(cc);
00144 Node sn(cc,d_a-1);
00145 clone++;
00146 ds.push(sn);
00147 cur->commit(d_a,NULL,propagate);
00148 d -= d_a;
00149 } else {
00150 cur->commit(0,NULL,propagate);
00151 }
00152 commit++;
00153 goto check_discrepancy;
00154 }
00155 }
00156 }
00157 }
00158
00159
00160
00161
00162
00163
00164
00165
00166 LDS::LDS(Space* s, unsigned int d, size_t sz)
00167 : d_cur(0), d_max(d), no_solution(true), e(sz) {
00168 unsigned int alt;
00169 if (s->status(alt) == SS_FAILED) {
00170 root = NULL;
00171 e.init(NULL,0);
00172 e.fail += 1;
00173 e.current(s);
00174 } else {
00175 root = s;
00176 Space* c = (d_max == 0) ? s : s->clone();
00177 e.init(c,0);
00178 e.current(s);
00179 e.current(NULL);
00180 e.current(c);
00181 }
00182 }
00183
00184 LDS::~LDS(void) {
00185 delete root;
00186 }
00187
00188 Space*
00189 LDS::next(void) {
00190 while (true) {
00191 Space* s = e.explore();
00192 if (s != NULL) {
00193 no_solution = false;
00194 return s;
00195 }
00196 if (no_solution || (++d_cur > d_max))
00197 break;
00198 no_solution = true;
00199 if (d_cur == d_max) {
00200 e.reset(root,d_cur);
00201 root = NULL;
00202 } else {
00203 e.clone++;
00204 e.reset(root->clone(),d_cur);
00205 }
00206 }
00207 return NULL;
00208 }
00209
00210 Statistics
00211 LDS::statistics(void) const {
00212 Statistics s = e;
00213 s.memory += e.stacksize();
00214 return e;
00215 }
00216
00217 }}
00218
00219