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
00060 class GolombRuler : public MinimizeScript {
00061 protected:
00063 const int n;
00065 IntVarArray m;
00066 public:
00068 enum {
00069 MODEL_NONE,
00070 MODEL_SUM,
00071 MODEL_RULER
00072 };
00074 enum {
00075 SEARCH_BAB,
00076 SEARCH_RESTART
00077 };
00079 int
00080 diag(int i, int j) {
00081 return (i*(2*n-i-1)) / 2 + j - i - 1;
00082 }
00083
00085 GolombRuler(const SizeOptions& opt)
00086 : n(opt.size()), m(*this,n,0,n*n) {
00087 const int dn = (n*n-n)/2;
00088
00089 IntVarArgs d(dn);
00090
00091
00092 rel(*this, m[0], IRT_EQ, 0);
00093
00094
00095 for (int j=1; j<n; j++)
00096 d[diag(0,j)] = m[j];
00097 for (int i=1; i<n-1; i++)
00098 for (int j=i+1; j<n; j++)
00099 d[diag(i,j)] = minus(*this, m[j], m[i]);
00100
00101
00102 rel(*this, m, IRT_LE);
00103
00104 switch (opt.model()) {
00105 case MODEL_NONE:
00106 break;
00107 case MODEL_SUM:
00108
00109 for (int i=0; i<n; i++)
00110 for (int j=i+1; j<n; j++)
00111 rel(*this, d[diag(i,j)], IRT_GQ, (j-i)*(j-i+1)/2);
00112 break;
00113 case MODEL_RULER:
00114 {
00115 static const int length[] = {
00116
00117 0,0,1,3,6,11,17,25,34,44,
00118
00119 55,72,85,106,127};
00120
00121 for (int i=0; i<n; i++)
00122 for (int j=i+1; j<n; j++)
00123 rel(*this, d[diag(i,j)], IRT_GQ, length[j-i+1]);
00124 }
00125 break;
00126 }
00127
00128 distinct(*this, d, opt.icl());
00129
00130 if (n > 2)
00131 rel(*this, d[diag(0,1)], IRT_LE, d[diag(n-2,n-1)]);
00132
00133 branch(*this, m, INT_VAR_NONE, INT_VAL_MIN);
00134 }
00135
00137 virtual IntVar cost(void) const {
00138 return m[n-1];
00139 }
00140
00142 virtual void
00143 print(std::ostream& os) const {
00144 os << "\tm[" << n << "] = " << m << std::endl;
00145 }
00146
00148 GolombRuler(bool share, GolombRuler& s)
00149 : MinimizeScript(share,s), n(s.n) {
00150 m.update(*this, share, s.m);
00151 }
00153 virtual Space*
00154 copy(bool share) {
00155 return new GolombRuler(share,*this);
00156 }
00157 };
00158
00162 int
00163 main(int argc, char* argv[]) {
00164 SizeOptions opt("GolombRuler");
00165 opt.solutions(0);
00166 opt.size(10);
00167 opt.icl(ICL_BND);
00168 opt.model(GolombRuler::MODEL_SUM);
00169 opt.model(GolombRuler::MODEL_NONE, "none",
00170 "no lower bound");
00171 opt.model(GolombRuler::MODEL_SUM, "sum",
00172 "use sum of ticks as lower bound");
00173 opt.model(GolombRuler::MODEL_RULER, "ruler",
00174 "use size of smaller rulers as lower bound");
00175 opt.search(GolombRuler::SEARCH_BAB);
00176 opt.search(GolombRuler::SEARCH_BAB, "bab");
00177 opt.search(GolombRuler::SEARCH_RESTART, "restart");
00178 opt.parse(argc,argv);
00179 if (opt.size() > 0)
00180 switch (opt.search()) {
00181 case GolombRuler::SEARCH_BAB:
00182 MinimizeScript::run<GolombRuler,BAB,SizeOptions>(opt); break;
00183 case GolombRuler::SEARCH_RESTART:
00184 MinimizeScript::run<GolombRuler,Restart,SizeOptions>(opt); break;
00185 }
00186 return 0;
00187 }
00188
00189
00190