Utilizarea teoriei NP-completitudinii in abordarea algoritmilor euristici

Utilizarea teoriei NP-completitudinii in abordarea algoritmilor euristici

1. Algoritmi euristici si aproximativi

Definitii de baza

Un algoritm aproximativ genereaza, pentru o problema data P, o solutie corecta avand o valoare apropiata intr-un sens    ce trebuie precizat, de valoarea solutiei optimale. In unele cazuri valoarea determinata de algoritmul aproximativ este chiar valoarea optima

Un algoritm se numeste algoritm euristic daca in contextul sau se folosesc anumite strategii de identificare a solutiei care asigura obtinerea unor rezultate acceptabile conform unor criterii ce se presupun precizate.

Euristica desemneaza una sau mai multe strategii folosite in cadrul unui algoritm euristic.

Majoritatea algoritmilor aproximativi au la baza lor euristici, si din acest motiv literatura de specialitate nu face deosebire clara intre aceste doua notiuni.

Pe parcursul acestei lucrari vor fi folosite urmatoarele notatii

A - algoritm

I - intrarile algorimului

A(I) - iesirile algoritmilor in functie de intrarile furnizate

OPT - algoritm optimal

OPT(I) - rezultatele algoritmului optimal

Un algoritm A, pentru determinarea solutiei unei probleme P, se numeste algoritm de aproximare absoluta daca si numai daca exista o constanta k astfel incat | OPT(I) -A (I) | <=k, pentru orice I.

Algoritmul A se numeste algoritm f(n) aproximativ daca si numai daca : |OPT(I) -A(I)| / |OPT(I)| <= f(n) pentru orice I de marime n.

Algoritmul A se numeste schema aproximativa daca si numai daca, pentru orice >0, A genereaza o solutie pentru care:

|OPT(I) - A(I)| / |OPT(I)| <=

1. Algoritmi cu aproximare absoluta

Enunt: Fiind date doua benzi magnetice T₁ si T₂, de lungime b₁ si b₂ si n fisiere f₁, f₂ . f_n cu lungimile l₁, l₂ . l_n, sa se plaseze pe cele doua benzi un numar cat mai mare din fisierele date.

Un algoritm pentru rezolvarea acestui enunt poate fi urmatorul:

Pas se ordoneaza in ordine crescatoare a lungimilor fisierele, cu precizarea ca fisierele de aceeasi lungime se pot lua in orice ordine.

Pas 2: se umple prima banda cu fisiere luate in ordinea de la pasul 1.

Pas 3: se umple cea de-a doua banda cu fisierele ramase dupa pasul 2; STOP.

Fie I multimea fisierelor ce trebuiesc memorate si A(I) numarul de fisiere memorate dupa aplicarea algoritmului mai sus descris, atunci : |OPT(I) - A(I)| <= 1

Algoritmul poate fi generalizat la cazul a k benzi cu un algoritm de aproximare absoluta in care benzile sunt umplute pe rand de fisiere considerate in ordinea crescatoare a lungimii lor, aproximarea fiind in acest caz: |OPT(I) - A(I)| <= k-1.

Aplicatii ale acestui algoritm se pot intalni in acordarea creditelor la banci, umplerea containerelor.

1.3. Algoritmi f(n) - aproximativi

Enunt: Se presupun m orase legate intre ele fiecare cu fiecare prin drumuri de lungime data. Se cauta un circuit de lungime minima care sa treaca o data si numai o data prin fiecare dintre orase.

In cazul in care distantele pe care le parcurge comisvoiajorul satisfac regula triunghiului adica: d(a,c) <= d(a,b) + d(b,c), pentru orice a, b, c atunci se poate elabora un algoritm euristic numit cel mai apropiat vecin (nearest neighbor).

Pas 1. Se pleaca dintr-un oras oarecare considerat oras initial.

Pas    Atata timp cat mai sunt orase neparcurse, se alege drept urmatoarea localitate cea mai apropiata dintre localitatile neparcurse pana in acel moment.

Pas 3. Se revine in orasul din care s-a plecat si atunci algoritmul se opreste STOP.

