h2. Indicaţii de rezolvare

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

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

O soluţie evidentă este încercarea celor $2^N^$ configuraţii posibile pentru termenii expresiei şi verificarea lor. Această abordare duce însă la o complexitate cu ordinul de excuţie $O(2^N^ * M)$. Cu această soluţie se obţin '$20$ de puncte':/job_detail/382683?action=view-source.

O soluţie evidentă este încercarea celor $2^N^$ configuraţii posibile pentru termenii expresiei şi verificarea lor. Această abordare duce însă la o complexitate cu ordinul de excuţie $O(2^N^ * M)$. Cu această soluţie se obţin '$20$ de puncte':job_detail/382683?action=view-source.

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':/job_detail/382685?action=view-source.

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':job_detail/382685?action=view-source.

O alta soluţie neliniară, în complexitatea $O(N^2^ * 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':/job_detail/382684?action=view-source.

O alta soluţie neliniară, în complexitatea $O(N^2^ * 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':job_detail/382684?action=view-source.

Soluţia optimă foloseşte 'relaţia de implicaţie':http://en.wikipedia.org/wiki/Logical_implication pentru a transforma expresia într-un graf după cum urmează: orice disjuncţie de literali <tex> x_{i} \vee x_{j} </tex> este echivalentă cu următoarele implicaţii <tex> \bar{x_{i}} \to x_{j} </tex> şi <tex> \bar{x_{j}} \to x_{i} </tex>. Vom construi un graf cu noduri din mulţimea <tex> \{x_{1}, x_{2}, .., x_{n}, \bar{x_{1}}, \bar{x_{2}}, .., \bar{x_{n}}\} </tex> astfel: pentru orice propoziţie <tex> x_{i} \vee x_{j} </tex> va exista muchie de la <tex> \bar{x_{i}} </tex> la <tex> x_{j} </tex> şi de la <tex> \bar{x_{j}} </tex> la <tex> x_{i} </tex>, după cum arată relaţiile de implicaţie echivalente.

h2. Aplicaţii

* 'Party':/problema/party
* 'Aladdin':/problema/aladdin

* 'Party':problema/party
* 'Aladdin':problema/aladdin

* 'Excursion':http://www.oi.edu.pl/download/boi-2001.pdf - Baltic Olympiad in Informatics, 2001
* 'Peaceful Commission':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 2001
* 'Gates':http://b08.oi.edu.pl/downloads/booklet.pdf - Baltic Olympiad in Informatics, 2008