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

photo.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 
00026 class PhotoSpec {
00027 public:
00028   const int  n_names; 
00029   const int  n_prefs; 
00030   const int* prefs;   
00031 };
00032 
00034 static const int s_prefs[] = {
00035   0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
00036 };
00038 static const PhotoSpec p_small = { 5, 8, s_prefs};
00039 
00041 static const int l_prefs[] = {
00042   0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4,
00043   4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
00044 };
00046 static const PhotoSpec p_large = { 9,17, l_prefs };
00047 
00059 class Photo : public Example {
00060 protected:
00062   const PhotoSpec& spec;
00064   IntVarArray      pos;
00066   IntVar           sat;
00067 
00068 public:
00070   Photo(const Options& opt) :
00071     spec(opt.size == 0 ? p_small : p_large),
00072     pos(this,spec.n_names, 0, spec.n_names-1),
00073     sat(this,0,spec.n_prefs)
00074   {
00075     BoolVarArgs ful(spec.n_prefs);
00076     // Map preferences to fulfilment
00077     for (int i = spec.n_prefs; i--; ) {
00078       int pa = spec.prefs[2*i+0];
00079       int pb = spec.prefs[2*i+1];
00080       ful[i] = post(this,
00081                     ~(pos[pb]-pos[pa] == 1) ^
00082                     ~(pos[pa]-pos[pb] == 1));
00083     }
00084     // Sum of fulfilment
00085     {
00086       IntVarArgs eq(spec.n_prefs+1);
00087       IntArgs    c(spec.n_prefs+1);
00088       eq[spec.n_prefs] = sat; c[spec.n_prefs] = -1;
00089       for (int i = spec.n_prefs; i--; ) {
00090         eq[i] = ful[i]; c[i] = 1;
00091       }
00092       linear(this, c, eq, IRT_EQ, 0);
00093     }
00094     distinct(this, pos, opt.icl);
00095 
00096     // Break some symmetries
00097     rel(this, pos[0], IRT_LE, pos[1]);
00098     
00099     if (opt.naive) {
00100       branch(this, pos, BVAR_NONE, BVAL_MIN);
00101     } else {
00102       branch(this, pos, BVAR_DEGREE_MAX, BVAL_MIN);
00103     }
00104   }
00105 
00107   Photo(bool share, Photo& s) :
00108     Example(share,s), spec(s.spec) {
00109     pos.update(this, share, s.pos);
00110     sat.update(this, share, s.sat);
00111   }
00112 
00114   virtual Space*
00115   copy(bool share) {
00116     return new Photo(share,*this);
00117   }
00118 
00120   virtual void
00121   print(void) {
00122     std::cout << "\tpos[] = {";
00123     for (int i = 0; i < spec.n_names; i++)
00124       std::cout << pos[i] << ((i<spec.n_names-1)?",":"};\n");
00125     std::cout << "\tsat: " << sat << std::endl;
00126   }
00127 
00129   void
00130   constrain(Space* s) {
00131     rel(this, sat, IRT_GR, static_cast<Photo*>(s)->sat.val());
00132   }
00133 
00134 };
00135 
00139 int
00140 main(int argc, char** argv) {
00141   Options opt("Photo");
00142   opt.solutions  = 0;
00143   opt.size       = 1;
00144   opt.iterations = 10;
00145   opt.icl        = ICL_BND;
00146   opt.parse(argc,argv);
00147   Example::run<Photo,BAB>(opt);
00148   return 0;
00149 }
00150 
00151 
00152 // STATISTICS: example-any
00153