Clasele 11-12 lecția 30 - 20 mai 2015

Algoritmi de aproximare

Generalități

Folosim algoritmi de aproximare pentru a găsi soluții polinomiale apropiate de optim pentru probleme NP-complete. În general, ne referim la probleme de optimizare, care pot cere găsirea unei soluții maxime sau minime, în funcție de problemă.

Un algoritm de aproximare are raportul de aproximare $\rho (n)$ dacă, pentru orice date de intrare de mărime n, soluția găsită este de cel mult $\rho (n)$ ori mai proastă decât soluția optimă.

Subliniem că putem da garanții despre unii algoritmi, chiar dacă nu știm care este optimul (tocmai pentru că problema este NP-completă).

Clase de complexitate: P, NP, NP complet

Clasa P

P este clasa problemelor de decizie pe care o mașină Turing le poate rezolva în timp polinomial.

Merită lămurite două lucruri în această definiție. Ce este o problemă de decizie? Și ce este o mașină Turing?

Noțiunile de NP-completitudine se aplică problemelor de decizie. Acestea sunt probleme care, pentru un set de date de intrare, trebuie să răspundă doar cu „da” sau „nu”. Dar multe probleme de interes sunt probleme de optimizare, adică dintre toate soluțiile o cer pe aceea care optimizează o anumită valoare.

Exemple:

• Problemă de decizie: Dându-se două numere, sunt ele prime între ele? Problemă de optimizare: Dându-se două numere, care este cel mai mare divizor comun al lor?
• Problemă de decizie: Dându-se n puncte în plan, există două confundate? Problemă de optimizare: Dându-se n puncte în plan, care este distanța minimă între oricare două puncte?

În general, între o problemă de optimizare și una înrudită de decizie există o relație strânsă. Fie cele două sunt la fel de dificile, fie diferă printr-un factor polinomial.

• Definiția mașinii Turing. Exemple de funcționare (copiere, incrementare binară, decrementare binară, adunare binară)

Mașinile Turing nu sunt un model perfect pentru calculatoarele reale. Totuși, ele pot calcula tot ce poate calcula un calculator real.

• Tot aici vom menționa în treacăt de ce problema rucsacului nu este polinomială (ea este polinomială în valoarea numerelor de la intrare, nu în numărul de numere de la intrare). În aceeași situație se află găsirea unei submulțimi de sumă S.

Clasa NP

Pentru clasa NP (nedeterminist polinomial) avem două definiții:

1. Probleme pe care o mașină Turing nedeterministă (MTND) le poate rezolva în timp polinomial
2. Probleme pe care o mașină Turing deterministă (MTD) le poate verifica în timp polinomial

Să demonstrăm că cele două definiții sunt echivalente. Dacă o MTND rezolvă problema în timp polinomial, atunci putem „salva”, din numărul exponențial de căi nedeterministe, calea care duce la soluție. Acea cale servește drept certificat, iar o MTD poate verifica acel certificat în timp polinomial. Invers, dacă o MTD poate verifica un certificat în timp polinomial, atunci o MTND poate încerca toate certificatele posibile în timp (nedeterminist) polinomial.

Este evident că orice problemă din P este în NP (rezolvarea în timp polinomial poate servi drept certificat). Știm deci că P ⊆ NP, dar nu știm sigur dacă P ⊂ NP sau P = NP. Aceasta este cea mai mare întrebare încă fără răspuns în informatica teoretică. Pare foarte probabil că P ≠ NP, dar nu putem spune mai mult.

• Exemple

Clasa NP-complet

O problemă L este NP-completă dacă

1. L este în NP
2. L este „cel puțin la fel de grea” ca orice altă problemă din NP. Formal, spunem că orice altă problemă din NP se reduce la L.

• Dacă L întrunește doar condiția 2, ea este în clasa NP-hard
• Relația între P, NP, NP-complet și NP-hard

Discuție despre reduceri

Reducerea unei probleme la alta prezintă interes teoretic pentru a arăta că, dacă cineva găsește un algoritm polinomial pentru o problemă, el poate fi aplicat pentru a rezolva în timp polinomial și alte probleme. În particular, dacă găsim un algoritm polinomial pentru o singură problemă din NP, atunci am demonstrat că P = NP.

În general, demonstrația că o problemă este NP-completă se face reducând o altă problemă NP-completă la ea. Pentru unele probleme (notoriu, pentru SAT) există demonstrații explicite că sunt NP-complete.

• (Eventual) demonstrație că SAT este NP-completă
• (Eventual) demonstrație că 3-SAT este NP-completă, prin reducere
• (Eventual) demonstrație că 3-COLOR este NP-completă, prin reducere

Acoperirea minimă cu noduri (vertex cover)

Enunț: Se dă un graf neorientat. Se cere să găsim o submulțime S de noduri cu cardinal minim astfel încât pentru orice muchie (u, v) să avem $u\in S$ sau $v\in S$ (sau ambele).

Problema este NP-completă, căci 3-SAT se poate reduce la ea. Mai exact, putem transforma orice problemă de 3-SAT într-o problemă de acoperire minimă. (Exemplu)

• Algoritm de aproximare
• Demonstrație că produce o 2-aproximare
• Nu se cunosc aproximări mai bune de 2 pe cazul general
• Legătura cu cuplajul maximal (nu maxim!)
• Discuții despre alți algoritmi greedy

Problema rucsacului

Se dă un set de n obiecte, fiecare definit prin greutate și profit. Avem un rucsac de capacitate W. Se cere să găsim un set de obiecte cu greutate totală cel mult egală cu W, care maximizează profitul total.

• Algoritmul de programare dinamică: D(i, p) = greutatea minimă a unui subset din primele i obiecte care atinge profitul p.
• Discretizarea în funcție de OPT și ε
• Algoritmul în $O(n^{3}/\epsilon )$

Problema comis-voiajorului

• Problema este NP-hard (nu poate fi verificată în timp polinomial)
• Algoritm pentru 2-aproximare în cazul euclidian
• Algoritmul Christofides pentru 3/2-aproximare
• Nu se cunosc algoritmi de aproximare cu factor constant în cazul general