Comment obtenir des valeurs 2-Sat

Question

Chaque fois que je recherche un algorithme de 2-Sat, je rentrerai l'algorithme de la forme de la décision du problème: existe-t-il un ensemble juridique de valeurs qui satisfont toutes les clauses. Cependant, cela ne me permet pas de trouver facilement un ensemble de valeurs booléennes satisfaisant.

Comment puis-je trouver efficacement un ensemble juridique de valeurs qui satisfera une instance 2-Sat?

Je travaille en C ++ avec la bibliothèque Boost et apprécierait un code qui peut être facilement intégré.

Merci d'avance

Answer 1

Si vous avez un algorithme de décision pour détecter s'il existe une cession valide 2-SAT, vous pouvez l'utiliser pour trouver réellement l'affectation réelle.

run Première 2-SAT algorithme de décision sur l'expression entière. On suppose qu'il dit qu'il ya une cession valide.

Maintenant, si x 1 est un littéral, Assigner x 1 à 0. Maintenant calculer le 2-SAT pour l'expression résultante (vous devrez assigner d'autres littéraux à cause de cela, par exemple, si x 1 OU x_3 apparaît, vous devez également pour définir x_3 à 1).

Si l'expresion résultant est 2-Satisfiable, alors vous pouvez prendre x 1 à 0, sinon prendre 1 x 1.

Maintenant, vous pouvez trouver cela sur chaque littéral.

Pour un algorithme plus efficace, je vous suggère essayer d'utiliser l'approche graphique d'implication.

Vous trouverez plus d'informations ici: http://en.wikipedia.org/wiki/ 2-satisfaisabilité

La partie pertinente:

  

une instance 2-satisfaisabilité est   résoluble si et seulement si toutes les variables   de l'instance appartient à un autre   fortement connexe du composant   graphe d'implication que la négation de   la même variable. depuis fortement   composants connectés peuvent être trouvés dans   temps linéaire par un algorithme basé sur   profondeur première recherche, le même linéaire   le temps lié applique aussi bien à   2-satisfaisabilité.

Les littéraux dans chaque composant fortement connecté sont soit tous égaux à zéro ou tous 1.

Answer 2

Il y a au moins un algorithme qui répertorie toutes les solutions à un problème 2-sam., par Tomas Feder: http://www.springerlink.com/content/j582276p06276l12/