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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
00039 #define __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/sequential/path.hh>
00045
00046 namespace Gecode { namespace Search { namespace Sequential {
00047
00049 class DFS : public Worker {
00050 private:
00052 Options opt;
00054 Path path;
00056 Space* cur;
00058 unsigned int d;
00059 public:
00061 DFS(Space* s, const Options& o);
00063 Space* next(void);
00065 Statistics statistics(void) const;
00067 void reset(Space* s);
00069 NoGoods& nogoods(void);
00071 ~DFS(void);
00072 };
00073
00074 forceinline
00075 DFS::DFS(Space* s, const Options& o)
00076 : opt(o), path(static_cast<int>(opt.nogoods_limit)), d(0) {
00077 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00078 fail++;
00079 cur = NULL;
00080 if (!opt.clone)
00081 delete s;
00082 } else {
00083 cur = snapshot(s,opt);
00084 }
00085 }
00086
00087 forceinline void
00088 DFS::reset(Space* s) {
00089 delete cur;
00090 path.reset();
00091 d = 0;
00092 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00093 cur = NULL;
00094 } else {
00095 cur = s;
00096 }
00097 Worker::reset();
00098 }
00099
00100 forceinline NoGoods&
00101 DFS::nogoods(void) {
00102 return path;
00103 }
00104
00105 forceinline Space*
00106 DFS::next(void) {
00107 start();
00108 while (true) {
00109 while (cur) {
00110 if (stop(opt))
00111 return NULL;
00112 node++;
00113 switch (cur->status(*this)) {
00114 case SS_FAILED:
00115 fail++;
00116 delete cur;
00117 cur = NULL;
00118 break;
00119 case SS_SOLVED:
00120 {
00121
00122 (void) cur->choice();
00123 Space* s = cur;
00124 cur = NULL;
00125 return s;
00126 }
00127 case SS_BRANCH:
00128 {
00129 Space* c;
00130 if ((d == 0) || (d >= opt.c_d)) {
00131 c = cur->clone();
00132 d = 1;
00133 } else {
00134 c = NULL;
00135 d++;
00136 }
00137 const Choice* ch = path.push(*this,cur,c);
00138 cur->commit(*ch,0);
00139 break;
00140 }
00141 default:
00142 GECODE_NEVER;
00143 }
00144 }
00145 do {
00146 if (!path.next())
00147 return NULL;
00148 cur = path.recompute(d,opt.a_d,*this);
00149 } while (cur == NULL);
00150 }
00151 GECODE_NEVER;
00152 return NULL;
00153 }
00154
00155 forceinline Statistics
00156 DFS::statistics(void) const {
00157 return *this;
00158 }
00159
00160 forceinline
00161 DFS::~DFS(void) {
00162 delete cur;
00163 path.reset();
00164 }
00165
00166 }}}
00167
00168 #endif
00169
00170