Hoe om 2-za waardes kry

Question

Wanneer ek soek vir 'n algoritme vir 2-Sat, kry ek terug die algoritme vir die besluit vorm van die probleem: Is daar 'n wetlike stel waardes wat al die klousules te bevredig bestaan. Maar dit beteken nie toelaat dat my om maklik te vind 'n stel van voldoening aan boolean waardes.

Hoe kan ek effektief 'n wettige stel waardes wat 'n 2-za byvoorbeeld sal bevredig vind?

Ek werk in C ++ met die hupstoot biblioteek en sou kode wat kan maklik geïntegreer waardeer.

Dankie by voorbaat

Answer 1

As jy 'n besluit algoritme vir die opsporing van as daar 'n geldige opdrag om 2-SAT, kan jy gebruik dat om werklik uit te vind die werklike opdrag.

Eerste hardloop 2-SAT besluit algoritme op die hele uitdrukking. Aanvaar dit sê daar is 'n geldige opdrag.

Nou as x_1 is 'n letterlike, Ken x_1 te wees 0. Nou bereken die 2-SAT vir die gevolglike uitdrukking (jy sal 'n paar ander vasgekodeerde as gevolg van hierdie toewys, byvoorbeeld as x_1 OR x_3 verskyn, het jy ook ' om set x_3 om 1).

As die gevolglike expresión is 2-Satisfiable, dan kan jy x_1 neem om te wees 0, anders neem x_1 tot 1.

Nou kan jy hierdie uit te vind oor elke letterlike.

Vir 'n meer doeltreffende algoritme, ek stel voor jy probeer om met behulp van die implikasie grafiek benadering.

Jy kan meer inligting hier vind: http://en.wikipedia.org/wiki/ 2-satisfiability

Die betrokke gedeelte:

  

'n 2-satisfiability byvoorbeeld is   oplosbare as en slegs as elke veranderlike   van die geval behoort aan 'n ander   sterk verbind komponent van die   implikasie grafiek as die ontkenning van   dieselfde veranderlike. sedert sterk   verbind komponente te vinde in   lineêre tyd deur 'n algoritme wat gebaseer is op   diepte eerste soek, dieselfde lineêre   tydgebonde geld sowel vir   2-satisfiability.

Die vasgekodeerde in elke sterk verbind komponent is óf al nul of al 1.

Answer 2

Daar is ten minste een algoritme wat lyste al die oplossings vir 'n 2-sit probleem, deur Tomas Feder: http://www.springerlink.com/content/j582276p06276l12/