golomb-ruler.cpp
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 <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 #include <iomanip>
00043
00044 using namespace Gecode;
00045
00066 class GolombRuler : public IntMinimizeScript {
00067 protected:
00069 IntVarArray m;
00070 public:
00072 GolombRuler(const SizeOptions& opt)
00073 : IntMinimizeScript(opt),
00074 m(*this,opt.size(),0,
00075 (opt.size() < 31) ? (1 << (opt.size()-1))-1 : Int::Limits::max) {
00076
00077
00078 rel(*this, m[0], IRT_EQ, 0);
00079
00080
00081 rel(*this, m, IRT_LE);
00082
00083
00084 const int n = m.size();
00085 const int n_d = (n*n-n)/2;
00086
00087
00088 IntVarArgs d(n_d);
00089
00090
00091 for (int k=0, i=0; i<n-1; i++)
00092 for (int j=i+1; j<n; j++, k++)
00093
00094 rel(*this, d[k] = expr(*this, m[j]-m[i]),
00095 IRT_GQ, (j-i)*(j-i+1)/2);
00096
00097 distinct(*this, d, opt.ipl());
00098
00099
00100 if (n > 2)
00101 rel(*this, d[0], IRT_LE, d[n_d-1]);
00102
00103 branch(*this, m, INT_VAR_NONE(), INT_VAL_MIN());
00104 }
00105
00107 virtual IntVar cost(void) const {
00108 return m[m.size()-1];
00109 }
00110
00112 virtual void
00113 print(std::ostream& os) const {
00114 os << "\tm[" << m.size() << "] = " << m << std::endl;
00115 }
00116
00118 GolombRuler(bool share, GolombRuler& s)
00119 : IntMinimizeScript(share,s) {
00120 m.update(*this, share, s.m);
00121 }
00123 virtual Space*
00124 copy(bool share) {
00125 return new GolombRuler(share,*this);
00126 }
00127 };
00128
00132 int
00133 main(int argc, char* argv[]) {
00134 SizeOptions opt("GolombRuler");
00135 opt.solutions(0);
00136 opt.size(10);
00137 opt.ipl(IPL_BND);
00138 opt.parse(argc,argv);
00139 if (opt.size() > 0)
00140 IntMinimizeScript::run<GolombRuler,BAB,SizeOptions>(opt);
00141 return 0;
00142 }
00143
00144
00145