Bonjour à tous! Je cherche à comprendre l'algorithme suivant qui est sensé déterminer l'ensemble des contraintes satisfiables. On considère qu'il existe uniquement 3 couleurs: Rouge, Vert et Bleu.


Le but de cette partie est de fournir et d'implémenter un algorithme randomisé qui décide
s'il existe une assignation qui satisfait un ensemble de contraintes.
Dans cette partie, on regarde uniquement les problèmes où les contraintes sont binaires
(concernent deux variables) ou unaires (concernent une seule variable). On note (3, 2) − SSS
le problème correspondant.
L'algorithme proposé fonctionne de la manière suivante : il supprime variable après variable
jusqu'à ce qu'il aboutisse à une contradiction, ou qu'il n'y ait plus de variables.

Il fonctionne suivant 4 cas :

1. Soit il y a une variable x qui apparaît dans 3 contraintes unaires, [(x, R)] , [(x, V )] et
[(x, B)]. Auquel cas l'ensemble de contraintes n'est pas satisfiable

2. Soit il existe une variable x qui apparaît dans 2 contraintes unaires, par exemple [(x, R)],
[(x, B)]. Auquel cas on peut éliminer la variable x.

3. Soit il existe une variable x qui apparaît dans une seule contrainte unaire, par exemple
[(x, R)]. Auquel cas on peut éliminer x de la façon suivante.
— Éliminer toutes les contraintes de la forme [(x, R),(y, ·)]
— Pour tout couple de contraintes [(x, V ),(y, b)] et [(x, B),(z, c)], ajouter la contrainte
[(y, b),(z, c)]

4. Sinon, il n'y a que des contraintes binaires.
— On prend la première, disons [(x, R),(y, B)].
— Choisir au hasard (chacune avec probabilité 1/4) une des quatre possibilités suivantes
:
— Ajouter [(x, R)] et [(y, R)]
— Ajouter [(x, R)] et [(y, V )]
— Ajouter [(x, B)] et [(y, B)]
— Ajouter [(x, V )] et [(y, B)]
— Supprimer x et y en utilisant les 3 premiers cas.

Je comprends facilement le premier cas: s'il y a 3 contraintes unaires, on ne pourra pas trouver d'assignation correct. Cependant, je bloque au cas numéro 2. Si quelqu'un pouvait m'aider, ça serait géniale ! Les cas 3 et 4 me paraissent obscures, mais je vais y aller pas après pas !

Bonne journée