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
00039 #include <iostream>
00040 #include <iomanip>
00041
00042 namespace Gecode { namespace Driver {
00043
00048 class Cutoff : public Search::Stop {
00049 private:
00050 Search::NodeStop* ns;
00051 Search::FailStop* fs;
00052 Search::TimeStop* ts;
00053
00054 Cutoff(unsigned int node, unsigned int fail, unsigned int time)
00055 : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00056 fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00057 ts((time > 0) ? new Search::TimeStop(time) : NULL) {}
00058 public:
00060 enum {
00061 SR_NODE = 1 << 0,
00062 SR_FAIL = 1 << 1,
00063 SR_TIME = 1 << 2
00064 };
00066 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00067 return
00068 ((ns != NULL) && ns->stop(s,o)) ||
00069 ((fs != NULL) && fs->stop(s,o)) ||
00070 ((ts != NULL) && ts->stop(s,o));
00071 }
00073 int reason(const Search::Statistics& s, const Search::Options& o) {
00074 return
00075 (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00076 (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00077 (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0);
00078 }
00080 static Search::Stop*
00081 create(unsigned int node, unsigned int fail, unsigned int time) {
00082 if ((node == 0) && (fail == 0) && (time == 0))
00083 return NULL;
00084 else
00085 return new Cutoff(node,fail,time);
00086 }
00088 ~Cutoff(void) {
00089 delete ns; delete fs; delete ts;
00090 }
00091 };
00092
00097 GECODE_DRIVER_EXPORT void
00098 stop(Support::Timer& t, std::ostream& os);
00099
00103 GECODE_DRIVER_EXPORT double
00104 am(double t[], int n);
00105
00109 GECODE_DRIVER_EXPORT double
00110 dev(double t[], int n);
00111
00112 #ifdef GECODE_HAS_GIST
00113
00117 template<class Engine>
00118 class GistEngine {
00119 };
00120
00122 template<typename S>
00123 class GistEngine<DFS<S> > {
00124 public:
00125 static void explore(S* root, const Gist::Options& opt) {
00126 (void) Gist::dfs(root, opt);
00127 }
00128 };
00129
00131 template<typename S>
00132 class GistEngine<LDS<S> > {
00133 public:
00134 static void explore(S* root, const Gist::Options& opt) {
00135 (void) Gist::dfs(root, opt);
00136 }
00137 };
00138
00140 template<typename S>
00141 class GistEngine<BAB<S> > {
00142 public:
00143 static void explore(S* root, const Gist::Options& opt) {
00144 (void) Gist::bab(root, opt);
00145 }
00146 };
00147
00149 template<typename S>
00150 class GistEngine<Restart<S> > {
00151 public:
00152 static void explore(S* root, const Gist::Options& opt) {
00153 (void) Gist::bab(root, opt);
00154 }
00155 };
00156
00157 #endif
00158
00159 template<class Space>
00160 template<class Script, template<class> class Engine, class Options>
00161 void
00162 ScriptBase<Space>::run(const Options& o) {
00163 using namespace std;
00164 try {
00165 switch (o.mode()) {
00166 case SM_GIST:
00167 #ifdef GECODE_HAS_GIST
00168 {
00169 Gist::Print<Script> pi(o.name());
00170 Gist::VarComparator<Script> vc(o.name());
00171 Gist::Options opt;
00172 opt.inspect.click(&pi);
00173 opt.inspect.compare(&vc);
00174 opt.clone = false;
00175 opt.c_d = o.c_d();
00176 opt.a_d = o.a_d();
00177 for (int i=0; o.inspect.click(i) != NULL; i++)
00178 opt.inspect.click(o.inspect.click(i));
00179 for (int i=0; o.inspect.solution(i) != NULL; i++)
00180 opt.inspect.solution(o.inspect.solution(i));
00181 for (int i=0; o.inspect.move(i) != NULL; i++)
00182 opt.inspect.move(o.inspect.move(i));
00183 for (int i=0; o.inspect.compare(i) != NULL; i++)
00184 opt.inspect.compare(o.inspect.compare(i));
00185 Script* s = new Script(o);
00186 (void) GistEngine<Engine<Script> >::explore(s, opt);
00187 }
00188 break;
00189
00190 #endif
00191 case SM_SOLUTION:
00192 {
00193 cout << o.name() << endl;
00194 Support::Timer t;
00195 int i = o.solutions();
00196 t.start();
00197 Script* s = new Script(o);
00198 unsigned int n_p = s->propagators();
00199 unsigned int n_b = s->branchers();
00200 Search::Options so;
00201 so.threads = o.threads();
00202 so.c_d = o.c_d();
00203 so.a_d = o.a_d();
00204 so.stop = Cutoff::create(o.node(),o.fail(), o.time());
00205 so.clone = false;
00206 Engine<Script> e(s,so);
00207 do {
00208 Script* ex = e.next();
00209 if (ex == NULL)
00210 break;
00211 ex->print(std::cout);
00212 delete ex;
00213 } while (--i != 0);
00214 Search::Statistics stat = e.statistics();
00215 cout << endl;
00216 if (e.stopped()) {
00217 cout << "Search engine stopped..." << endl
00218 << "\treason: ";
00219 int r = static_cast<Cutoff*>(so.stop)->reason(stat,so);
00220 if (r & Cutoff::SR_NODE)
00221 cout << "node ";
00222 if (r & Cutoff::SR_FAIL)
00223 cout << "fail ";
00224 if (r & Cutoff::SR_TIME)
00225 cout << "time ";
00226 cout << "limit reached" << endl << endl;
00227 }
00228 cout << "Initial" << endl
00229 << "\tpropagators: " << n_p << endl
00230 << "\tbranchers: " << n_b << endl
00231 << endl
00232 << "Summary" << endl
00233 << "\truntime: ";
00234 stop(t, cout);
00235 cout << endl
00236 << "\tsolutions: "
00237 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00238 << "\tpropagations: " << stat.propagate << endl
00239 << "\tnodes: " << stat.node << endl
00240 << "\tfailures: " << stat.fail << endl
00241 << "\tpeak depth: " << stat.depth << endl
00242 << "\tpeak memory: "
00243 << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00244 << endl;
00245 }
00246 break;
00247 case SM_STAT:
00248 {
00249 cout << o.name() << endl;
00250 Support::Timer t;
00251 int i = o.solutions();
00252 t.start();
00253 Script* s = new Script(o);
00254 unsigned int n_p = s->propagators();
00255 unsigned int n_b = s->branchers();
00256 Search::Options so;
00257 so.clone = false;
00258 so.threads = o.threads();
00259 so.c_d = o.c_d();
00260 so.a_d = o.a_d();
00261 so.stop = Cutoff::create(o.node(),o.fail(), o.time());
00262 Engine<Script> e(s,so);
00263 do {
00264 Script* ex = e.next();
00265 if (ex == NULL)
00266 break;
00267 delete ex;
00268 } while (--i != 0);
00269 Search::Statistics stat = e.statistics();
00270 cout << endl
00271 << "\tpropagators: " << n_p << endl
00272 << "\tbranchers: " << n_b << endl
00273 << "\truntime: ";
00274 stop(t, cout);
00275 cout << endl
00276 << "\tsolutions: "
00277 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00278 << "\tpropagations: " << stat.propagate << endl
00279 << "\tnodes: " << stat.node << endl
00280 << "\tfailures: " << stat.fail << endl
00281 << "\tpeak depth: " << stat.depth << endl
00282 << "\tpeak memory: "
00283 << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00284 << endl;
00285 }
00286 break;
00287 case SM_TIME:
00288 {
00289 cout << o.name() << endl;
00290 Support::Timer t;
00291 double* ts = new double[o.samples()];
00292 for (unsigned int s = o.samples(); s--; ) {
00293 t.start();
00294 for (unsigned int k = o.iterations(); k--; ) {
00295 unsigned int i = o.solutions();
00296 Script* s = new Script(o);
00297 Search::Options so;
00298 so.clone = false;
00299 so.threads = o.threads();
00300 so.c_d = o.c_d();
00301 so.a_d = o.a_d();
00302 so.stop = Cutoff::create(o.node(),o.fail(), o.time());
00303 Engine<Script> e(s,so);
00304 do {
00305 Script* ex = e.next();
00306 if (ex == NULL)
00307 break;
00308 delete ex;
00309 } while (--i != 0);
00310 }
00311 ts[s] = t.stop() / o.iterations();
00312 }
00313 double m = am(ts,o.samples());
00314 double d = dev(ts,o.samples()) * 100.0;
00315 delete [] ts;
00316 cout << "\tRuntime: "
00317 << setw(20) << right
00318 << showpoint << fixed
00319 << setprecision(6) << m << "ms"
00320 << setprecision(2) << " (" << d << "% deviation)"
00321 << endl;
00322 }
00323 break;
00324 }
00325 } catch (Exception e) {
00326 cout << "Exception: " << e.what() << "." << endl
00327 << "Stopping..." << endl;
00328 }
00329 }
00330
00331 }}
00332
00333