Generated on Thu Jul 6 07:06:40 2006 for Gecode by doxygen 1.4.7

golomb.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2001
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3188 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "examples/support.hh"
00023 #include "gecode/minimodel.hh"
00024 
00037 class Golomb : public Example {
00038 protected:
00040   const int n;
00042   IntVarArray m;
00043 public:
00045   int
00046   diag(int i, int j) {
00047     return (i*(2*n-i-1)) / 2 + j - i - 1;
00048   }
00049 
00051   Golomb(const Options& opt)
00052     : n(opt.size), m(this,n,0,n*n) {
00053     const int nn = n*n;
00054     const int dn = (n*n-n)/2;
00055 
00056     IntVarArgs d(dn);
00057 
00058     // Assume first mark to be zero
00059     rel(this, m[0], IRT_EQ, 0);
00060 
00061     // Setup difference constraints
00062     for (int j=1; j<n; j++)
00063       d[diag(0,j)] = m[j];
00064     for (int i=1; i<n-1; i++)
00065       for (int j=i+1; j<n; j++)
00066         d[diag(i,j)] = minus(this, m[j], m[i]);
00067 
00068     // Order marks
00069     for (int i=1; i<n; i++)
00070       rel(this, m[i-1], IRT_LE, m[i]);
00071 
00072     if (opt.naive) {
00073       // d[diag(i,j)] must be at least sum of first j-i integers
00074       for (int i=0; i<n; i++)
00075         for (int j=i+1; j<n; j++)
00076           rel(this, d[diag(i,j)], IRT_GQ, (j-i)*(j-i+1)/2);
00077     } else {
00078       static const int length[] = {
00079         // Length 0-9
00080         0,0,1,3,6,11,17,25,34,44,
00081         // Length 10-
00082         55,72,85,106,127};
00083 
00084       // Marks from i to j must be ruler of length j-1+i
00085       for (int i=0; i<n; i++)
00086         for (int j=i+1; j<n; j++)
00087           rel(this, d[diag(i,j)], IRT_GQ, length[j-i+1]);
00088     }
00089     distinct(this, d, opt.icl);
00090 
00091     if (n > 2)
00092       rel(this, d[diag(0,1)], IRT_LE, d[diag(n-2,n-1)]);
00093 
00094     branch(this, m, BVAR_NONE, BVAL_MIN);
00095   }
00096 
00098   void
00099   constrain(Space* s) {
00100     rel(this, m[n-1], IRT_LE, static_cast<Golomb*>(s)->m[n-1].val());
00101   }
00102 
00104   virtual void
00105   print(void) {
00106     std::cout << "\tm[" << n << "] = {";
00107     for (int i = 0; i < n; i++)
00108       std::cout << m[i] << ((i<n-1)?",":"};\n");
00109   }
00110 
00111 
00113   Golomb(bool share, Golomb& s)
00114     : Example(share,s), n(s.n) {
00115     m.update(this, share, s.m);
00116   }
00118   virtual Space*
00119   copy(bool share) {
00120     return new Golomb(share,*this);
00121   }
00122 
00123 };
00124 
00128 int
00129 main(int argc, char** argv) {
00130   Options o("Golomb");
00131   o.solutions = 0;
00132   o.size      = 10;
00133   o.icl       = ICL_BND;
00134   o.naive     = true;
00135   o.parse(argc,argv);
00136   if (o.size > 0)
00137     Example::run<Golomb,BAB>(o);
00138   return 0;
00139 }
00140 
00141 // STATISTICS: example-any
00142