select-view.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2002 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 { namespace Int { namespace Branch { 00039 00040 // Select variable with smallest min 00041 forceinline 00042 ByMinMin::ByMinMin(void) : min(0) {} 00043 forceinline 00044 ByMinMin::ByMinMin(Space& home, const VarBranchOptions& vbo) 00045 : ViewSelBase<IntView>(home,vbo), min(0) {} 00046 forceinline ViewSelStatus 00047 ByMinMin::init(Space&, View x) { 00048 min = x.min(); 00049 return VSS_BETTER; 00050 } 00051 forceinline ViewSelStatus 00052 ByMinMin::select(Space&, View x) { 00053 if (x.min() < min) { 00054 min = x.min(); return VSS_BETTER; 00055 } else if (x.min() > min) { 00056 return VSS_WORSE; 00057 } else { 00058 return VSS_TIE; 00059 } 00060 } 00061 00062 // Select variable with largest min 00063 forceinline 00064 ByMinMax::ByMinMax(void) : min(0) {} 00065 forceinline 00066 ByMinMax::ByMinMax(Space& home, const VarBranchOptions& vbo) 00067 : ViewSelBase<IntView>(home,vbo), min(0) {} 00068 forceinline ViewSelStatus 00069 ByMinMax::init(Space&, View x) { 00070 min = x.min(); 00071 return VSS_BETTER; 00072 } 00073 forceinline ViewSelStatus 00074 ByMinMax::select(Space&, View x) { 00075 if (x.min() > min) { 00076 min = x.min(); return VSS_BETTER; 00077 } else if (x.min() < min) { 00078 return VSS_WORSE; 00079 } else { 00080 return VSS_TIE; 00081 } 00082 } 00083 00084 // Select variable with smallest max 00085 forceinline 00086 ByMaxMin::ByMaxMin(void) : max(0) {} 00087 forceinline 00088 ByMaxMin::ByMaxMin(Space& home, const VarBranchOptions& vbo) 00089 : ViewSelBase<IntView>(home,vbo), max(0) {} 00090 forceinline ViewSelStatus 00091 ByMaxMin::init(Space&, View x) { 00092 max = x.max(); 00093 return VSS_BETTER; 00094 } 00095 forceinline ViewSelStatus 00096 ByMaxMin::select(Space&, View x) { 00097 if (x.max() < max) { 00098 max = x.max(); return VSS_BETTER; 00099 } else if (x.max() > max) { 00100 return VSS_WORSE; 00101 } else { 00102 return VSS_TIE; 00103 } 00104 } 00105 00106 // Select variable with largest max 00107 forceinline 00108 ByMaxMax::ByMaxMax(void) : max(0) {} 00109 forceinline 00110 ByMaxMax::ByMaxMax(Space& home, const VarBranchOptions& vbo) 00111 : ViewSelBase<IntView>(home,vbo), max(0) {} 00112 forceinline ViewSelStatus 00113 ByMaxMax::init(Space&, View x) { 00114 max = x.max(); 00115 return VSS_BETTER; 00116 } 00117 forceinline ViewSelStatus 00118 ByMaxMax::select(Space&, View x) { 00119 if (x.max() > max) { 00120 max = x.max(); return VSS_BETTER; 00121 } else if (x.max() < max) { 00122 return VSS_WORSE; 00123 } else { 00124 return VSS_TIE; 00125 } 00126 } 00127 00128 // Select variable with smallest size 00129 forceinline 00130 BySizeMin::BySizeMin(void) : size(0U) {} 00131 forceinline 00132 BySizeMin::BySizeMin(Space& home, const VarBranchOptions& vbo) 00133 : ViewSelBase<IntView>(home,vbo), size(0U) {} 00134 forceinline ViewSelStatus 00135 BySizeMin::init(Space&, View x) { 00136 size = x.size(); 00137 return (size == 2) ? VSS_BEST : VSS_BETTER; 00138 } 00139 forceinline ViewSelStatus 00140 BySizeMin::select(Space&, View x) { 00141 if (x.size() < size) { 00142 size = x.size(); 00143 return (size == 2) ? VSS_BEST : VSS_BETTER; 00144 } else if (x.size() > size) { 00145 return VSS_WORSE; 00146 } else { 00147 return VSS_TIE; 00148 } 00149 } 00150 00151 // Select variable with largest size 00152 forceinline 00153 BySizeMax::BySizeMax(void) : size(0U) {} 00154 forceinline 00155 BySizeMax::BySizeMax(Space& home, const VarBranchOptions& vbo) 00156 : ViewSelBase<IntView>(home,vbo), size(0U) {} 00157 forceinline ViewSelStatus 00158 BySizeMax::init(Space&, View x) { 00159 size = x.size(); 00160 return VSS_BETTER; 00161 } 00162 forceinline ViewSelStatus 00163 BySizeMax::select(Space&, View x) { 00164 if (x.size() > size) { 00165 size = x.size(); 00166 return VSS_BETTER; 00167 } else if (x.size() < size) { 00168 return VSS_WORSE; 00169 } else { 00170 return VSS_TIE; 00171 } 00172 } 00173 00174 // Select variable with smallest size/degree 00175 forceinline 00176 BySizeDegreeMin::BySizeDegreeMin(void) : sizedegree(0) {} 00177 forceinline 00178 BySizeDegreeMin::BySizeDegreeMin(Space& home, const VarBranchOptions& vbo) 00179 : ViewSelBase<IntView>(home,vbo), sizedegree(0) {} 00180 forceinline ViewSelStatus 00181 BySizeDegreeMin::init(Space&, View x) { 00182 sizedegree = 00183 static_cast<double>(x.size())/static_cast<double>(x.degree()); 00184 return VSS_BETTER; 00185 } 00186 forceinline ViewSelStatus 00187 BySizeDegreeMin::select(Space&, View x) { 00188 double sd = 00189 static_cast<double>(x.size())/static_cast<double>(x.degree()); 00190 if (sd < sizedegree) { 00191 sizedegree = sd; return VSS_BETTER; 00192 } else if (sd > sizedegree) { 00193 return VSS_WORSE; 00194 } else { 00195 return VSS_TIE; 00196 } 00197 } 00198 00199 // Select variable with largest size/degree 00200 forceinline 00201 BySizeDegreeMax::BySizeDegreeMax(void) : sizedegree(0) {} 00202 forceinline 00203 BySizeDegreeMax::BySizeDegreeMax(Space& home, const VarBranchOptions& vbo) 00204 : ViewSelBase<IntView>(home,vbo), sizedegree(0) {} 00205 forceinline ViewSelStatus 00206 BySizeDegreeMax::init(Space&, View x) { 00207 sizedegree = 00208 static_cast<double>(x.size())/static_cast<double>(x.degree()); 00209 return VSS_BETTER; 00210 } 00211 forceinline ViewSelStatus 00212 BySizeDegreeMax::select(Space&, View x) { 00213 double sd = 00214 static_cast<double>(x.size())/static_cast<double>(x.degree()); 00215 if (sd > sizedegree) { 00216 sizedegree = sd; return VSS_BETTER; 00217 } else if (sd < sizedegree) { 00218 return VSS_WORSE; 00219 } else { 00220 return VSS_TIE; 00221 } 00222 } 00223 00224 // Select variable with smallest size/afc 00225 forceinline 00226 BySizeAfcMin::BySizeAfcMin(void) : sizeafc(0) {} 00227 forceinline 00228 BySizeAfcMin::BySizeAfcMin(Space& home, const VarBranchOptions& vbo) 00229 : ViewSelBase<IntView>(home,vbo), sizeafc(0) {} 00230 forceinline ViewSelStatus 00231 BySizeAfcMin::init(Space&, View x) { 00232 sizeafc = static_cast<double>(x.size())/x.afc(); 00233 return VSS_BETTER; 00234 } 00235 forceinline ViewSelStatus 00236 BySizeAfcMin::select(Space&, View x) { 00237 double sa = static_cast<double>(x.size())/x.afc(); 00238 if (sa < sizeafc) { 00239 sizeafc = sa; return VSS_BETTER; 00240 } else if (sa > sizeafc) { 00241 return VSS_WORSE; 00242 } else { 00243 return VSS_TIE; 00244 } 00245 } 00246 00247 // Select variable with largest size/afc 00248 forceinline 00249 BySizeAfcMax::BySizeAfcMax(void) : sizeafc(0) {} 00250 forceinline 00251 BySizeAfcMax::BySizeAfcMax(Space& home, const VarBranchOptions& vbo) 00252 : ViewSelBase<IntView>(home,vbo), sizeafc(0) {} 00253 forceinline ViewSelStatus 00254 BySizeAfcMax::init(Space&, View x) { 00255 sizeafc = static_cast<double>(x.size())/x.afc(); 00256 return VSS_BETTER; 00257 } 00258 forceinline ViewSelStatus 00259 BySizeAfcMax::select(Space&, View x) { 00260 double sa = static_cast<double>(x.size())/x.afc(); 00261 if (sa > sizeafc) { 00262 sizeafc = sa; return VSS_BETTER; 00263 } else if (sa < sizeafc) { 00264 return VSS_WORSE; 00265 } else { 00266 return VSS_TIE; 00267 } 00268 } 00269 00270 // Select variable with smallest min-regret 00271 forceinline 00272 ByRegretMinMin::ByRegretMinMin(void) : regret(0U) {} 00273 forceinline 00274 ByRegretMinMin::ByRegretMinMin(Space& home, const VarBranchOptions& vbo) 00275 : ViewSelBase<IntView>(home,vbo), regret(0U) {} 00276 forceinline ViewSelStatus 00277 ByRegretMinMin::init(Space&, View x) { 00278 regret = x.regret_min(); 00279 return (regret == 1) ? VSS_BEST : VSS_BETTER; 00280 } 00281 forceinline ViewSelStatus 00282 ByRegretMinMin::select(Space&, View x) { 00283 if (x.regret_min() < regret) { 00284 regret = x.regret_min(); 00285 return (regret == 1) ? VSS_BEST : VSS_BETTER; 00286 } else if (x.regret_min() > regret) { 00287 return VSS_WORSE; 00288 } else { 00289 return VSS_TIE; 00290 } 00291 } 00292 00293 // Select variable with largest min-regret 00294 forceinline 00295 ByRegretMinMax::ByRegretMinMax(void) : regret(0U) {} 00296 forceinline 00297 ByRegretMinMax::ByRegretMinMax(Space& home, const VarBranchOptions& vbo) 00298 : ViewSelBase<IntView>(home,vbo), regret(0U) {} 00299 forceinline ViewSelStatus 00300 ByRegretMinMax::init(Space&, View x) { 00301 regret = x.regret_min(); 00302 return VSS_BETTER; 00303 } 00304 forceinline ViewSelStatus 00305 ByRegretMinMax::select(Space&, View x) { 00306 if (x.regret_min() > regret) { 00307 regret = x.regret_min(); 00308 return VSS_BETTER; 00309 } else if (x.regret_min() < regret) { 00310 return VSS_WORSE; 00311 } else { 00312 return VSS_TIE; 00313 } 00314 } 00315 00316 // Select variable with smallest max-regret 00317 forceinline 00318 ByRegretMaxMin::ByRegretMaxMin(void) : regret(0U) {} 00319 forceinline 00320 ByRegretMaxMin::ByRegretMaxMin(Space& home, const VarBranchOptions& vbo) 00321 : ViewSelBase<IntView>(home,vbo), regret(0U) {} 00322 forceinline ViewSelStatus 00323 ByRegretMaxMin::init(Space&, View x) { 00324 regret = x.regret_max(); 00325 return (regret == 1) ? VSS_BEST : VSS_BETTER; 00326 } 00327 forceinline ViewSelStatus 00328 ByRegretMaxMin::select(Space&, View x) { 00329 if (x.regret_max() < regret) { 00330 regret = x.regret_max(); 00331 return (regret == 1) ? VSS_BEST : VSS_BETTER; 00332 } else if (x.regret_max() > regret) { 00333 return VSS_WORSE; 00334 } else { 00335 return VSS_TIE; 00336 } 00337 } 00338 00339 // Select variable with largest max-regret 00340 forceinline 00341 ByRegretMaxMax::ByRegretMaxMax(void) : regret(0U) {} 00342 forceinline 00343 ByRegretMaxMax::ByRegretMaxMax(Space& home, const VarBranchOptions& vbo) 00344 : ViewSelBase<IntView>(home,vbo), regret(0U) {} 00345 forceinline ViewSelStatus 00346 ByRegretMaxMax::init(Space&, View x) { 00347 regret = x.regret_max(); 00348 return VSS_BETTER; 00349 } 00350 forceinline ViewSelStatus 00351 ByRegretMaxMax::select(Space&, View x) { 00352 if (x.regret_max() > regret) { 00353 regret = x.regret_max(); 00354 return VSS_BETTER; 00355 } else if (x.regret_max() < regret) { 00356 return VSS_WORSE; 00357 } else { 00358 return VSS_TIE; 00359 } 00360 } 00361 00362 }}} 00363 00364 // STATISTICS: int-branch