Pentru problema comis voiajorului cu m orase si in conditiile satisfacerii regulii triunghiului are loc inegalitatea: (NN(I) - OPT(I) / OPT(I) <= ([log₂m] -1 )

Pentru orice valori ale lui m exista probleme pentru care: ( NN(I) - OPT (I) ) / OPT(I) > 1/3 (log₂(m+1) - 5/3). De aici rezulta ca algoritmul este de aproximare [log₂m].

Aplicatii ale acestui algoritm sunt de exemplu stabilirea traseelor postale sau de alta natura, aprovizionarea magazinelor, planificarea activitatilor.

1.4. Algoritmi e - aproximativi

Enunt: Fiind date multimile P = si W= , unde P este multimea profiturilor obiectelor 1, 2, ., r si W este multimea ponderilor acestor obiecte, se cere sa se determine o multime de obiecte, a caror pondere totala sa nu depaseasca M, capacitatea rucsacului, si sa dea un profit total maxim posibil.

Se presupune ca obiectele au fost ordonate in ordine necrescatoare a densitatii profitului, adica p_i / w_i p_i+1 / w_i+1, pentru I=1, ., r-1. Fie L(I, P, W, M) profitul obtinut pe calea umplerii, in ordine necrescatoare a rapoartelor p_i / w_i, a acelei parti din rucsacul de capacitate M care a ramas neocupata dupa ce obiectele din I au fost introduse in rucsac. P si W au semnificatiile de mai sus si se presupune ca r>0 si _i M. Acest algoritm va fi tratat mai pe larg pe parcursul acestei lucrari.

Aplicatii posibile ale acestui algoritm ar fi in incarcarea containerelor, stabilirea rutelor pe calea ferata

Utilizarea NP - completitudinii

Notam cu P clasa problemelor P pentru care exista un algoritm determinist care rezolva P in timp polinomial si cu NP clasa problemelor P pentru care exista un algoritm nedeterminist care rezolva P in timp polinomial. Evident, are loc P NP.

Exista foarte multe motive pentru a crede ca incluziunea PNP este stricta, PNP. Algoritmii nedeterministi constituie un instrument mult mai puternic decat cei deterministi si pana acum nu s-a putut gasi o metoda prin care algoritmii nedeterministi sa poata fi convertiti in algoritmi deterministi in timp polinomial. Cel mai puternic rezultat care s-a putut dovedi este urmatorul:

Teorema Daca o problema P apartine clasei NP, atunci exista polinoamele p(n) si q(n) astfel incat P poate fi rezolvata de un algoritm determinist in timpul O(p(n)2q(n)).

Demonstratie. Fara sa restrangem generalitatea, presupunem ca functia choice alege aleator din multimea si ca algoritmul nedeterminist "ghiceste" structura prin q(n) apeluri ale lui choice. Mai presupunem ca verificarea structurii se face in timpul O(p(n)). Algoritmul determinist va genera si verifica toate cele 2q(n) structuri. Rezulta imediat ca algoritmul nedeterminist are complexitatea O(p(n)2q(n)).

O problema P este NP-completa daca

este in NP, i.e. exista un algoritm nedeterminist care rezolva P in timp polinomial (echivalent, exista un algoritm determinist care rezolva P in timp exponetial);

este NP-dificila orice alta problema Q din NP se reduce polinomial la P.

P = NP daca exista un algoritm determinist care rezolva in timp polinomial

o problema NP-completa

Pana astazi nu a fost gasit un asemenea algoritm. De fapt, toti cercetatorii

din informatica teoretica considera ca egalitatea nu are loc, i.e. exista incluziunea stricta P NP, si de aceea este imposibila gasirea unui asemenea algoritm.

Din pacate, multe probleme practice s-au dovedit a fi NP-complete. Exista probleme NP-complete in calculul numeric, in geometrie, in algebra, in procesarea grafurilor, in procesarea sirurilor, etc. De aceea un bun proiectant de algoritmi trebuie sa inteleaga bine elementele de baza ale NP-completitudinii. Aceste elemente includ formalizarea abstracta a unei probleme, instrumente cu care se poate dovedi ca o anumita problema este NP-completa si ce trebuie facut dupa ce s-a dovedit ca o problema este NP-completa

Ce trebuie sa facem atunci cand avem de rezolvat o problema practica despre care am dovedit ca este NP completa.

Din pacate nu putem da raspunsuri care sa se constituie in retete "sigure". Pentru problemele de optimizare, algoritmii de aproximare (euristicile) constituie o solutie aplicata cu succes. Algoritmii de aproximare se bazeaza pe ideea "mai bine o solutie aproape optima obtinuta in timp polinomial (deci util) decat solutia exacta obtinuta intr-un timp foarte mare, deci inefectiv". Cei mai multi algoritmi de aproximare se bazeaza pe metoda greedy, dar si metode precum backtracking, divide et impera si metoda programarii dinamice.