brancher-view.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main author: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2009-10-13 21:12:58 +0200 (Tue, 13 Oct 2009) $ by $Author: schulte $ 00011 * $Revision: 9897 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { 00039 00046 00047 class EmptyViewSelChoice { 00048 public: 00050 size_t size(void) const; 00051 }; 00052 00056 template<class _View> 00057 class ViewSelBase { 00058 public: 00060 typedef _View View; 00062 typedef EmptyViewSelChoice Choice; 00064 ViewSelBase(void); 00066 ViewSelBase(Space& home, const VarBranchOptions& vbo); 00068 EmptyViewSelChoice choice(Space& home); 00070 void commit(Space& home, const EmptyViewSelChoice& c, unsigned a); 00072 void update(Space& home, bool share, ViewSelBase& vs); 00074 void dispose(Space& home); 00075 }; 00076 00080 template<class View> 00081 class ViewSelNone : public ViewSelBase<View> { 00082 public: 00084 ViewSelNone(void); 00086 ViewSelNone(Space& home, const VarBranchOptions& vbo); 00088 ViewSelStatus init(Space& home, View x); 00090 ViewSelStatus select(Space& home, View x); 00091 }; 00092 00096 template<class View> 00097 class ViewSelDegreeMin : public ViewSelBase<View> { 00098 protected: 00100 unsigned int degree; 00101 public: 00103 ViewSelDegreeMin(void); 00105 ViewSelDegreeMin(Space& home, const VarBranchOptions& vbo); 00107 ViewSelStatus init(Space& home, View x); 00109 ViewSelStatus select(Space& home, View x); 00110 }; 00111 00115 template<class View> 00116 class ViewSelDegreeMax : public ViewSelBase<View> { 00117 protected: 00119 unsigned int degree; 00120 public: 00122 ViewSelDegreeMax(void); 00124 ViewSelDegreeMax(Space& home, const VarBranchOptions& vbo); 00126 ViewSelStatus init(Space& home, View x); 00128 ViewSelStatus select(Space& home, View x); 00129 }; 00130 00134 template<class View> 00135 class ViewSelAfcMin : public ViewSelBase<View> { 00136 protected: 00138 double afc; 00139 public: 00141 ViewSelAfcMin(void); 00143 ViewSelAfcMin(Space& home, const VarBranchOptions& vbo); 00145 ViewSelStatus init(Space& home, View x); 00147 ViewSelStatus select(Space& home, View x); 00148 }; 00149 00153 template<class View> 00154 class ViewSelAfcMax : public ViewSelBase<View> { 00155 protected: 00157 double afc; 00158 public: 00160 ViewSelAfcMax(void); 00162 ViewSelAfcMax(Space& home, const VarBranchOptions& vbo); 00164 ViewSelStatus init(Space& home, View x); 00166 ViewSelStatus select(Space& home, View x); 00167 }; 00168 00172 template<class _View> 00173 class ViewSelRnd { 00174 protected: 00176 Support::RandomGenerator r; 00178 unsigned int n; 00179 public: 00181 typedef _View View; 00183 typedef Support::RandomGenerator Choice; 00185 ViewSelRnd(void); 00187 ViewSelRnd(Space& home, const VarBranchOptions& vbo); 00189 ViewSelStatus init(Space& home, _View x); 00191 ViewSelStatus select(Space& home, _View x); 00193 Support::RandomGenerator choice(Space& home); 00195 void commit(Space& home, const Support::RandomGenerator& c, unsigned a); 00197 void update(Space& home, bool share, ViewSelRnd& vs); 00199 void dispose(Space& home); 00200 }; 00202 00203 // Empty view selection choice 00204 forceinline size_t 00205 EmptyViewSelChoice::size(void) const { 00206 return sizeof(EmptyViewSelChoice); 00207 } 00208 00209 // Selection base class 00210 template<class View> 00211 forceinline 00212 ViewSelBase<View>::ViewSelBase(void) {} 00213 template<class View> 00214 forceinline 00215 ViewSelBase<View>::ViewSelBase(Space&, const VarBranchOptions&) {} 00216 template<class View> 00217 forceinline EmptyViewSelChoice 00218 ViewSelBase<View>::choice(Space&) { 00219 EmptyViewSelChoice c; return c; 00220 } 00221 template<class View> 00222 forceinline void 00223 ViewSelBase<View>::commit(Space&, const EmptyViewSelChoice&, unsigned int) {} 00224 template<class View> 00225 forceinline void 00226 ViewSelBase<View>::update(Space&, bool, ViewSelBase<View>&) {} 00227 template<class View> 00228 forceinline void 00229 ViewSelBase<View>::dispose(Space&) {} 00230 00231 00232 // Select first view 00233 template<class View> 00234 forceinline 00235 ViewSelNone<View>::ViewSelNone(void) {} 00236 template<class View> 00237 forceinline 00238 ViewSelNone<View>::ViewSelNone(Space& home, const VarBranchOptions& vbo) 00239 : ViewSelBase<View>(home,vbo) {} 00240 template<class View> 00241 forceinline ViewSelStatus 00242 ViewSelNone<View>::init(Space&, View) { 00243 return VSS_BEST; 00244 } 00245 template<class View> 00246 forceinline ViewSelStatus 00247 ViewSelNone<View>::select(Space&, View) { 00248 return VSS_BEST; 00249 } 00250 00251 00252 // Select variable with smallest degree 00253 template<class View> 00254 forceinline 00255 ViewSelDegreeMin<View>::ViewSelDegreeMin(void) : degree(0U) {} 00256 template<class View> 00257 forceinline 00258 ViewSelDegreeMin<View>::ViewSelDegreeMin(Space& home, 00259 const VarBranchOptions& vbo) 00260 : ViewSelBase<View>(home,vbo), degree(0U) {} 00261 template<class View> 00262 forceinline ViewSelStatus 00263 ViewSelDegreeMin<View>::init(Space&, View x) { 00264 degree = x.degree(); 00265 return (degree == 0) ? VSS_BEST : VSS_BETTER; 00266 } 00267 template<class View> 00268 forceinline ViewSelStatus 00269 ViewSelDegreeMin<View>::select(Space&, View x) { 00270 if (x.degree() < degree) { 00271 degree = x.degree(); 00272 return (degree == 0) ? VSS_BEST : VSS_BETTER; 00273 } else if (x.degree() > degree) { 00274 return VSS_WORSE; 00275 } else { 00276 return VSS_TIE; 00277 } 00278 } 00279 00280 00281 // Select variable with largest degree 00282 template<class View> 00283 forceinline 00284 ViewSelDegreeMax<View>::ViewSelDegreeMax(void) : degree(0) {} 00285 template<class View> 00286 forceinline 00287 ViewSelDegreeMax<View>::ViewSelDegreeMax(Space& home, 00288 const VarBranchOptions& vbo) 00289 : ViewSelBase<View>(home,vbo), degree(0U) {} 00290 template<class View> 00291 forceinline ViewSelStatus 00292 ViewSelDegreeMax<View>::init(Space&, View x) { 00293 degree = x.degree(); 00294 return VSS_BETTER; 00295 } 00296 template<class View> 00297 forceinline ViewSelStatus 00298 ViewSelDegreeMax<View>::select(Space&, View x) { 00299 if (x.degree() > degree) { 00300 degree = x.degree(); 00301 return VSS_BETTER; 00302 } else if (x.degree() < degree) { 00303 return VSS_WORSE; 00304 } else { 00305 return VSS_TIE; 00306 } 00307 } 00308 00309 00310 // Select variable with smallest afc 00311 template<class View> 00312 forceinline 00313 ViewSelAfcMin<View>::ViewSelAfcMin(void) : afc(0.0) {} 00314 template<class View> 00315 forceinline 00316 ViewSelAfcMin<View>::ViewSelAfcMin(Space& home, 00317 const VarBranchOptions& vbo) 00318 : ViewSelBase<View>(home,vbo), afc(0.0) {} 00319 template<class View> 00320 forceinline ViewSelStatus 00321 ViewSelAfcMin<View>::init(Space&, View x) { 00322 afc = x.afc(); 00323 return (afc == 0.0) ? VSS_BEST : VSS_BETTER; 00324 } 00325 template<class View> 00326 forceinline ViewSelStatus 00327 ViewSelAfcMin<View>::select(Space&, View x) { 00328 if (x.afc() < afc) { 00329 afc = x.afc(); 00330 return (afc == 0.0) ? VSS_BEST : VSS_BETTER; 00331 } else if (x.afc() > afc) { 00332 return VSS_WORSE; 00333 } else { 00334 return VSS_TIE; 00335 } 00336 } 00337 00338 00339 // Select variable with largest afc 00340 template<class View> 00341 forceinline 00342 ViewSelAfcMax<View>::ViewSelAfcMax(void) : afc(0.0) {} 00343 template<class View> 00344 forceinline 00345 ViewSelAfcMax<View>::ViewSelAfcMax(Space& home, 00346 const VarBranchOptions& vbo) 00347 : ViewSelBase<View>(home,vbo), afc(0.0) {} 00348 template<class View> 00349 forceinline ViewSelStatus 00350 ViewSelAfcMax<View>::init(Space&, View x) { 00351 afc = x.afc(); 00352 return VSS_BETTER; 00353 } 00354 template<class View> 00355 forceinline ViewSelStatus 00356 ViewSelAfcMax<View>::select(Space&, View x) { 00357 double xafc = x.afc(); 00358 if (xafc > afc) { 00359 afc = xafc; 00360 return VSS_BETTER; 00361 } else if (xafc < afc) { 00362 return VSS_WORSE; 00363 } else { 00364 return VSS_TIE; 00365 } 00366 } 00367 00368 00369 // Select variable by random 00370 template<class View> 00371 forceinline 00372 ViewSelRnd<View>::ViewSelRnd(void) : n(0) {} 00373 template<class View> 00374 forceinline 00375 ViewSelRnd<View>::ViewSelRnd(Space&, const VarBranchOptions& vbo) 00376 : r(vbo.seed), n(0) {} 00377 template<class View> 00378 forceinline ViewSelStatus 00379 ViewSelRnd<View>::init(Space&, View) { 00380 n=1; 00381 return VSS_BETTER; 00382 } 00383 template<class View> 00384 forceinline ViewSelStatus 00385 ViewSelRnd<View>::select(Space&, View) { 00386 n++; 00387 return (r(n) == (n-1)) ? VSS_BETTER : VSS_WORSE; 00388 } 00389 template<class View> 00390 forceinline Support::RandomGenerator 00391 ViewSelRnd<View>::choice(Space&) { 00392 return r; 00393 } 00394 template<class View> 00395 forceinline void 00396 ViewSelRnd<View>::commit(Space&, const Support::RandomGenerator& c, 00397 unsigned int) { 00398 r = c; 00399 } 00400 template<class View> 00401 forceinline void 00402 ViewSelRnd<View>::update(Space&, bool, ViewSelRnd<View>& vs) { 00403 r = vs.r; 00404 } 00405 template<class View> 00406 forceinline void 00407 ViewSelRnd<View>::dispose(Space&) { 00408 } 00409 00410 } 00411 00412 // STATISTICS: kernel-branch