00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
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
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
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
00153