O alta solutie se poate realiza daca fixam o variabila $p$ dintr-o propozitie. In cazul acesta suntem obligati sa ii dam o anumita valoare celeilalte variabile din acea propozitie, $q$, ceea ce ne obliga sa atribuim valori si variabilelor care se gasesc in alte propozitii care il contin pe $q$. Astfel "propagam" schimbarile si, daca problema admite solutie vom ajunge la ea, complexitatea finala fiind $O(N * M)$.
Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema sunt mai grele decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile $p$ şi $q$, apoi una dintre ele, de exemplu $p$. Ii atribuim lui $p$ valoarea $0$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr, atunci valoarea lui q trebuie fixată. Fixând si valoarea lui $q$, probabil si alte propoziţii ce conţin literalul $q$ vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări. După ce toate schimbările forţate au fost făcute, propoziţiile rezultate vor fi de următoarele tipuri: $A SAU B$, $1 SAU 0$, $1 SAU 1$, $1 SAU B$. Propozitii de tipul $0 SAU B$ nu pot aparea, pentru ca toate schimbarile fortate au fost deja propagate. Dacă apare o propoziţie $0 SAU 0$ atunci alegerea făcută pentru valoarea lui p este greşită. Vom încerca şi alegerea opusă pentru p. Dacă ambele duc la o propoziţie de tip atunci expresia nu poate fi satisfăcută. Propoziţiile de forma $1 SAU 0$, $1 SAU 1$, $1 SAU B$ pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminat câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate $O(N * M)$, pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată. Aceasta solutie trebuie sa obtina $40$ de puncte, sursa se gaseste aici.
O alta solutie neoptima, in complexitatea $O(N^2^)$ se bazeaza pe un algoritm randomizat. Initial se atribuie valori arbitrare variabilelor, iar apoi cat timp expresia nu este satisfacuta se gaseste o propozitie cu valoarea de adevar $0$ si se schimba valoarea unuia dintre cei 2 termeni componenti ai propozitiei.
O alta solutie neoptima, in complexitatea $O(N^2^)$ se bazeaza pe un algoritm randomizat. Initial se atribuie valori arbitrare variabilelor, iar apoi cat timp expresia nu este satisfacuta se gaseste o propozitie cu valoarea de adevar $0$ si se schimba valoarea unuia dintre cei 2 termeni componenti ai propozitiei. Pentru o demonstratie a functionalitatii acestui algoritm consultati 'articolul':/2-sat#solutie-3
Solutia optima, in complexitatea $O(M + N)$ se foloseste de relatia de implicatie, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand compomentele tare-conexe.
Pentru mai multe detalii in legatura cu solutiile consultati 'articolul':/2-sat
//TODO: Solutia in O(M + N)
Pentru o demonstratie a functionalitatii acestui algoritm consultati 'articolul':/2-sat#solutie-3
*Marius* Cezar, scuze că îţi zic puţin târziu, dar, din punctul meu de vedere nu mai e nevoie să explici în detaliu soluţiile. Sunt deja prezentate în articolul lui Cosmin. Câte cuvinte despre fiecare (cum e la ultima cu algoritmul randomizat) şi o sursă beton sunt de ajuns. Dar să fie beton sursa. :)
h3. Aplicatii
