Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-01-14 06:20:26.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:2sat.in, 2sat.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deCezarMocanCezar Mocan •CezarMocan
Timp execuţie pe test0.425 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

2SAT

Problema satisfiabilităţii, notată prescurtat cu SAT, cere determinarea existenţei unei atribuiri satisfiabile pentru o formulă booleană. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte „atribuire satisfiabilă” dacă evaluarea expresiei după atribuirea valorilor are ca rezultat valoarea de adevăr „adevărat”. Următoarea formulă: ((x_{1} \rightarrow x_{2}) \vee \sim((\sim x_{1} \leftrightarrow x_{3}) \vee x_{4})) \wedge \sim x_{2} , are o atribuire satisfiabilă dată de: \langle x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1 \rangle .

Utilizând următoarele echivalenţe logice: regula dublei negaţii, legile lui De Morgan şi legea distributivităţii, orice formulă booleană poate fi transformată în forma normal conjunctivă, o expresie scrisă ca o conjuncţie de propoziţii, iar fiecare propoziţie ca o disjuncţie de literali. Un exemplu de expresie în forma normal conjunctivă este: (x_{1} \vee x_{3}) \wedge (x_{2} \vee \bar{x_{1}}) \wedge (\bar{x_{4}} \vee x{3}) .

În consecinţă, va fi suficient să studiem doar forma normal conjunctivă. Problema SAT, pe cazul general, este NP-completă, chiar şi dacă restricţionăm expresiile la unele care în forma normal conjunctivă au doar trei literali în fiecare dintre propoziţii. Problema satisfiabilităţii pentru asemenea expresii se numeşte 3SAT.

În continuare ne vom ocupa de problema 2SAT ce are doi literali în fiecare din propoziţiile ce alcătuiesc forma normal conjunctivă, 2SAT fiind rezolvabilă în timp polinomial.

Cerinţă

Dându-se o expresie 2SAT să se determine o atribuire satisfiabilă a acesteia.

Date de intrare

Fişierul de intrare 2sat.in va conţine pe prima linie două numere naturale, N, numărul de termeni care apar în expresie, şi M, numărul de propoziţii disjunctive din care este formată expresia. Pe fiecare dintre urmatoarele M linii se vor afla câte două numere întregi, numerele de ordine ale termenilor prezenţi în fiecare dintre propoziţii. Semnul minus în faţa unui număr reprezintă negarea termenului în expresie.

Date de ieşire

În fişierul de ieşire 2sat.out se vor afişa N numere naturale, 0 sau 1, reprezentând o atribuire satisfiabilă pentru expresia dată în fişierul de intrare, sau valoarea -1 în caz că expresia nu admite soluţie.

Restricţii

  • 1 ≤ N ≤ 100 000.
  • 1 ≤ M ≤ 200 000.

Exemplu

2sat.in2sat.out
4 5
-1 -2
2 -3
2 3
-2 -4
3 4
0 1 1 0

Explicaţie

Datele de intrare corespund următoarei expresii: (\bar{x_{1}} \vee \bar{x_{2}}) \wedge (x_{2} \vee \bar{x_{3}}) \wedge (x_{2} \vee x_{3}) \wedge (\bar{x_{2}} \vee \bar{x_{4}}) \wedge (x_{3} \vee x_{4}) . O atribuire satisfiabilă este: \langle x_{1} = 0, x_{2} = 1, x_{3} = 1, x_{4} = 0 \rangle .

Indicaţii de rezolvare

Articolul Problema 2-satisfiabilităţii prezintă fiecare dintre soluţiile de mai jos în detaliu. Iată o schiţă...

O soluţie evidentă este încercarea celor 2N configuraţii posibile pentru termenii expresiei şi verificarea lor. Această abordare duce însă la o complexitate cu ordinul de excuţie O(2N * M). Cu această soluţie se obţin 20 de puncte.

O altă soluţie se conturează dacă fixăm o variabilă p dintr-o propoziţie. În cazul acesta suntem obligaţi să îi dăm o anumită valoare celeilalte variabile din acea propoziţie, q, ceea ce ne obligă să propagăm atribuiri de valori şi variabilelor care se găsesc în alte propoziţii care îl conţin pe q, şi aşa mai departe. Astfel, dacă problema admite soluţie vom ajunge la ea. Complexitatea finală este O(N * M). Acest algoritm obţine 70 de puncte.

O alta soluţie neliniară, în complexitatea O(N2 * M), se bazează pe un algoritm randomizat. Iniţial, se atribuie valori arbitrare variabilelor, după care, cât timp expresia nu este satisfăcută, se găseşte o propoziţie cu valoarea de adevăr 0 şi se schimbă valoarea unuia dintre cei doi termeni componenţi ai propoziţiei. Precizăm că această abordare se comportă foarte bine în practică, aşa că ar trebui să obţină circa 70 de puncte.

Soluţia optimă, în complexitatea O(M + N), se foloseşte de relaţia de implicaţie ce transformă expresia într-un graf, care se poate rezolva determinând componentele tare-conexe şi o sortare topologică.

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?