pbs.hpp
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 #include <climits>
00039
00040 namespace Gecode { namespace Search { namespace Meta { namespace Sequential {
00041
00042
00043 forceinline
00044 PortfolioStop::PortfolioStop(Stop* so0)
00045 : so(so0) {}
00046 forceinline void
00047 PortfolioStop::share(SharedStopInfo* ssi0) {
00048 ssi = ssi0;
00049 }
00050
00051
00052 forceinline void
00053 Slave::init(Engine* e, Stop* s) {
00054 slave = e; stop = s;
00055 }
00056 forceinline Space*
00057 Slave::next(void) {
00058 return slave->next();
00059 }
00060 forceinline Statistics
00061 Slave::statistics(void) const {
00062 return slave->statistics();
00063 }
00064 forceinline bool
00065 Slave::stopped(void) const {
00066 return slave->stopped();
00067 }
00068 forceinline void
00069 Slave::constrain(const Space& b) {
00070 slave->constrain(b);
00071 }
00072 forceinline
00073 Slave::~Slave(void) {
00074 delete slave;
00075 delete stop;
00076 }
00077
00078
00079 template<bool best>
00080 forceinline
00081 PBS<best>::PBS(Engine** e, Stop** s, unsigned int n,
00082 const Statistics& stat0,
00083 const Search::Options& opt)
00084 : stat(stat0), slice(opt.slice),
00085 slaves(heap.alloc<Slave>(n)), n_slaves(n), cur(0),
00086 slave_stop(false) {
00087 ssi.done = false;
00088 ssi.l = opt.slice;
00089 for (unsigned int i=n; i--; ) {
00090 slaves[i].init(e[i],static_cast<PortfolioStop*>(s[i]));
00091 static_cast<PortfolioStop*>(s[i])->share(&ssi);
00092 }
00093 }
00094
00095 template<bool best>
00096 Space*
00097 PBS<best>::next(void) {
00098 slave_stop = false;
00099 unsigned int n_exhausted = 0;
00100 while (n_slaves > 0) {
00101 if (Space* s = slaves[cur].next()) {
00102
00103 if (best) {
00104 for (unsigned int i=0; i<cur; i++)
00105 slaves[i].constrain(*s);
00106 for (unsigned int i=cur+1; i<n_slaves; i++)
00107 slaves[i].constrain(*s);
00108 }
00109 return s;
00110 }
00111 if (slaves[cur].stopped()) {
00112 if (ssi.done) {
00113 cur++; n_exhausted++;
00114 } else {
00115 slave_stop = true;
00116 return NULL;
00117 }
00118 } else {
00119
00120 stat += slaves[cur].statistics();
00121 slaves[cur].~Slave();
00122 slaves[cur] = slaves[--n_slaves];
00123 if (n_slaves == 1)
00124
00125 ssi.l = ULONG_MAX;
00126 }
00127 if (n_exhausted == n_slaves) {
00128 n_exhausted = 0;
00129
00130 ssi.l += slice;
00131 }
00132 if (cur == n_slaves)
00133 cur = 0;
00134 }
00135 return NULL;
00136 }
00137
00138 template<bool best>
00139 bool
00140 PBS<best>::stopped(void) const {
00141 return slave_stop;
00142 }
00143
00144 template<bool best>
00145 Statistics
00146 PBS<best>::statistics(void) const {
00147 Statistics s(stat);
00148 for (unsigned int i=n_slaves; i--; )
00149 s += slaves[i].statistics();
00150 return s;
00151 }
00152
00153 template<bool best>
00154 void
00155 PBS<best>::constrain(const Space& b) {
00156 if (!best)
00157 throw NoBest("PBS::constrain");
00158 for (unsigned int i=0; i<n_slaves; i++)
00159 slaves[i].constrain(b);
00160 }
00161
00162 template<bool best>
00163 PBS<best>::~PBS(void) {
00164 for (unsigned int i=n_slaves; i--; )
00165 slaves[i].~Slave();
00166
00167 heap.rfree(slaves);
00168 }
00169
00170 }}}}
00171
00172