Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

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: 2005-11-04 15:30:42 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2499 $
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 "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     IntVarArray d(this,dn,0,nn);
00056 
00057     rel(this, m[0], IRT_EQ, 0);
00058 
00059     // Setup difference constraints
00060     for (int j=1; j<n; j++)
00061       d[diag(0,j)] = m[j];
00062     for (int i=1; i<n-1; i++)
00063       for (int j=i+1; j<n; j++)
00064         post(this, m[j]-m[i] == d[diag(i,j)]);
00065 
00066     // Order marks
00067     for (int i=1; i<n; i++)
00068       rel(this, m[i-1], IRT_LE, m[i]);
00069 
00070     if (opt.naive) {
00071       // d[diag(i,j)] must be at least sum of first j-i integers
00072       for (int i=0; i<n; i++)
00073         for (int j=i+1; j<n; j++)
00074           rel(this, d[diag(i,j)], IRT_GQ, (j-i)*(j-i+1)/2);
00075     } else {
00076       static const int length[] = {
00077         // Length 0-9
00078         0,0,1,3,6,11,17,25,34,44,
00079         // Length 10-
00080         55,72,85,106,127};
00081 
00082       // Marks from i to j must be ruler of length j-1+i
00083       for (int i=0; i<n; i++)
00084         for (int j=i+1; j<n; j++)
00085           rel(this, d[diag(i,j)], IRT_GQ, length[j-i+1]);
00086     }
00087     distinct(this, d, opt.icl);
00088 
00089     if (n > 2)
00090       rel(this, d[diag(0,1)], IRT_LE, d[diag(n-2,n-1)]);
00091 
00092     branch(this, m, BVAR_NONE, BVAL_MIN);
00093   }
00094 
00096   void
00097   constrain(Space* s) {
00098     rel(this, m[n-1], IRT_LE, static_cast<Golomb*>(s)->m[n-1].val());
00099   }
00100 
00102   virtual void
00103   print(void) {
00104     std::cout << "\tm[" << n << "] = {";
00105     for (int i = 0; i < n; i++)
00106       std::cout << m[i] << ((i<n-1)?",":"};\n");
00107   }
00108 
00109 
00111   Golomb(bool share, Golomb& s)
00112     : Example(share,s), n(s.n) {
00113     m.update(this, share, s.m);
00114   }
00116   virtual Space*
00117   copy(bool share) {
00118     return new Golomb(share,*this);
00119   }
00120 
00121 };
00122 
00126 int
00127 main(int argc, char** argv) {
00128   Options o("Golomb");
00129   o.solutions = 0;
00130   o.size      = 10;
00131   o.icl       = ICL_BND;
00132   o.naive     = true;
00133   o.parse(argc,argv);
00134   if (o.size > 0)
00135     Example::run<Golomb,BAB>(o);
00136   return 0;
00137 }
00138 
00139 // STATISTICS: example-any
00140