Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Contrainte satisfiable ?

Posté par
Alfortville
30-11-14 à 11:34

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

Posté par
Alfortville
re : Contrainte satisfiable ? 22-12-14 à 22:53

Personne ?

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !