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 IntMinimizeScript {
00081 protected:
00083 const PhotoSpec& spec;
00085 IntVarArray pos;
00087 IntVar violations;
00088
00089 public:
00091 enum {
00092 BRANCH_NONE,
00093 BRANCH_DEGREE
00094 };
00096 Photo(const SizeOptions& opt) :
00097 IntMinimizeScript(opt),
00098 spec(opt.size() == 0 ? p_small : p_large),
00099 pos(*this,spec.n_names, 0, spec.n_names-1),
00100 violations(*this,0,spec.n_prefs)
00101 {
00102
00103 BoolVarArgs viol(spec.n_prefs);
00104 for (int i=0; i<spec.n_prefs; i++) {
00105 int pa = spec.prefs[2*i+0];
00106 int pb = spec.prefs[2*i+1];
00107 viol[i] = expr(*this, abs(pos[pa]-pos[pb]) > 1);
00108 }
00109 rel(*this, violations == sum(viol));
00110
00111 distinct(*this, pos, opt.icl());
00112
00113
00114 rel(*this, pos[0] < pos[1]);
00115
00116 if (opt.branching() == BRANCH_NONE) {
00117 branch(*this, pos, INT_VAR_NONE(), INT_VAL_MIN());
00118 } else {
00119 branch(*this, pos, tiebreak(INT_VAR_DEGREE_MAX(),INT_VAR_SIZE_MIN()),
00120 INT_VAL_MIN());
00121 }
00122 }
00123
00125 Photo(bool share, Photo& s) :
00126 IntMinimizeScript(share,s), spec(s.spec) {
00127 pos.update(*this, share, s.pos);
00128 violations.update(*this, share, s.violations);
00129 }
00131 virtual Space*
00132 copy(bool share) {
00133 return new Photo(share,*this);
00134 }
00136 virtual void
00137 print(std::ostream& os) const {
00138 os << "\tpos[] = " << pos << std::endl
00139 << "\tviolations: " << violations << std::endl;
00140 }
00142 virtual IntVar cost(void) const {
00143 return violations;
00144 }
00145 };
00146
00150 int
00151 main(int argc, char* argv[]) {
00152 SizeOptions opt("Photo");
00153 opt.solutions(0);
00154 opt.size(1);
00155 opt.iterations(10);
00156 opt.icl(ICL_BND);
00157 opt.branching(Photo::BRANCH_DEGREE);
00158 opt.branching(Photo::BRANCH_NONE, "none");
00159 opt.branching(Photo::BRANCH_DEGREE, "degree");
00160 opt.parse(argc,argv);
00161 IntMinimizeScript::run<Photo,BAB,SizeOptions>(opt);
00162 return 0;
00163 }
00164
00165
00166
00167