toulbar2
csproblem.h
1 /* classe des problèmes de satisfaction de contraintes CSP*/
3 class CSProblem : public OpProblem {
4 public:
5  /* nombre de contraintes */
7  int nbconst;
8 
9  /* tableau des domaines : chaque domaine est un vecteur d'entiers */
11  vector<int>* tabdomains;
12  /* pour chaque variable, numéro de son domaine : indice dans le tableau tabdomains */
14  int* domains;
15  /* tableau des connexions : pour chaque variable, vecteur des variables connectées */
17  vector<int>* connections;
18  /* constructeur de base */
20  CSProblem(int nbvar, int nbconst);
21  /* constructeur avec borne inférieure */
23  CSProblem(int nbvar, int nbconst, int lower);
24  ~CSProblem();
25  void move_execution(Configuration* configuration, Move* move);
26  /* la taille du domaine de la variable var */
28  virtual int variable_domainsize(int var);
29  void random_configuration(Configuration* configuration);
30  /* une variable choisie aléatoirement */
32  virtual int random_variable(Configuration* configuration);
34  virtual int random_conflict_variable(Configuration* configuration);
35  /* une valeur choisie aléatoirement, si possible distincte de val : retourne l'indice de la valeur dans le domaine */
37  virtual int random_value(int var, int val);
38  /* une valeur dans le domaine de la variable minimisant les conflits avec la configuration */
41  virtual int min_conflict_value(int var, int val, Configuration* configuration);
42  /* initialisation des domaines par défaut : un seul domaine numéro 0 pour toutes les variables */
44  virtual void init_domains(int nbvar, int s);
45  /* un seul domaine par défaut : entiers de 0 à s-1 */
47  virtual void init_tabdomains(int s);
48  /* calcul des variables en conflit : on reconstruit le vecteur des variables en conflit d'une configuration*/
50  void compute_var_conflict(Configuration* configuration);
51  void best_config_analysis();
52  void best_config_write();
53  Long move_evaluation(Configuration* configuration, Move* move);
54  void init_population(Configuration** population, int populationsize);
55  Configuration* create_configuration();
56  Move* create_move();
57  void adjust_parameters(Configuration* configuration, int& maxneighbors, int& minneighbors);
58  void next_move(Configuration* configuration, Move* move, NeighborhoodSearch* nbhs);
59  /* met en place les domaines et connexions d'un problème */
61  virtual void set_domains_connections(int* dom, vector<int>* tabledom, vector<int>* connect);
62  /* initialisation des domaines : appel de init_domains et init_tabdomains */
64  virtual void init_domain_tabdomain();
65  int tabuindex(Move* move, Configuration* config);
66  int tabuinverseindex(Move* move, Configuration* config);
67  int nbtabuindex();
68 };
69 
70 /* CSP Binaires : ajout du tableau des contraintes à partir de 2 variables */
72 class BinaryCSProblem : public CSProblem {
73 public:
74  /* pour une paire de variables (i,j) (i<j) , constraints[i][j] contient le numéro de contraintes +1 entre ces variables si
75  elles sont connectées, 0 sinon. On se limite à au plus une contrainte par paire de variables : dans le
76  cas contraire on peut utiliser la classe WeightExtensionBinaryCSP */
79  int** constraints;
80  BinaryCSProblem(int nbvar, int nbconst);
81  BinaryCSProblem(int nbvar, int nbconst, int lower);
82  ~BinaryCSProblem() { ; };
83 };
84 
85 int** csp_constraintdatastructure(int nbvar);
CSProblem::init_domain_tabdomain
virtual void init_domain_tabdomain()
Definition: csproblem.cpp:291
CSProblem::random_value
virtual int random_value(int var, int val)
Definition: csproblem.cpp:133
CSProblem::tabdomains
vector< int > * tabdomains
Definition: csproblem.h:11
Move
Definition: incop.h:185
OpProblem::domainsize
int domainsize
Definition: incop.h:229
OpProblem::index2value
virtual int index2value(int index, int var)
Definition: incop.h:296
CSProblem::compute_var_conflict
void compute_var_conflict(Configuration *configuration)
Definition: csproblem.cpp:33
CSProblem::init_domains
virtual void init_domains(int nbvar, int s)
Definition: csproblem.cpp:18
CSProblem::random_conflict_variable
virtual int random_conflict_variable(Configuration *configuration)
Definition: csproblem.cpp:125
BinaryCSProblem
Definition: csproblem.h:72
CSPMove
Definition: incop.h:203
CSProblem::nbconst
int nbconst
Definition: csproblem.h:7
OpProblem::best_config
Configuration * best_config
Definition: incop.h:223
OpProblem::nbvar
int nbvar
Definition: incop.h:226
OpProblem
Definition: incop.h:219
Configuration::valuation
Long valuation
Definition: incop.h:93
CSProblem::min_conflict_value
virtual int min_conflict_value(int var, int val, Configuration *configuration)
Definition: csproblem.cpp:148
NeighborhoodSearch::var_conflict
int var_conflict
Definition: incop.h:327
NeighborhoodSearch::val_conflict
int val_conflict
Definition: incop.h:330
NeighborhoodSearch
Definition: incop.h:312
Configuration::var_conflict
vector< int > var_conflict
Definition: incop.h:97
CSProblem::domains
int * domains
Definition: csproblem.h:14
OpProblem::config_evaluation
virtual Long config_evaluation(Configuration *configuration)
Definition: incop.h:290
OpProblem::move_execution
virtual void move_execution(Configuration *configuration, Move *move)
Definition: csproblem.cpp:197
CSProblem::random_variable
virtual int random_variable(Configuration *configuration)
Definition: csproblem.cpp:109
CSProblem::set_domains_connections
virtual void set_domains_connections(int *dom, vector< int > *tabledom, vector< int > *connect)
Definition: csproblem.cpp:284
CSProblem::connections
vector< int > * connections
Definition: csproblem.h:17
CSProblem::CSProblem
CSProblem(int nbvar, int nbconst)
Definition: csproblem.cpp:49
Configuration
Definition: incop.h:82
OpProblem::best_config_verification
virtual void best_config_verification()
Definition: csproblem.cpp:257
OpProblem::currentmove
Move * currentmove
Definition: incop.h:235
OpProblem::bestmove
Move * bestmove
Definition: incop.h:241
CSProblem::variable_domainsize
virtual int variable_domainsize(int var)
Definition: csproblem.cpp:44
Configuration::get_conflicts_problem
virtual Long get_conflicts_problem(OpProblem *problem, int var, int val)
Definition: incopalgo.cpp:225
BinaryCSProblem::constraints
int ** constraints
Definition: csproblem.h:79
Configuration::config
int * config
Definition: incop.h:90
CSProblem::init_tabdomains
virtual void init_tabdomains(int s)
Definition: csproblem.cpp:25
OpProblem::firstmove
Move * firstmove
Definition: incop.h:238
OpProblem::create_move
virtual Move * create_move()
Definition: incop.h:259
OpProblem::allocate_moves
virtual void allocate_moves()
Definition: csproblem.cpp:249
CSProblem
Definition: csproblem.h:3