IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

algorithme de papadimitriou pour résoudre le 2SAt-problem


Sujet :

C++

  1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut algorithme de papadimitriou pour résoudre le 2SAt-problem
    Bonjour à tous, je vous remercie par avance de l'aide que certains pourront m'apporter.

    Je vous poste ici le code puis vous explique exactement ce que je n'arrive pas à faire après des heures et des heures de recherche :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    #include <iostream>
    #include <fstream>
    #include <set>
    #include <string>
    #include <sstream>
    #include <utility>
    #include <algorithm>
    #include <map>
    #include <list>
     
     
     
    class variable {
     
    private:
    	long int var;
    	bool checked;
     
    public:
    	long int get_variable() {return var;};
    	bool isChecked() {return checked;};
    	void setChecked(bool boolean) {checked = boolean;};
    	variable(long int var_, bool checked_) : var(var_), checked(checked_) {}
     
     
    };
     
    class clause {
     
    private:
    	variable var_1;
    	variable var_2;
    	bool expression;
     
    public:
    	bool verified() {return expression;};
    	variable getFirstVar() const {return var_1;};
    	variable getSecondVar() const {return var_2;};
    	clause(variable var_1_, variable var_2_, bool clause_) : var_1(var_1_), var_2(var_2_), expression(clause_) {}
     
    };
     
    std::ostream& operator<<(std::ostream& flux, clause& clause_){
    		if(clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(clause_.getFirstVar().isChecked() and !clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou non" << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(!clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else 
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou non " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		return flux;
    }
     
     
    class problem {
     
    private:
    	typedef std::map<long int, std::map<long int, clause>> myClauses;
    	myClauses clauses;
     
    	typedef std::map<long int, int> myNegations;
    	myNegations negations;
     
    	typedef std::map<long int, int> myClaims;
    	myClaims claims;
     
    public:
    	void create_clause(variable var_1, variable var_2, bool clause_) {
    		clauses[var_1.get_variable()].insert(std::make_pair(var_2.get_variable(), clause(var_1, var_2, clause_)));
    		clauses[var_2.get_variable()].insert(std::make_pair(var_1.get_variable(), clause(var_2, var_1, clause_)));
    	}
     
    	void remove_clause(long int var) {
    		clauses.erase(var);
    		for(auto e = map_iterator(); e!=noMap(); ++e){
    			if(e->second.find(var) != e->second.end())
    				e->second.erase(e->second.find(var));
    		}
    	}
     
    	void create_negation(long int neg) {
    		if(negations.find(neg) == no_more_negation()){
    			negations[neg] = 1;
    		}
    		else
    			negations[neg]++;
    	}
     
    	void create_claim(long int claim) {
    		if(claims.find(claim) == no_more_claim()){
    			claims[claim] = 1;
    		}
    		else{
    			claims[claim]++;
    		}
    	}
     
    	void remove_claim(long int claim) {
    		if(claims.find(claim) != no_more_claim()){
    			if(claims[claim] == 1)
    				claims.erase(claim);
    			else
    				claims[claim]--;
    		}
    	}
     
    	void remove_all_claim(long int claim) {
    		claims.erase(claim);
    	}
     
    	void remove_all_negation(long int neg) {
    		negations.erase(neg);
    	}
     
    	void remove_negation(long int neg) {
    		if(negations.find(neg) != no_more_negation()){
    			if(negations[neg] == 1)
    				negations.erase(neg);
    			else
    				negations[neg]--;
    		}
    	}
     
    	void remove_clause_(long int variable) {
    		for(auto e = clauses[variable].begin(); e!=clauses[variable].end(); ++e){
    			remove_claim(e->second.getSecondVar().get_variable());
    			remove_negation(e->second.getSecondVar().get_variable());
    			clauses[e->second.getSecondVar().get_variable()].erase(variable);
    		}
     
    		clauses.erase(variable);        // on supprime les contraintes liées à variable
    	}
     
    	myClauses get_clauses() {return clauses;};
    	myNegations get_negations() {return negations;};
    	myClaims get_claims() {return claims;};
     
    	bool contains_claim(long int var) {if(claims.find(var) != no_more_claim()) return true; else return false;};
    	bool contains_neg(long int neg) {if(negations.find(neg) != no_more_negation()) return true; else return false;};
     
    	std::map<long int, std::map<long int, clause>>::iterator map_iterator() {return clauses.begin();};
    	std::map<long int, std::map<long int, clause>>::iterator noMap() {return clauses.end();};
     
    	std::map<long int, clause>::iterator clause_iterator(std::map<long int, clause> m) {return m.begin();};
    	std::map<long int, clause>::iterator noClause(std::map<long int, clause> m) {return m.end();};
     
    	std::map<long int, int>::iterator negation_iterator() {return negations.begin();};
    	std::map<long int, int>::iterator no_more_negation() {return negations.end();};
     
    	std::map<long int, int>::iterator claim_iterator() {return claims.begin();};
    	std::map<long int, int>::iterator no_more_claim() {return claims.end();};
    };
     
    problem parse(const char* filename) {
    	problem prob;
     
    	std::string line;
    	std::ifstream fichier(filename);
     
    	getline(fichier, line);
     
    	while(std::getline(fichier, line)){
    		std::istringstream iss(line);
     
    		long int var1, var2;
     
    		iss >> var1 >> var2;
     
    		variable variable1(abs(var1), true);
    		variable variable2(abs(var2), true);
     
    		if(var1 < 0 and var2 > 0) {	
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_claim(var2);
    		}
    		else if(var1 < 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || !variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_negation(abs(var2));
    		}
    		else if(var1 > 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, variable1.isChecked() || !variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_negation(abs(var2));
    		}
    		else {
    			prob.create_clause(variable1, variable2, variable1.isChecked() || variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_claim(var2);
    		}
    	}
     
    	return prob;
    }
     
    int simplify_problem(problem& prob) {
    	int nb_deletions(0);
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){
    		if(!prob.contains_neg(e->first)){
    			prob.remove_clause_(e->first);
    			prob.remove_all_claim(e->first);
    			nb_deletions++;
    		}
    	}
     
    	for(auto e = prob.negation_iterator(); e != prob.no_more_negation(); ++e){
    		if(!prob.contains_claim(e->first)){
    			prob.remove_clause_(e->first);
    			prob.remove_all_negation(e->first);
    			nb_deletions++;
    		}
    	}
     
    	return nb_deletions;
    }
     
    int main(int argc, char* argv[]) {
     
    	problem prob = parse("2sat1.txt");
     
    	long int k(0);
    	for(auto e = prob.map_iterator(); e!= prob.noMap(); ++e){
    		for(auto l = e->second.begin(); l!= e->second.end(); ++l){
    			k++;
    		}
    	}
     
     
    	std::cout << k << std::endl;
     
    	int nb_deletions(-1);
    	while(nb_deletions != 0){
    		nb_deletions = simplify_problem(prob);
    		std::cout << nb_deletions << std::endl;
    	}
     
    	k = 0;
    	for(auto e = prob.map_iterator(); e!= prob.noMap(); ++e){
    		for(auto l = e->second.begin(); l!= e->second.end(); ++l)
    			k++;
    	}
    	std::cout << k / 2 << " constraints " << std::endl;
     
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){
    		if(!prob.contains_neg(e->first))
    			std::cout << "un intrus " << e->first << std::endl;
    	}
     
    	for(auto e = prob.negation_iterator(); e!=prob.no_more_negation(); ++e){
    		if(!prob.contains_claim(e->first))
    			std::cout << "un intrus " << e->second << std::endl;
    	}
     
    	return 0;
    }
    Le fond du problème ce sont les fonctions simplify_problem et remove_clause. En fait je dois simplifier mon problème selon le principe suivant, prenons l'exemple : (les variables sont toutes booleennes)

    contrainte 1 : A ou non(B)
    contrainte 2 : B ou non(C)
    contrainte 3 : A ou C

    On voit que non(A) n'apparait jamais donc on peut supprimer A de la liste des variables et toutes les clauses qui impliquent A soit les contraintes 1 et 3. Mais en faisant cela on s'aperçoit que maintenant C et non(B) n'apparaissent jamais donc on peut supprimer B et C ainsi que toutes les clauses impliquant B et C.

    Et bien ma fonction simplify_problem a pour but de faire une itération et la boucle

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    int nb_deletions(-1);
    	while(nb_deletions != 0){
    		nb_deletions = simplify_problem(prob);
    		std::cout << nb_deletions << std::endl;
    	}
    a pour but de répéter l'opération tant qu'on peut supprimer des contraintes.

    Pour ce faire voici comment j'opère, je parcours la map dans laquelle se trouvent mes variables claims (les variables qui apparaissent sous la forme A) et je regarde si ma variable se trouve aussi dans mes variables negations (celles qui apparaissent dans les contraintes sous la forme non(A)). Si elle n'apparait pas c'est que je peux la supprimer et toutes les contraintes qui vont avec !

    Ca c'est a priori relativement facile, ce qui l'est moins (pour moi en tout cas). C'est que pour reprendre l'exemple basique que j'ai montré une fois que j'ai supprimé la contrainte 1, non(B) n'apparait plus dans mes negations et donc je dois l'enlever.

    En fait ce qui est compliqué c'est que j'ai 100 000 contraintes dans le fichier qui décrit l'instance de mon problème : et A peut apparaitre plusieurs fois dans claims ou dans negations.

    Si c'est la variable que je regarde et qu'elle n'appartient pas à mes deux maps (claims et negations) alors je supprime complètement la variable de claims ou de négations mais si c'est une variable impliquée dans une contrainte comme par exemple B dans mon exemple je ne supprime que "une présence" (elle peut apparaitre dans plusieurs contraintes sous la forme non(B) par exemple A et non(B), D et non(B) et donc je ne dois pas la supprimer d'un coup).

    Pour ce faire j'ai codé remove_claim et remove_negation mais ça ne marche pas, il me reste à la fin 34 975 contraintes alors qu'il devrait m'en rester 6...

  2. #2
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    Et tu peux confirmer avec un problème à 50 contraintes?

    Parce que sur 100000, tu ne peux bien évidemment pas contrôler le code à la main.

    Je te suggère d'avoir (temporairement?) quelques fonctions supplémentaires:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    pick_free_constraint() (et has_free_constraint()), qui sélection (ou dit s'il existe) une contrainte libre
    et simplify_by_constraint(...), qui simplifie le problème pour une seule contrainte libre
    ainsi, qu'un operator<< pour ostream
    ainsi, tu pourras écrire
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    while(pb.has_free_constraint()) {
        ... constraint = pb.pick_free_constraint();
        pb.simplify_by_constraint(constraint );
        cout << "\tsimplification de "<<constraint<<'\n'<<pb << endl;
    }
    Ainsi, tu auras une trace contrôlable.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  3. #3
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Bonjour leternel merci de ton aide. Je ne suis pas certain d'avoir parfaitement compris ce que tu me proposais alors je vais essayer de clarifier les choses. Qu'appelles-tu simplify_by_constraint ? Parce que la fonction simplify avance plus par variable que par contrainte donc je ne vois pas ce que devrais faire cette fonction pour etre intéressante selon toi ?

    J'ai mis à jour mon code : il ne me reste plus que 10801 contraintes et j'ai 2473 variables negations et claims (donc pas trop mal puisque j'en ai au moins le même nombre ce qui est cohérent).

    Tu verras que je suis passé à std::map<long int, std::map<long int, clause>> pour stocker mes clauses. C est pour l'usage suivant :

    si j'ai une contrainte x1 ou x2 et que je m'intéresse à la variable x1, je dois supprimer toutes les contraintes liées à x1 (ça ça va) mais aussi la contrainte x1 ou x2 qui se trouve dans clauses[x2] et c'était impossible (ou trop difficile) avec une list

    Le problème c'est que maintenant je n'ai plus trop d'idées pour progresser dans monprogramme.

  4. #4
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Pour l'opérateur j'ai codé ça, est ce que c'est ce que tu attendais ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    std::ostream& operator<<(std::ostream& flux, clause& clause_){
    		if(clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(clause_.getFirstVar().isChecked() and !clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou non" << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(!clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else 
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou non " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		return flux;
    }

  5. #5
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Bon je remets le code, maintenant il ne me reste plus aucune variable/contrainte à la fin :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    #include <iostream>
    #include <fstream>
    #include <set>
    #include <string>
    #include <sstream>
    #include <utility>
    #include <algorithm>
    #include <map>
    #include <list>
     
     
     
    class variable {
     
    private:
    	long int var;
    	bool checked;
     
    public:
    	long int get_variable() {return var;};
    	bool isChecked() {return checked;};
    	void setChecked(bool boolean) {checked = boolean;};
    	variable(long int var_, bool checked_) : var(var_), checked(checked_) {}
     
     
    };
     
    class clause {
     
    private:
    	variable var_1;
    	variable var_2;
    	bool expression;
     
    public:
    	bool verified() {return expression;};
    	variable getFirstVar() const {return var_1;};
    	variable getSecondVar() const {return var_2;};
    	clause(variable var_1_, variable var_2_, bool clause_) : var_1(var_1_), var_2(var_2_), expression(clause_) {}
     
    };
     
    std::ostream& operator<<(std::ostream& flux, clause& clause_){                              // pour pouvoir afficher une clause
    		if(clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(clause_.getFirstVar().isChecked() and !clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou non" << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(!clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else 
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou non " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		return flux;
    }
     
     
    class problem {
     
    private:
    	typedef std::map<long int, std::map<long int, clause>> myClauses;
    	myClauses clauses;
     
    	typedef std::map<long int, int> myNegations;
    	myNegations negations;
     
    	typedef std::map<long int, int> myClaims;
    	myClaims claims;
     
    public:
    	void create_clause(variable var_1, variable var_2, bool clause_) {
    		clauses[var_1.get_variable()].insert(std::make_pair(var_2.get_variable(), clause(var_1, var_2, clause_))); // on ajoute chaque contrainte deux fois
    		clauses[var_2.get_variable()].insert(std::make_pair(var_1.get_variable(), clause(var_2, var_1, clause_))); // sous la forme clauses[x1][x2] et clauses[x2][x1]
    	}
     
    	void create_negation(long int neg) {
    		if(negations.find(neg) == no_more_negation()){
    			negations[neg] = 1;
    		}
    		else
    			negations[neg]++;
    	}
     
    	void create_claim(long int claim) {                // si la variable n'existe pas dans claim on la crée et l'ajoute 
    		if(claims.find(claim) == no_more_claim()){
    			claims[claim] = 1;
    		}
    		else{
    			claims[claim]++;                          // sinon on ajoute 1 au nombre de fois que la variable apparait (en positif)
    		}
    	}
     
    	void remove_claim(long int claim) {               
    		if(claims.find(claim) != no_more_claim()){  // si la variable existe dans claim
    			if(claims[claim] == 1)                   // si elle est présente une fois elle va disparaitre donc on la supprime de la map
    				claims.erase(claim);
    			else
    				claims[claim]--;                      // sinon on décrémente le nombre d'apparitions de 1
    		}
    	}
     
    	void remove_all_claim(long int claim) {
    		claims.erase(claim);
    	}
     
    	void remove_all_negation(long int neg) {
    		negations.erase(neg);
    	}
     
    	void remove_negation(long int neg) {
    		if(negations.find(neg) != no_more_negation()){
    			if(negations[neg] == 1)
    				negations.erase(neg);
    			else
    				negations[neg]--;
    		}
    	}
     
    	void remove_clause_(long int variable) {
    		for(auto e = clauses[variable].begin(); e!=clauses[variable].end(); ++e){
    			if(e->second.getSecondVar().isChecked()){
    				remove_claim(e->second.getSecondVar().get_variable()); 	
    			}	
    			else{															//on décrémente le nbr d'apparations dans claims ou négations de la variation impliquée 
    				remove_negation(e->second.getSecondVar().get_variable());
    			}				// dans la contrainte avec la variable "variable"
    			clauses[e->second.getSecondVar().get_variable()].erase(variable);		// on supprime les contraintes du style map[x][variable] qui sont les symétriques de
    		}																			// celles qu'on supprime juste après
     
    		clauses.erase(variable);        // on supprime les contraintes liées à variable dans map[variable] donc ça supprime une map<long int(la variable), clause>
    	}
     
    	myClauses get_clauses() {return clauses;};
    	myNegations get_negations() {return negations;};
    	myClaims get_claims() {return claims;};
     
    	bool contains_claim(long int var) {if(claims.find(var) != no_more_claim()) return true; else return false;};
    	bool contains_neg(long int neg) {if(negations.find(neg) != no_more_negation()) return true; else return false;};
     
    	std::map<long int, std::map<long int, clause>>::iterator map_iterator() {return clauses.begin();};
    	std::map<long int, std::map<long int, clause>>::iterator noMap() {return clauses.end();};
     
    	std::map<long int, clause>::iterator clause_iterator(std::map<long int, clause> m) {return m.begin();};
    	std::map<long int, clause>::iterator noClause(std::map<long int, clause> m) {return m.end();};
     
    	std::map<long int, int>::iterator negation_iterator() {return negations.begin();};
    	std::map<long int, int>::iterator no_more_negation() {return negations.end();};
     
    	std::map<long int, int>::iterator claim_iterator() {return claims.begin();};
    	std::map<long int, int>::iterator no_more_claim() {return claims.end();};
    };
     
    problem parse(const char* filename) {
    	problem prob;
     
    	std::string line;
    	std::ifstream fichier(filename);
     
    	getline(fichier, line);
     
    	while(std::getline(fichier, line)){
    		std::istringstream iss(line);
     
    		long int var1, var2;
     
    		iss >> var1 >> var2;
     
    		variable variable1(abs(var1), true);
    		variable variable2(abs(var2), true);
     
    		if(var1 < 0 and var2 > 0) {	
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_claim(var2);
    		}
    		else if(var1 < 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || !variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_negation(abs(var2));
    		}
    		else if(var1 > 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, variable1.isChecked() || !variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_negation(abs(var2));
    		}
    		else {
    			prob.create_clause(variable1, variable2, variable1.isChecked() || variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_claim(var2);
    		}
    	}
     
    	return prob;
    }
     
    int simplify_problem(problem& prob) {
    	int nb_deletions(0);
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){ // on parcourt les claims et on vérifie qu'elles sont dans les negations
    		if(!prob.contains_neg(e->first)){  
    			prob.remove_all_claim(e->first);              //si c'est pas le cas
    			prob.remove_clause_(e->first);					// on supprime les clauses liées à la variable en question																// on supprime la variable de la map claims
    			nb_deletions++;
    		}
    	}
     
    	for(auto e = prob.negation_iterator(); e != prob.no_more_negation(); ++e){  // on parcourt les negations et ...
    		if(!prob.contains_claim(e->first)){
    			prob.remove_clause_(e->first);						
    			prob.remove_all_negation(e->first);
    			nb_deletions++;
    		}
    	}
     
    	return nb_deletions;
    }
     
    int main(int argc, char* argv[]) {
     
    	problem prob = parse("2sat1.txt");
     
    	int nb_deletions(-1);
    	while(nb_deletions != 0){
    		nb_deletions = simplify_problem(prob);
    		std::cout << nb_deletions << std::endl;
    	}
     
     
    	return 0;
    }
    Voici comment je m'y prends :

    dans la fonction remove_clause_ :

    je regarde dans clauses[variable] qui est une std::map<long int, clause> puis je regarde la seconde variable impliquée dans la cause (car c'est celle qui n'est pas la variable "variable") si jamais elle a été set à "true" c'est qu'elle est dans claims auquel cas je mets à jour la map claims, sinon je mets à jour la map negations.

    Ensuite je supprime clauses[la_variable_impliquée][variable] qui est la clause symmétrique (je rappelle que au début j'ajoute à la fois clauses[x1][x2] et clauses[x2][x1]

    Enfin je supprime clauses[variable] qui contient naturellement toutes les clauses impliquant ma variable.

    Malheureusement au terme de ce travail je supprime littéralement toutes les contraintes alors qu'il devrait m'en rester 6.

  6. #6
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Points : 16 213
    Points
    16 213
    Par défaut
    Tu devrais vraiment mettre en place des tests unitaires (et j'entends par là des tests totalement automatisés, regarde par exemple les bibliothèques boost.test ou googletest) pour ton algo...

    Commence par des cas simples, genre une clause, une variable, vérifie que ça marche.
    Puis complexifie peu à peu, par exemple, 2 clauses, mais tu testes uniquement la partie qui détermine si une variable est à enlever (en t'assurant grâce à plusieurs tests que tu gères bien les différents cas). Puis tu testes uniquement la partie qui enlève une variable. Puis tu teste la totalité. Tu n'oublies pas de tester les cas aux limites (si tu as 0 clauses, si tu ne peux supprimer aucune variable, si tu peux toutes les supprimer...).

    À chaque étape, tu ré-exécutes l'ensemble des tests déjà existants afin te t'assurer que tu n'as rien cassé, éventuellement, tu corriges.

    Ce n'est que comme ça, en bâtissant des bases robustes, que tu arriveras à gérer le cas global. Et à avoir confiance que tu le gères correctement.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  7. #7
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    J'ai finalement réussi à régler mon problème JolyLoic mais je te remercie de tes conseils j'espère que j'aurai l'occasion de m'en servir un jour !

  8. #8
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    J'ai apporté quelques améliorations à ton code, du point de vue lisibilité.

    Peux-tu nous dire comment tu as résolu ton problème?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    #include <iostream>
    #include <fstream>
    #include <set>
    #include <string>
    #include <sstream>
    #include <utility>
    #include <algorithm>
    #include <map>
    #include <list>
     
    using id_t = long int;
     
    class variable {
     
    private:
    	id_t var;
    	bool checked;
     
    public:
    	variable(id_t var, bool checked) : var(var_), checked(checked_) {}
     
    	id_t operator* () const {return var;}
     
    	operator bool() const {return checked;}
    	bool operator !() const {return !checked;}
     
    	id_t id() const {return var;};
    };
     
    std::ostream& operator<<(std::ostream& os, variable const& that) {
    	if (!that) os << "non ";
    	return os << *that;
    }
     
     
    class clause {
     
    private:
    	variable var_1;
    	variable var_2;
    	bool expression;
     
    public:
    	clause(variable const& var_1, variable const& var_2, bool verified) : var_1(var_1), var_2(var_2), expression(verified) {}
     
    	bool verified() const {return expression;};
    	variable getFirstVar() const {return var_1;};
    	variable getSecondVar() const {return var_2;};
    };
     
    std::ostream& operator<<(std::ostream& flux, const clause& that) {
    	return flux << that.getFirstVar() << " ou " << that.getSecondVar() << " : " << that.verified() ;
    }
     
     
    class problem {
     
    private:
    	typedef std::map<id_t, clause> clause_t;
    	typedef std::map<id_t, clause_t> myClauses;
    	myClauses clauses;
     
    	typedef std::map<id_t, int> myNegations;
    	myNegations negations;
     
    	typedef std::map<id_t, int> myClaims;
    	myClaims claims;
     
    public:
    	void create_clause(variable const& a, variable  const& b, bool clause_) {
    		clauses[*a].insert(std::make_pair(*b, clause(a, b, clause_)));
    		clauses[*b].insert(std::make_pair(*a, clause(a, b, clause_)));
    	}
     
    	void remove_clause(id_t var) {
    		clauses.erase(var);
    		for(auto e = map_iterator(); e!=noMap(); ++e){
    			if(e->second.find(var) != e->second.end())
    				e->second.erase(e->second.find(var));
    		}
    	}
     
    	void create_negation(id_t neg) {
    		if(negations.find(neg) == no_more_negation()){
    			negations[neg] = 1;
    		}
    		else
    			negations[neg]++;
    	}
     
    	void create_claim(id_t claim) {
    		if(claims.find(claim) == no_more_claim()){
    			claims[claim] = 1;
    		}
    		else{
    			claims[claim]++;
    		}
    	}
     
    	void remove_claim(id_t claim) {
    		if(claims.find(claim) != no_more_claim()){
    			if(claims[claim] == 1)
    				claims.erase(claim);
    			else
    				claims[claim]--;
    		}
    	}
     
    	void remove_all_claim(id_t claim) {
    		claims.erase(claim);
    	}
     
    	void remove_all_negation(id_t neg) {
    		negations.erase(neg);
    	}
     
    	void remove_negation(id_t neg) {
    		if(negations.find(neg) != no_more_negation()){
    			if(negations[neg] == 1)
    				negations.erase(neg);
    			else
    				negations[neg]--;
    		}
    	}
     
    	void remove_clause_(id_t variable) {
    		for(auto e = clauses[variable].begin(); e!=clauses[variable].end(); ++e){
    			remove_claim(e->second.getSecondVar().id());
    			remove_negation(e->second.getSecondVar().id());
    			clauses[e->second.getSecondVar().id()].erase(variable);
    		}
     
    		// on supprime les contraintes liées à variable
    		clauses.erase(variable);
    	}
     
    	myClauses get_clauses() {return clauses;};
    	myNegations get_negations() {return negations;};
    	myClaims get_claims() {return claims;};
     
    	bool contains_claim(id_t var) {if(claims.find(var) != no_more_claim()) return true; else return false;};
    	bool contains_neg(id_t neg) {if(negations.find(neg) != no_more_negation()) return true; else return false;};
     
    	myClauses::iterator map_iterator() {return clauses.begin();};
    	myClauses::iterator noMap() {return clauses.end();};
     
    	clause_t::iterator clause_iterator(std::map<id_t, clause> m) {return m.begin();};
    	clause_t::iterator noClause(std::map<id_t, clause> m) {return m.end();};
     
    	myNegations::iterator negation_iterator() {return negations.begin();};
    	myNegations::iterator no_more_negation() {return negations.end();};
     
    	myClaims::iterator claim_iterator() {return claims.begin();};
    	myClaims::iterator no_more_claim() {return claims.end();};
     
     
    	int size() const {
    		clause_t::size_type count = 0;
    		for(auto e = map_iterator(); e!= noMap(); ++e){
    			count += e->second.size();
    		}
    		return count;
    	}
     
    	myNegations::size_type negates_count() const {
    		return negations.size();
    	}
     
    	myClaims::size_type claims_count() const {
    		return claims.size();
    	}
     
    };
     
    problem parse(const char* filename) {
    	problem prob;
     
    	std::string line;
    	std::ifstream fichier(filename);
     
    	getline(fichier, line);
     
    	while(std::getline(fichier, line)){
    		std::istringstream iss(line);
     
    		id_t var1, var2;
     
    		iss >> var1 >> var2;
     
    		variable variable1(abs(var1), true);
    		variable variable2(abs(var2), true);
     
    		if(var1 < 0 and var2 > 0) {
    			prob.create_clause(variable1, variable2, !variable1 || variable2);
    			prob.create_negation(abs(var1));
    			prob.create_claim(var2);
    		}
    		else if(var1 < 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, !variable1 || !variable2);
    			prob.create_negation(abs(var1));
    			prob.create_negation(abs(var2));
    		}
    		else if(var1 > 0 and var2 < 0) {
    			prob.create_clause(variable1, variable2, variable1 || !variable2);
    			prob.create_claim(var1);
    			prob.create_negation(abs(var2));
    		}
    		else {
    			prob.create_clause(variable1, variable2, variable1 || variable2);
    			prob.create_claim(var1);
    			prob.create_claim(var2);
    		}
    	}
     
    	return prob;
    }
     
    int simplify_problem(problem& prob) {
    	int nb_deletions(0);
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){
    		if(!prob.contains_neg(e->first)){
    			prob.remove_clause_(e->first);
    			prob.remove_all_claim(e->first);
    			nb_deletions++;
    		}
    	}
     
    	for(auto e = prob.negation_iterator(); e != prob.no_more_negation(); ++e){
    		if(!prob.contains_claim(e->first)){
    			prob.remove_clause_(e->first);
    			prob.remove_all_negation(e->first);
    			nb_deletions++;
    		}
    	}
     
    	return nb_deletions;
    }
     
     
     
    int main(int argc, char* argv[]) {
     
    	problem prob = parse("2sat1.txt");
     
    	std::cout << prob.size() << std::endl;
     
    	int nb_deletions;
    	while((nb_deletions = simplify_problem(prob)) != 0){
    		std::cout << nb_deletions << std::endl;
    	}
     
    	std::cout << prob.size() / 2 << " constraints " << std::endl;
     
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){
    		if(!prob.contains_neg(e->first))
    			std::cout << "un intrus " << e->first << std::endl;
    	}
     
    	for(auto e = prob.negation_iterator(); e!=prob.no_more_negation(); ++e){
    		if(!prob.contains_claim(e->first))
    			std::cout << "un intrus " << e->second << std::endl;
    	}
     
    	return 0;
    }
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  9. #9
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Je te mets le code leternel. Et merci à toi pour avoir réécrit mon code de manière plus lisible .

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    #include <iostream>
    #include <fstream>
    #include <set>
    #include <string>
    #include <sstream>
    #include <utility>
    #include <algorithm>
    #include <map>
    #include <list>
    #include <ctime>
     
     
     
    class variable {
     
    private:
    	long int var;
    	bool checked;
     
    public:
    	long int get_variable() {return var;};
    	bool isChecked() {return checked;};
    	void setChecked(bool boolean) {checked = boolean;};
    	variable(long int var_, bool checked_) : var(var_), checked(checked_) {}
     
     
    };
     
    class clause {
     
    private:
    	variable var_1;
    	variable var_2;
    	bool expression;
     
    public:
    	bool verified() {return expression;};
    	variable getFirstVar() const {return var_1;};
    	variable getSecondVar() const {return var_2;};
    	clause(variable var_1_, variable var_2_, bool clause_) : var_1(var_1_), var_2(var_2_), expression(clause_) {}
     
    };
     
    std::ostream& operator<<(std::ostream& flux, clause& clause_){                              // pour pouvoir afficher une clause
    		if(clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(clause_.getFirstVar().isChecked() and !clause_.getSecondVar().isChecked())
    			flux << clause_.getFirstVar().get_variable() << " ou non " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else if(!clause_.getFirstVar().isChecked() and clause_.getSecondVar().isChecked())
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		else 
    			flux << "non " << clause_.getFirstVar().get_variable() << " ou non " << clause_.getSecondVar().get_variable() << " : " << clause_.verified() ;
    		return flux;
    }
     
    struct clause_compare {
    	bool operator() (clause const& c1, clause const& c2){
    		return c1.getFirstVar().get_variable() < c2.getFirstVar().get_variable() ;
    	}
    };
     
    class problem {
     
    private:
    	typedef std::map<long int, std::map<long int, clause>> myClauses;
    	myClauses clauses;
     
    	typedef std::map<long int, int> myNegations;
    	myNegations negations;
     
    	typedef std::map<long int, int> myClaims;
    	myClaims claims;
     
    	typedef std::set<clause, clause_compare> myfailedClauses;
    	myfailedClauses failedClauses;
     
    public:
    	void create_clause(variable var_1, variable var_2, bool clause_) {
    		clauses[var_1.get_variable()].insert(std::make_pair(var_2.get_variable(), clause(var_1, var_2, clause_))); // on ajoute chaque contrainte deux fois
    		clauses[var_2.get_variable()].insert(std::make_pair(var_1.get_variable(), clause(var_2, var_1, clause_))); // sous la forme clauses[x1][x2] et clauses[x2][x1]
    	}
     
    	void create_negation(long int neg) {
    		if(negations.find(neg) == no_more_negation()){
    			negations[neg] = 1;
    		}
    		else
    			negations[neg]++;
    	}
     
    	void create_claim(long int claim) {                // si la variable n'existe pas dans claim on la crée et l'ajoute 
    		if(claims.find(claim) == no_more_claim()){
    			claims[claim] = 1;
    		}
    		else{
    			claims[claim]++;                          // sinon on ajoute 1 au nombre de fois que la variable apparait (en positif)
    		}
    	}
     
    	void remove_claim(long int claim) {               
    		if(claims.find(claim) != no_more_claim()){  // si la variable existe dans claim
    			if(claims[claim] == 1)                   // si elle est présente une fois elle va disparaitre donc on la supprime de la map
    				claims.erase(claim);
    			else
    				claims[claim]--;                      // sinon on décrémente le nombre d'apparitions de 1
    		}
    	}
     
    	void remove_all_claim(long int claim) {
    		claims.erase(claim);
    	}
     
    	void remove_all_negation(long int neg) {
    		negations.erase(neg);
    	}
     
    	void remove_negation(long int neg) {
    		if(negations.find(neg) != no_more_negation()){
    			if(negations[neg] == 1)
    				negations.erase(neg);
    			else
    				negations[neg]--;
    		}
    	}
     
    	void remove_clause_(long int variable) {
    		for(auto e = clauses[variable].begin(); e!=clauses[variable].end(); ++e){
    			if(e->second.getSecondVar().isChecked()){
    				remove_claim(e->second.getSecondVar().get_variable()); 	
    			}	
    			else{																	//on décrémente le nbr d'apparations dans claims ou négations de la variation impliquée 
    				remove_negation(e->second.getSecondVar().get_variable());
    			}																		// dans la contrainte avec la variable "variable"
    			clauses[e->second.getSecondVar().get_variable()].erase(variable);		// on supprime les contraintes du style map[x][variable] qui sont les symétriques de
    		}																			// celles qu'on supprime juste après
     
    		clauses.erase(variable);        // on supprime les contraintes liées à variable dans map[variable] donc ça supprime une map<long int(la variable), clause>
    	}
     
    	void rem_clause(long int var) {
    		clauses.erase(var);
    	}
     
    	myClauses get_clauses() {return clauses;};
    	myNegations get_negations() {return negations;};
    	myClaims get_claims() {return claims;};
    	myfailedClauses get_failed_clauses() {return failedClauses;};
     
    	bool contains_claim(long int var) {if(claims.find(var) != no_more_claim()) return true; else return false;};
    	bool contains_neg(long int neg) {if(negations.find(neg) != no_more_negation()) return true; else return false;};
     
    	std::map<long int, std::map<long int, clause>>::iterator map_iterator() {return clauses.begin();};
    	std::map<long int, std::map<long int, clause>>::iterator noMap() {return clauses.end();};
     
    	std::map<long int, clause>::iterator clause_iterator(std::map<long int, clause> m) {return m.begin();};
    	std::map<long int, clause>::iterator noClause(std::map<long int, clause> m) {return m.end();};
     
    	std::map<long int, int>::iterator negation_iterator() {return negations.begin();};
    	std::map<long int, int>::iterator no_more_negation() {return negations.end();};
     
    	std::map<long int, int>::iterator claim_iterator() {return claims.begin();};
    	std::map<long int, int>::iterator no_more_claim() {return claims.end();};
    };
     
    problem parse(const char* filename) {
    	problem prob;
     
    	std::string line;
    	std::ifstream fichier(filename);
     
    	getline(fichier, line);
     
    	while(std::getline(fichier, line)){
    		std::istringstream iss(line);
     
    		long int var1, var2;
     
    		iss >> var1 >> var2;
     
    		if(var1 < 0 and var2 > 0) {	
    			variable variable1(abs(var1), false);
    			variable variable2(var2, true);
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_claim(var2);
    		}
    		else if(var1 < 0 and var2 < 0) {
    			variable variable1(abs(var1), false);
    			variable variable2(abs(var2), false);
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || !variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_negation(abs(var2));
    		}
    		else if(var1 > 0 and var2 < 0) {
    			variable variable1(var1, true);
    			variable variable2(abs(var2), false);
    			prob.create_clause(variable1, variable2, variable1.isChecked() || !variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_negation(abs(var2));
    		}
    		else {
    			variable variable1(var1, true);
    			variable variable2(var2, true);
    			prob.create_clause(variable1, variable2, variable1.isChecked() || variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_claim(var2);
    		}
    	}
     
    	return prob;
    }
     
    int simplify_problem(problem& prob) {
    	int nb_deletions(0);
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){ // on parcourt les claims et on vérifie qu'elles sont dans les negations
    		if(!prob.contains_neg(e->first)){ 
    			prob.remove_clause_(e->first);	 
    			prob.remove_all_claim(e->first);              //si c'est pas le cas	// on supprime les clauses liées à la variable en question																// on supprime la variable de la map claims
    			nb_deletions++;
    		}
    	}
     
    	for(auto e = prob.negation_iterator(); e != prob.no_more_negation(); ++e){  // on parcourt les negations et ...
    		if(!prob.contains_claim(e->first)){
    			prob.remove_clause_(e->first);						
    			prob.remove_all_negation(e->first);
    			nb_deletions++;
    		}
    	}
     
    	return nb_deletions;
    }
     
    void flip_value(clause& clause_) {
    	int r(rand()%2);
    	if(r==0)
    		clause_.getFirstVar().setChecked(!clause_.getFirstVar().isChecked());
    	else 
    		clause_.getSecondVar().setChecked(!clause_.getSecondVar().isChecked());
    }
     
     
    bool papadimitriou(problem& prob) {
    	int nb_deletions(-1);
    	while(nb_deletions != 0){
    		nb_deletions = simplify_problem(prob);
    	}
     
    	for(auto e = prob.map_iterator(); e != prob.noMap(); ++e){ 						//pour remove les doublons
    		for(auto el = e->second.begin(); el != e->second.end(); ++el){
    			prob.rem_clause(el->first);
    			if(!el->second.verified())
    				prob.get_failed_clauses().insert(el->second);
     
    		}
    	}
    	return true;
    }
    Alors le problème que j'avais c'est que dans la fonction remove_clause_ je faisais remove_claim et remove_negation donc je supprimais une "instance" (ou apparition, je ne sais pas si c'est trop clair, si ce n'est pas le cas je t'expliquerai mieux) dans chacune des listes systématiquement alors qu'il faut choisir : si jamais la variable apparait sous la forme "non" il faut appeler remove_negation et sinon il faut appeler remove_claim.

    Le deuxième problème c'était dans l'initialisation des variables. Selon qu'elles apparaissent dans le fichier sous la forme "non x1" ou "x1" je pensais au départ qu'initialiser tout le monde à true n'avait pas d'importance mais cela en a donc j'ai corrigé cela.

  10. #10
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    J'aime bien ton style de code, mais il y a un principe qu'il faudrait revoir.

    Par exemple flip value:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class variable {
    private:
    	bool checked;
    public:
    	bool isChecked() {return checked;};
    	void setChecked(bool boolean) {checked = boolean;};
    };//j'ai enlevé l'inutile...
     
     
    void flip_value(clause& clause_) {
    	int r(rand()%2);
    	if(r==0)
    		clause_.getFirstVar().setChecked(!clause_.getFirstVar().isChecked());
    	else 
    		clause_.getSecondVar().setChecked(!clause_.getSecondVar().isChecked());
    }
    je préfère, et recommande que, le comportement propre à un objet soit défini par la classe.
    Le fait de changer l'état d'une propriété de la variable en fonction de son état actuel devrait être une de ses fonctions.

    en l'occurence, j'écrirai:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class variable {
    private:
    	bool checked;
    public:
    	bool isChecked() const {return checked;}
    	void setChecked(bool boolean) {checked = boolean;}
     
    	bool toogle() {return checked = !checked;}
     
    };//j'ai enlevé l'inutile...
     
    void flip_value(clause& clause_) {
    	int r(rand()%2);
    	if(r==0)
    		clause_.getFirstVar().toogle();
    	else 
    		clause_.getSecondVar().toogle();
    }
     
    //ou en plus fun
    void random_flip(clause& clause_) {
    	(rand()%2  ? clause_.getFirstVar() : clause_.getSecondVar() ) .toogle();
    }
    Attention aussi à la const-correctness.
    Prends l'habitude d'utiliser des variables (et surtout des références) constantes aussi souvent que possible.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  11. #11
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Merci leternel, j'espère que tu aimes parce que je prends exemple sur ce code que tu m'avais écrit il y a 3 semaines environ. Et oui pour la fonction flip j'avais hésité à la mettre dedans et j'aurais du ! Et tu as aussi raison à propos des références, j'étais un peu fatigué je n'ai pas pris que les meilleures décisions :p. En tout cas merci encore pour le travail que tu réalises sur mon code, je risque de venir vers vous les gars si jamais je n'arrive pas à implémenter la suite.

  12. #12
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    Au plaisir

    Si j'ai un peu de temps, je verrai pour réécrire ton code plus à ma sauce, avec des commentaires sur le pourquoi du style.

    Je réalise que c'est toi qui avait lancé le sujet sur Belmann Ford...
    Apparemment, j'aime bien tes sujets
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  13. #13
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Hey salut leternel et les autres,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    #include <iostream>
    #include <fstream>
    #include <set>
    #include <string>
    #include <sstream>
    #include <utility>
    #include <algorithm>
    #include <map>
    #include <list>
    #include <ctime>
     
    using id_t = long int;
     
    class variable {
     
    private:
    	id_t var;
    	bool checked;
     
    public:
    	variable(id_t var_, bool checked_) : var(var_), checked(checked_) {}
     
    	id_t operator* () const {return var;}
    	operator bool() const {return checked;}
    	bool operator !() const {return !checked;}
     
    	bool isChecked() {return checked;};
    	void setChecked(bool boolean) {checked = boolean;};
     
    	id_t id() const {return var;};
    	bool toggle() {return checked = !checked;};
     
    };
     
    std::ostream& operator<<(std::ostream& os, variable const& that) {
    	if (!that) os << "non ";
    	return os << *that;
    }
     
    class clause {
     
    private:
    	variable var_1;
    	variable var_2;
    	bool expression;
     
    public:
    	bool verified() const {return expression;};
    	variable getFirstVar() const {return var_1;};
    	variable getSecondVar() const {return var_2;};
    	clause(variable var_1_, variable var_2_, bool clause_) : var_1(var_1_), var_2(var_2_), expression(clause_) {}
     
    };
     
    std::ostream& operator<<(std::ostream& flux, const clause& that) {
    	return flux << that.getFirstVar() << " ou " << that.getSecondVar() << " : " << that.verified() ;
    }
     
    struct clause_compare {
    	bool operator() (clause const& c1, clause const& c2){
    		return c1.getFirstVar().id() < c2.getFirstVar().id() ;
    	}
    };
     
    class problem {
     
    private:
    	typedef std::map<id_t, clause> clause_t;
    	typedef std::map<id_t, clause_t> myClauses;
    	myClauses clauses;
     
    	typedef std::map<id_t, int> myNegations;
    	myNegations negations;
     
    	typedef std::map<id_t, int> myClaims;
    	myClaims claims;
     
    	typedef std::set<clause, clause_compare> myfailedClauses;
    	myfailedClauses failedClauses;
     
    public:
    	void create_clause(variable const& var_1, variable const& var_2, bool clause_) {
    		clauses[*var_1].insert(std::make_pair(*var_2, clause(var_1, var_2, clause_))); // on ajoute chaque contrainte deux fois
    		clauses[*var_2].insert(std::make_pair(*var_1, clause(var_2, var_1, clause_))); // sous la forme clauses[x1][x2] et clauses[x2][x1]
    	}
     
    	void create_negation(id_t neg) {
    		if(negations.find(neg) == no_more_negation()){
    			negations[neg] = 1;
    		}
    		else
    			negations[neg]++;
    	}
     
    	void create_claim(id_t claim) {                // si la variable n'existe pas dans claim on la crée et l'ajoute 
    		if(claims.find(claim) == no_more_claim()){
    			claims[claim] = 1;
    		}
    		else{
    			claims[claim]++;                          // sinon on ajoute 1 au nombre de fois que la variable apparait (en positif)
    		}
    	}
     
    	void remove_claim(id_t claim) {               
    		if(claims.find(claim) != no_more_claim()){  // si la variable existe dans claim
    			if(claims[claim] == 1)                   // si elle est présente une fois elle va disparaitre donc on la supprime de la map
    				claims.erase(claim);
    			else
    				claims[claim]--;                      // sinon on décrémente le nombre d'apparitions de 1
    		}
    	}
     
    	void remove_all_claim(id_t claim) {
    		claims.erase(claim);
    	}
     
    	void remove_all_negation(id_t neg) {
    		negations.erase(neg);
    	}
     
    	void remove_negation(id_t neg) {
    		if(negations.find(neg) != no_more_negation()){
    			if(negations[neg] == 1)
    				negations.erase(neg);
    			else
    				negations[neg]--;
    		}
    	}
     
    	void remove_clause_(id_t variable) {
    		for(auto e = clauses[variable].begin(); e!=clauses[variable].end(); ++e){
    			if(e->second.getSecondVar().isChecked()){
    				remove_claim(e->second.getSecondVar().id()); 	
    			}	
    			else{																	//on décrémente le nbr d'apparations dans claims ou négations de la variation impliquée 
    				remove_negation(e->second.getSecondVar().id());
    			}																		// dans la contrainte avec la variable "variable"
    			clauses[e->second.getSecondVar().id()].erase(variable);		// on supprime les contraintes du style map[x][variable] qui sont les symétriques de
    		}																			// celles qu'on supprime juste après
     
    		clauses.erase(variable);        // on supprime les contraintes liées à variable dans map[variable] donc ça supprime une map<long int(la variable), clause>
    	}
     
    	void rem_clause(id_t var) {
    		clauses.erase(var);
    	}
     
    	myClauses get_clauses() {return clauses;};
    	myNegations get_negations() {return negations;};
    	myClaims get_claims() {return claims;};
    	myfailedClauses get_failed_clauses() {return failedClauses;};
     
    	bool contains_claim(id_t var) {if(claims.find(var) != no_more_claim()) return true; else return false;};
    	bool contains_neg(id_t neg) {if(negations.find(neg) != no_more_negation()) return true; else return false;};
     
    	myClauses::iterator map_iterator() {return clauses.begin();};
    	myClauses::iterator noMap() {return clauses.end();};
     
    	clause_t::iterator clause_iterator(std::map<id_t, clause> m) {return m.begin();};
    	clause_t::iterator noClause(std::map<id_t, clause> m) {return m.end();};
     
    	myNegations::iterator negation_iterator() {return negations.begin();};
    	myNegations::iterator no_more_negation() {return negations.end();};
     
    	myClaims::iterator claim_iterator() {return claims.begin();};
    	myClaims::iterator no_more_claim() {return claims.end();};
     
    	int size() {
    		clause_t::size_type count = 0;
    		for(auto e = map_iterator(); e!= noMap(); ++e){
    			count += e->second.size();
    		}
    		return count;
    	}
     
    	myNegations::size_type negates_count() const {
    		return negations.size();
    	}
     
    	myClaims::size_type claims_count() const {
    		return claims.size();
    	}
    };
     
    problem parse(const char* filename) {
    	problem prob;
     
    	std::string line;
    	std::ifstream fichier(filename);
     
    	getline(fichier, line);
     
    	while(std::getline(fichier, line)){
    		std::istringstream iss(line);
     
    		long int var1, var2;
     
    		iss >> var1 >> var2;
     
    		if(var1 < 0 and var2 > 0) {	
    			variable variable1(abs(var1), false);
    			variable variable2(var2, true);
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_claim(var2);
    		}
    		else if(var1 < 0 and var2 < 0) {
    			variable variable1(abs(var1), false);
    			variable variable2(abs(var2), false);
    			prob.create_clause(variable1, variable2, !variable1.isChecked() || !variable2.isChecked());
    			prob.create_negation(abs(var1));
    			prob.create_negation(abs(var2));
    		}
    		else if(var1 > 0 and var2 < 0) {
    			variable variable1(var1, true);
    			variable variable2(abs(var2), false);
    			prob.create_clause(variable1, variable2, variable1.isChecked() || !variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_negation(abs(var2));
    		}
    		else {
    			variable variable1(var1, true);
    			variable variable2(var2, true);
    			prob.create_clause(variable1, variable2, variable1.isChecked() || variable2.isChecked());
    			prob.create_claim(var1);
    			prob.create_claim(var2);
    		}
    	}
     
    	return prob;
    }
     
    int simplify_problem(problem& prob) {
    	int nb_deletions(0);
    	for(auto e = prob.claim_iterator(); e != prob.no_more_claim(); ++e){ // on parcourt les claims et on vérifie qu'elles sont dans les negations
    		if(!prob.contains_neg(e->first)){ 
    			prob.remove_clause_(e->first);	 
    			prob.remove_all_claim(e->first);              //si c'est pas le cas	// on supprime les clauses liées à la variable en question																// on supprime la variable de la map claims
    			nb_deletions++;
    		}
    	}
     
    	for(auto e = prob.negation_iterator(); e != prob.no_more_negation(); ++e){  // on parcourt les negations et ...
    		if(!prob.contains_claim(e->first)){
    			prob.remove_clause_(e->first);						
    			prob.remove_all_negation(e->first);
    			nb_deletions++;
    		}
    	}
     
    	return nb_deletions;
    }
     
    void flip_value(clause& clause_) {
    	int r(rand()%2);
    	if(r==0)
    		clause_.getFirstVar().toggle();
    	else 
    		clause_.getSecondVar().toggle();
    }
     
     
    bool papadimitriou(problem& prob) {
    	int nb_deletions(-1);
    	while(nb_deletions != 0){
    		nb_deletions = simplify_problem(prob);
    	}
     
    	for(auto e = prob.map_iterator(); e != prob.noMap(); ++e){ 						//pour remove les doublons
    		for(auto el = e->second.begin(); el != e->second.end(); ++el){
    			prob.rem_clause(el->first);
    			if(!el->second.verified())
    				prob.get_failed_clauses().insert(el->second);
     
    		}
    	}
    	return true;
    }
     
     
     
     
     
     
    int main(int argc, char* argv[]) {
     
    	problem prob = parse("2sat1.txt");
     
    	papadimitriou(prob);
     
    	int k(0);
    	for(auto e = prob.map_iterator(); e!=prob.noMap(); ++e){
    		for(auto el = e->second.begin(); el!=e->second.end(); el++){
    			std::cout << el->second << std::endl;
    			k++;
    		}
    	}
     
    	std::cout << k << std::endl;
     
    	return 0;
    }
    je dois coder à partir de la réduction de mon problème l'algorithm suivant :

    repeat log[2](n) times où n est le nombre de variables

    chose random initial assignment (mettre les variables dans un état initial soit faux soit vrai de manière aléatoire)

    repeat 2*n^2 times

    if current assignment all clauses, halt + report this (les variables dans l'état)

    else pick up arbitrary unsastisfied clause and flip the value of one of its variables

    report unsatisfiable

    Je précise que dans mon cas je ne tiens pas particulièrement à connaitre une solution du problème, savoir qu'elle existe me suffit donc en gros si à un moment toutes les clauses sont respectées je report "ok" si à la fin de la boucle extérieure je n'ai pas trouvé de solutions je return "pas ok".

    Mon problème c'est le suivant : quand j'ai simplifié mon problème j'ai initialisé mes variables "en trichant" (je veux dire que dans deux clauses différentes qui utilisent la même variable la variable peut-être dans une initialisation initialisée à false et dans l'autre clause à true mais c'est évidemment interdit dans la solution).

    Je me demande donc comment faire pour créer un "initial assignment" qui soit valable et sur lequel je puisse itérer.

    J'avais pensé à créer dans ma classe problem une map de variable std::map<id_t, bool> qui contient à chaque instant mes variables et leurs valeurs booléennes, qu'en penses-tu ?

    Par ailleurs j'ai codé ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    typedef std::set<clause, clause_compare> myfailedClauses;struct clause_compare {
    	bool operator() (clause const& c1, clause const& c2){
    		return c1.getFirstVar().id() < c2.getFirstVar().id() ;
    	}
    };
    dans le but de ne réaliser la boucle intérieure que sur les clauses qui sont fausses à un instant donné, cela nécessite par contre de maintenir cette propriété lorsque je "flip" une valeur booléenne.

    Penses-tu que dans cette optique un set de clause est la meilleure idée ? As-tu une alternative plus efficace ou même simplement des conseils pour implémenter ma solution correctement ?

    merci infiniment

    En fait je me rends compte qu'un set ça n'est pas très pratique pour accéder à la clause qui nous intéresse. Je me demande si je ferais pas mieux de recréer une std::map<id_t, std::map<id_t, clause>> comme pour mes clauses sauf que dans cette map je ne mettrais que les clauses non vérifiées. Au moins elles seront indexées de la même façon ce qui est plus pratique...

  14. #14
    Membre habitué
    Profil pro
    Inscrit en
    Février 2011
    Messages
    147
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Février 2011
    Messages : 147
    Points : 180
    Points
    180
    Par défaut
    Salut,

    Je suis la discussion depuis un moment car j'avais deja bosse sur 2-SAT.

    Je précise que dans mon cas je ne tiens pas particulièrement à connaitre une solution du problème, savoir qu'elle existe me suffit donc en gros si à un moment toutes les clauses sont respectées je report "ok" si à la fin de la boucle extérieure je n'ai pas trouvé de solutions je return "pas ok".
    Donc, si je comprend bien, tu veux juste avoir la reponse a la question "existe-t-il une distribution qui satisfasse mon probleme ?"
    Dans ce cas, pas besoin de faire tout ce que tu fais, il existe un algorithme lineaire qui repond a ta question (oui 2Sat est dans P)

    Tu peux trouver la description de l'algo dans le papier suivant Aspvall, Plass & Tarjan
    En deux mot, l'idee est de creer des graphes oriente a partir des clauses. Tu vas lier les variables les une aux autres, et si dans un graphe tu as une variable et son contraire, alors tu n'as pas de solution.
    Cet algo ne donne pas d'affectation pour tes variables, il renseigne juste sur l'existence d'une solution. Cependant, les graphes te donne un bon point de depart pour trouver une solution.

  15. #15
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Je te remercie de ta réponse Isangoma mais en fait j'ai oublié de préciser que je devais obligatoirement utiliser cet algorithme . Néanmoins je regarderai le lien que tu m'as donné !

  16. #16
    Membre habitué
    Profil pro
    Inscrit en
    Février 2011
    Messages
    147
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Février 2011
    Messages : 147
    Points : 180
    Points
    180
    Par défaut
    D'accord, on reste sur ton algo alors.

    Depuis le depart, je me pose la question de l'utilise d'un SET dans ton probleme.
    Pourquoi ne pas simplement utiliser un vecteur ?

    Tu as 'n' variables : X1...Xn.
    Pour ta premiere question avec ton probleme pour simplifier les clauses et supprimer les variable qui apparaissent toujours positives ou toujours negative, deux tableaux de booleens auraient fait l'affaire.

    De meme ici. Sachant que tu as 'n' variable, tu crees un nouveau tableau de booleens qui contient l'etat de tes variables.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    vector<bool> litteral_value(N,false);
    for (size_t i = 0; i < N; i++) if (rand()%2 == 0) litteral_value(i) = true;
    Ensuite pour tester si toutes tes clauses sont verifie, il suffit de boucler sur l'ensemble des clauses et de verifier directement dans le tableau.

  17. #17
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Oui c'est vrai pourquoi faire simple quand on peut faire compliqué n'est-ce-pas ?

    Je vais essayer ce que tu m'as gentiment proposé et je reviendrai te dire comment ça se passe. Merci beaucoup de ton aide.

  18. #18
    Membre habitué
    Profil pro
    Inscrit en
    Février 2011
    Messages
    147
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Février 2011
    Messages : 147
    Points : 180
    Points
    180
    Par défaut
    Bonne chance.

  19. #19
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    Tu peux éventuellement passer sur une map<int, bool>, si les variables ne sont pas numérotées continuellement de 0 à max
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  20. #20
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Oui leternel merci c'est ce que j'ai fait en fait ! Pour l'instant ça compile mais j'ai certainement quelques ajustements à faire... je vous tiens au courant.

Discussions similaires

  1. cherche algorithme pour résoudre une question
    Par bayari dans le forum Ruby
    Réponses: 0
    Dernier message: 06/07/2010, 00h35
  2. Algorithme d'indexation pour moteur de recherche
    Par caspertn dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 24/04/2006, 17h57
  3. Comment utiliser Developpez.com pour résoudre votre problème
    Par Anomaly dans le forum Mode d'emploi & aide aux nouveaux
    Réponses: 0
    Dernier message: 08/01/2005, 12h11
  4. La LIB pour résoudre ODBC ?
    Par dede92 dans le forum Windows
    Réponses: 3
    Dernier message: 20/12/2004, 15h23
  5. commande dos pour résoudre une adresse ip
    Par stephy dans le forum Développement
    Réponses: 2
    Dernier message: 17/12/2002, 15h04

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo