Generated on Thu Mar 22 10:39:35 2012 for Gecode by doxygen 1.6.3

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