photo.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2001 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 MinimizeScript { 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 spec(opt.size() == 0 ? p_small : p_large), 00098 pos(*this,spec.n_names, 0, spec.n_names-1), 00099 violations(*this,0,spec.n_prefs) 00100 { 00101 // Map preferences to violation 00102 BoolVarArgs viol(spec.n_prefs); 00103 for (int i=0; i<spec.n_prefs; i++) { 00104 int pa = spec.prefs[2*i+0]; 00105 int pb = spec.prefs[2*i+1]; 00106 viol[i] = expr(*this, abs(pos[pa]-pos[pb]) > 1); 00107 } 00108 rel(*this, violations == sum(viol)); 00109 00110 distinct(*this, pos, opt.icl()); 00111 00112 // Break some symmetries 00113 rel(*this, pos[0] < pos[1]); 00114 00115 if (opt.branching() == BRANCH_NONE) { 00116 branch(*this, pos, INT_VAR_NONE, INT_VAL_MIN); 00117 } else { 00118 branch(*this, pos, tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN), 00119 INT_VAL_MIN); 00120 } 00121 } 00122 00124 Photo(bool share, Photo& s) : 00125 MinimizeScript(share,s), spec(s.spec) { 00126 pos.update(*this, share, s.pos); 00127 violations.update(*this, share, s.violations); 00128 } 00130 virtual Space* 00131 copy(bool share) { 00132 return new Photo(share,*this); 00133 } 00135 virtual void 00136 print(std::ostream& os) const { 00137 os << "\tpos[] = " << pos << std::endl 00138 << "\tviolations: " << violations << std::endl; 00139 } 00141 virtual IntVar cost(void) const { 00142 return violations; 00143 } 00144 }; 00145 00149 int 00150 main(int argc, char* argv[]) { 00151 SizeOptions opt("Photo"); 00152 opt.solutions(0); 00153 opt.size(1); 00154 opt.iterations(10); 00155 opt.icl(ICL_BND); 00156 opt.branching(Photo::BRANCH_DEGREE); 00157 opt.branching(Photo::BRANCH_NONE, "none"); 00158 opt.branching(Photo::BRANCH_DEGREE, "degree"); 00159 opt.parse(argc,argv); 00160 MaximizeScript::run<Photo,BAB,SizeOptions>(opt); 00161 return 0; 00162 } 00163 00164 00165 // STATISTICS: example-any 00166