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 using namespace Gecode;
00043
00045 class PhotoSpec {
00046 public:
00047 const int n_names;
00048 const int n_prefs;
00049 const int* prefs;
00050 PhotoSpec(const int n_n, const int n_p, const int* p)
00051 : n_names(n_n), n_prefs(n_p), prefs(p) {}
00052 };
00053
00055 const int s_prefs[] = {
00056 0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
00057 };
00059 const PhotoSpec p_small(5, 8, s_prefs);
00060
00062 const int l_prefs[] = {
00063 0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4,
00064 4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
00065 };
00067 const PhotoSpec p_large(9,17, l_prefs);
00068
00080 class Photo : public MaximizeScript {
00081 protected:
00083 const PhotoSpec& spec;
00085 IntVarArray pos;
00087 IntVar sat;
00088
00089 public:
00091 enum {
00092 BRANCH_NONE,
00093 BRANCH_DEGREE
00094 };
00096 Photo(const SizeOptions& opt) :
00097 spec(opt.size() == 0 ? p_small : p_large),
00098 pos(*this,spec.n_names, 0, spec.n_names-1),
00099 sat(*this,0,spec.n_prefs)
00100 {
00101 BoolVarArgs ful(spec.n_prefs);
00102
00103 for (int i = spec.n_prefs; i--; ) {
00104 int pa = spec.prefs[2*i+0];
00105 int pb = spec.prefs[2*i+1];
00106 ful[i] = post(*this,
00107 ~(pos[pb]-pos[pa] == 1) ^
00108 ~(pos[pa]-pos[pb] == 1));
00109 }
00110
00111 linear(*this, ful, IRT_EQ, sat);
00112
00113 distinct(*this, pos, opt.icl());
00114
00115
00116 rel(*this, pos[0], IRT_LE, pos[1]);
00117
00118 if (opt.branching() == BRANCH_NONE) {
00119 branch(*this, pos, INT_VAR_NONE, INT_VAL_MIN);
00120 } else {
00121 branch(*this, pos, tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN),
00122 INT_VAL_MIN);
00123 }
00124 }
00125
00127 Photo(bool share, Photo& s) :
00128 MaximizeScript(share,s), spec(s.spec) {
00129 pos.update(*this, share, s.pos);
00130 sat.update(*this, share, s.sat);
00131 }
00133 virtual Space*
00134 copy(bool share) {
00135 return new Photo(share,*this);
00136 }
00138 virtual void
00139 print(std::ostream& os) const {
00140 os << "\tpos[] = " << pos << std::endl
00141 << "\tsat: " << sat << std::endl;
00142 }
00144 virtual IntVar cost(void) const {
00145 return sat;
00146 }
00147 };
00148
00152 int
00153 main(int argc, char* argv[]) {
00154 SizeOptions opt("Photo");
00155 opt.solutions(0);
00156 opt.size(1);
00157 opt.iterations(10);
00158 opt.icl(ICL_BND);
00159 opt.branching(Photo::BRANCH_DEGREE);
00160 opt.branching(Photo::BRANCH_NONE, "none");
00161 opt.branching(Photo::BRANCH_DEGREE, "degree");
00162 opt.parse(argc,argv);
00163 MaximizeScript::run<Photo,BAB,SizeOptions>(opt);
00164 return 0;
00165 }
00166
00167
00168
00169