Metoda Greedy - Descrierea metodei

Metoda Greedy

1. Descrierea metodei:

Metoda Greedy este o metoda generala de proiectare a algoritmilor care consta in construirea solutiei globale optimale printr-un sir de solutii cu caracter de optim local atunci cind este posibila exprimarea "optimului global" ca o combinatie de o "optime locale".

Schema de proiectare: Problema se prezinta sub forma unei multimi S cu n componente. O parte din submultimile lui S reprezinta solutii care satisfac un anume criteriu si se numesc solutii admisibile. In spatiul solutiilor admisibile prezinta interes o solutie care maximizeaza/minimizeaza o functie obiectiv. Solutiile admisibile au proprietatea ca odata cu o solutie admisibila toate submultimile sale sint de asemenea admisibile. Metoda Greedy sugereaza un algoritm de constructie a solutiei optimale pas cu pas pornind de la multimea vida. La fiecare pas se selecteaza un element nou care va fi "inghitit" in solutie (greedy) in baza unei proceduri de selectie. De exemplu la problemele de optimizare procedura de selectie alege acel element care face sa creasca cel mai mult valoarea functiei obiectiv. Desigur nu in toate problemele, aceasta strategie conduce la solutia optima, metoda Greedy nefiind o metoda universala.

2. Modelul matematic:

Fie S o multime finita de intrari si C o colectie de submultimi ale lui S. Spuneme ca C este admisibila daca satisface axioma de admisibilitate:

X I C: X T xIX: X (x) I C)

Daca C este admisibila atunci perechea (S,C) se numste sistem admisibil. O submultime XIC se numeste baza daca este maximala ( nu exista xIS X astefel incit X I C. Clasa de probleme pentru care se pot defini algoritmi greedy este definita de urmatoarea schema:

Se considera date un sistem admisibil (S,C) si o functie obiectiv f:C R.

Se cere determinarea determinarea unei baze B I C. care satisface:

f(B) = optim

In general prin optim se va intelege minim sau maxim. Strategia "greedy" ("lacom") consta in gasirea unui criteriu de selectie a elementelor din S care candideaza la formarea bazei optime, numit criteriu de selectie greedy sau criteriu de selectie locala sau optim local.

Schema strategiei greedy este urmatoarea:

// Initial

S1 = S;

B =

repeat

// pasul de selectie greedy

alege x din S1 conform unui criteriu de optim local ;

S1 = S1 - ;

daca B este in C atunci B = B

// Conditia de terminare

until (nu se mai pot adauga elemente din S1 la B)

Obs. In studiile teoretice, optimul local are o definitie exacta:

f(B ) = optim ) | y I S1}

In practica construirii de algorimi greedy, este recomandabil sa fie lasata libera definitia optimului local. Exista totusi restrictia ca definitia acestuia sa nu depinda de alegerile ulterioare sau de solutiile subproblemelor. In schimb poate depinde de selectiile facute la acel moment. In acest fel se obtine o flexibilitate mai mare in proiectarea de algoritmi greedy dar de fiecare data trebuie demonstrat ca selectia conform optimului local conduce la o baza pentru care se obtine optimul global pentru functia obiectiv.

Din pacate numai conditia de admisibilitate nu asigura existenta unui crieriu de selectie locala care sa conduca la determinarea unei baze optime. Aceasta inseamna ca pentru anumite probleme algoritmii greedy nu construiesc o solutie optima ci numai o baza pentru care functia obiectiv poate avea valori apropiate de cea optima. Acesta este cazul unor probleme NP-complete.

Eficienta metodei (complexitatea):

Se presupune ca pasul de alegere greedy selectioneaza elemente x in O(k^p) timp unde k = S1 iar testarea conditiei B IC necesita O(l^q) timp, l = B, k + l n . De asemenea se presupune ca operatiile B si S - necesita O(1) timp. Rezulta:

T(n)= O(n^p +1^q) + . + O(1^p + n^q ) = O(1^p +.+ n^p + 1^q + . + n^q)= O(n^p+1 + n^q+1 ) = O(n^{max(p+1, q+1)})

3. Probleme

3.1. Interclasare optimala

Problema Avem secventele X₁,X₂,..X_n fiecare sortate.Sa se gaseasca o strategie de interclasare doua cate doua astfel incat numarul de operatii sa fie minim.

Exemplu: Fie urmatoarele secvente X₁, X₂, X₃ unde

X₁ are 30 elem.

X₂ are 20 elem.

X₃ are 10 elem.

Se aplica citeva variante de organizare a interclasarii

Y=merge(X₁,X₂) 50 operatii Y-50 elem.

Z=merge(Y,X₃) 60 operatii

----- ----- -----

110 operatii

2. Y=merge(X₂,X₃) 30 operatii Y-30 elem.

Z=merge(Y,X₁) 60 operatii

----- ----- -----

90 operatii

Solutia: Problema se rezolva aplicind o tehnica Greedy la fiecare pas cind se interclaseaza cele mai mici 2 secvente. Problema se poate reprezenta ca un arbore binar.

Exemplu

95 y₄

y₂ 35 60 y₃

y₁ 15 x₁ 20 30 x₅ 30 x₂

5 10

x₄ x₃

X₃,X₄ -> Y₁ -15 elem.

X₁,Y₁ -> Y₂ -35 elem.

X₂,X₅ -> Y₃ -60 elem

Y₃,Y₂ -> Y₄ -95 elem.

205 elem.

Nodul x₄ este la distanta 3 de nodul y₄, deci valoarea din x₄ se va aduna de 3 ori.

Daca notam d_i distanta de la radacina la nodul frunza x_i si cu q_i valoarea nodului, atunci

d_i = level ( q_i ) - 1

nr. total operatii

5*3 + 10*3 + 20*2 + 30*2 + 30*2 = 15 + 30 +40 + 60 + 60 = 205

S = se numeste lungimea drumurilor externe ponderate ale arborelui

O interclasare optimala corespunde construirii unui arbore binar optimal relativ la S.

Algoritm pentru construirea unui arbore binar optimal

tree ( L,n )

return (least(L))

}

Teorema 1 Fie algoritmul tree si L continand initial arbori cu un nod de valori ( q₁, q₂, q_n ). Atunci tree genereaza un arbore binar cu S = minima ( d_i distanta de la radacina la nodul q_i )

Demonstratie . Demonstratia se face prin inductie dupa n

1. n = 1 evident , arbore minimal

2. P(n-1) : Pentru orice secventa initiala de valori nod ( q₁, q₂, q_m ), 1 m n-1 tree genereaza un arbore T_a^m optimal

Presupunem P(n-1) adevarata.

P(n) : Pentru orice secventa initiala de valori nod ( q₁, q₂, q_n ), tree genereaza un arbore T_aⁿ optimal

Demonstram P(n) adevarata.

Lema 1 : Fie q_i si q_j cele mai mici doua valori ale secventei (nodurile care vor fi returnate in prima iteratie a buclei for de functia least ). Fie T un arbore optimal ( nu neaparat cel construit de tree). Fie P nodul interior cel mai indepartat de radacina si presupunem ca descendentii lui P au valorile q_k, q_l diferite de q_i, q_j.

(q_i q_k) si / sau (q_j q_l) se pot interschimba in arbore T, obtinandu-se un arbore T" care ramane optimal.

Demonstratie:

Fie d_i distanta de la nodul de valoare q_i la radacina

d_j distanta de la nodul de valoare q_j la radacina

d_k distanta de la nodul de valoare q_k la radacina

d_l distanta de la nodul de valoare q_l la radacina

q_i

q_j

q_k    q_l

S(T) =

Dupa interschimbarea valorilor q_i, q_k se obtine :

S(T') =

Avem D = S(T') - S(T) = q_i(d_k-d_i) - q_k(d_k-d_i) = (d_k-d_i) (q_i-q_k)

= -(d_k-d_i) (q_k-q_i)

Dar d_kd_i pentru ca P-ul e mai indepartat S(T')-S(T)0 S(T')S(T)

q_kq_i pentru ca q_i , q_j minime T minimal

S(T') = S(T) .

Analog se procedeaza pentru perechea (q_j,q_l). Se obtine T" pentru care S(T")=S(T).

Revenim la demonstratia P(n) adevarata:

Din Lema anterioara rezulta ca T" este optimal pentru secventa de valori nod ( q₁, q₂, q_n ) si contine nodul P care are in descendenti valorile q_i , q_j cele mai mici.

Inlocuim subarborele P cu un nod care are valoarea q_i+q_j .Noul arbore T''' fiind un subarbore al arborelui T" este optimal pentru secventa de valori nord (q₁ q_i-1 q_i+q_j q_i+1 q_j-1 q_j+1 q_n) deci S(T''') = q₁d₁+.+q_i-1d_I-1+ (q_i+q_j)d_i+j+ q_i+1d_i+1+.+ q_j-1d_j-1+ q_j+1d_j+1+.+ q_nd_n minima

S(T)'' - S(T''') = (q_id_i+ q_jd_j ) - (q_i+q_j)d_i+j= q_i(d_i-d_i+j) + q_j(d_j-d_i+j)=q_i+q_j.

Rezulta S(T) = S(T''') + q_i+q_j

Nodul P este construit de tree in prima iteratie, dupa care in iteratia urmatoare se intra in secventa de valori nod (q₁ q_i-1 q_i+q_j q_i+1 q_j-1 q_j+1 q_n)

Conform ipotezei inductive algoritmul construieste un arbore optimal T_a^n-1 pentru secventa de valori nord (q₁ q_i-1 q_i+q_j q_i+1 q_j-1 q_j+1 q_n) deci S(T_a^n-1) minima. Rezulta S(T_a^n-1) = S(T''')

Din modul de constructie a lui T_a^n-1 si T_aⁿ avem S(T_aⁿ)-S(T_a^n-1)=(q_id_i+ q_jd_j ) - (q_i+q_j)d_i+j= q_i(d_i-d_i+j) + q_j(d_j-d_i+j)=q_i+q_j .

Rezulta in final S(T_aⁿ) = S(T_a^n-1)+ q_i+q_r = S(T''') + q_i+q_j = S(T) deci T_aⁿ este optimal.

Complexitatea : Bucla for se executa de n ori .

Functiile least() si insert():

L - lista inlantuita: least() - O(n)

insert() - O(1) tree O(n²)

L - lista inlantuita ordonata: least() - O(1)

insert() - O(n)

L - heap:     least() - O(logn) tree O(nlogn)

insert() - O(logn)

Obs. Metoda functioneaza si pentru arbori k-ari ( fiecare nod cu k descendenti )

3.2. Compresiile de date. Arbori Huffman

Problema: Fie J = ( D₁, D₂, , D_n ) un grup de date, fiecare de lungime l si M un mesaj compus din aceste date .( Exemplu: D_i octeti de date si M un fisier ). Se cunoaste ca D_i apare in M de q_i ori i = 1, n. Sa se construiasca un sistem de coduri binare pentru elementele lui J a.i M sa fie de lungime minima.

Solutia: Se codifica fiecare data D_i , i = 1, n cu un numar variabil de biti pe baza unui arbore binar cu arcele etichetate astfel:

0 - pentru arcele de forma ( p, left(p))

1 - pentru arcele de forma ( p, right(p))

Arborele are n noduri terminale cate unul asociat fiecarei date D_i. Codul asociat datei D_i va fi secventa de biti de biti (0,1) care apar ca etichete pe drumul de la radacina la D_i.

Exemplu: D = ( D₁, D₂, , D_n ) = ( rosu, alb, verde, crem, bleu, galben, negru, maro)

r a v c b g n m

coduri(D) = ( 000, 001, , 111 )

0 1

0 1 0 1

0 1 0 1 0 1 0 1

r a v c b g n m

insa, de asemenea, poate fi si:

coduri(D) = ( 00, 01, 100, 101, 1100, 1101, 11110, 11111)

0 1

0 1 0 1

r a 0 1 0 1

v c 0 1 0 1

b g n m

Obs. Pentru a codifica n obiecte sunt necesare log₂n biti

Decodarea: 1. Codurile sunt de aceeasi lungime . Este suficienta o tabela de indirectare.

2. Codurile sunt de lungime variabila. Se foloseste arborele de codare . Aceasta se bazeaza pe faptul ca se obtine un sistem de coduri care sunt 'prefix distinctibile', adica i, j cod(D_i) nu este prefix al secventei cod(D_j).

Exemplu: M = 01 1111 00 00 01 01 01 101 1110 1100 00 100 1101 1101

a m r r a a a c n b r v g g

Lungime mesaj:

M = a m r r a a a c n b r v g g

in prima codare: l(M) = 14*3 = 42 biti

in a doua codare: l(M) = 40 biti

Obs. Problema determinarii unei codari care sa minimizeze lungimea lui M se reduce la determinarea unui arbore binar cu lungimea drumurilor externe ponderate minime

Fie M = D_i1 D_i2 D_ik compus din datele (D₁, D₂, D_n) cu frecventele de aparitii Q = (q₁, q₂, ,q_n) , q_i = nr. de aparitii in M a datelor D_i, atunci

l(M) = =

dist(D_i) - distanta de la radacina la D_i

Pentru exemplul anterior:

M = a m r r a a a c n b r v g g ,

D = ( b, m, v, n, c, g, r, a )

Q = ( 1, 1, 1, 1, 1, 2, 3, 4 )

Reyulta M de forma:

M = 00 0101 11 11 00 00 00 100 0111 0100 11 0110 101 101 -- 39 biti

a m r r a a a c n b r v g g

cu desenul din figura urmatoare:

0 1

2 6

0 1 0 1

4 4 3 3

a r

0 1 0 1

2 2 1 2

c g

0 1 0 1

1 1 1 1

b m v n

Obs. - Metoda este eficienta atunci cand frecventa aparitiilor este cunoscuta exact, si nu estimata;

- Ambele procese codor, decodor trebuie sa cunoasca arborele;

- Pastrarea codificarii lui M impreuna cu arborele de decodificare ridica probleme de ineficienta ocuparii spatiului;

- Pentru texte se foloseste un arbore cu q_i estimate statistic;

- Exemplu pentru un CD-ROM cu carti inmagazinate - se poate pastra un album 38 frunze ( alfabetul latin , plus semnele de punctuatie );

3.3. Drum minim intr-un graf ( sursa - destinatie )

Problema : Se da G = ( V, E ) un graf, e: E R⁺ functia de etichetare. Se cere un drum (s = V₁V₂V_k = d), unde dist(s,d) = minimal.

Obs. : Exista un algoritm care da toate aceste drumuri ( cu inmultire de matrici , de cost O(n³)).

Algoritmul Greedy pentru determinarea drumurilor minime de la nodul i la toate celelalte noduri :

short_path( G, C, s, n )

// C - matrice de cost C(i,j) =

// folosim vectorii dist(1..n) si pred(1..n)

// S - multimea nodurilor atinse

S =

for (i=1; i n; i++)

for (k=2; k n-1; k++)

xVS

S = S

for all yVS

}

return (dist, pred)

}

Teorema 2 Algoritmul obtine drumurile minime de la s la orice nod vV.

Demonstratie:

Demonstram ca nodul care se adauga in linia * are proprietatea ca drumul de lungime minima de la s la u trece numai prin noduri din S.

Presupumen ca exista un alt drum d de lungime mai mica decit dist(u) care contine cel putin un nod wVS : d = (s.w.u) ; lungime(d) < dist(u).

Presupunem ca segmentul d₁=(s.w) contine numai noduri din S cu (exceptia lui w). Nu restringem generalitatea deoarece in situatia in care exista mai multe noduri in d care sint din V/S putem alege w in d cu proprietatea de a fi primul nod din V/S in parcurgerea drumului de d de la s la u.

Din lungime(d₁) < lungime(d) < dist(u) rezulta ca u nu a fost ales cu dist(u) = min . Ar fi trebuit sa fie ales w.

Deoarece in final toate nodurile vor fi incluse in S rezulta ca drumurile obtinute sint de lungime minima.

Complexitatea: O(n²).

3.4. Problema rucsacului (Knapsack)

Problema Datele problemei sunt:

obiectele: i₁ i₂ i_n

greutatile: w₁ w₂ w_n

profiturile: p₁ p₂ p_n

capacitatea: M

Se cere o alegere X = ( x₁ , x₂ , , x_n ) , 0 x_i 1, astfel incat

(*) si

- maxim (**)

o solutie admisibila satisface (*).

o solutie optima este admisibila si satisface (**)

Obs. 1. Daca solutia optimala este x_i=1, i=1,.,n. Deci problema are sens pentru si astfel conditia de admisibilitate a unei solutii devine .

Un algoritm relativ performant se obtine pornind de la sortarea obiectelor in ordinea descrescatoare a valorilor p_i/w_i.

greedy_knapsack (P,W,M,n)

// P(1..n) - profiturile

// W(1..n) - greutatile

// M - capacitatea rucsacului

// X(1..n) vectorul solutie

// obiectele sint ordonate astfel incit P(i)/W(i) P(i+1)/W(i+1)

if (i n) X(i) = C/W(i);

return (X)

Teorema 3. Solutia generata de GREEDY_KNAPSACK este optimala.

Demonstratie: Fie X=(x₁,x₂,.,x_n) solutia generata de algoritm. Din modul de constructie rezulta

= M.

Daca X=(1,1,..,1) rezulta X optimala.

Daca X (1,1,..,1) fie j indicele pentru care x_i=1, 1 i<j ; 0 x_j<1; x_i=0 , j<i n . Rezulta = M

Presupunem ca X nu este optimala. Fie Y=(y₁,y₂,.,y_n) o solutie admisibila astfel incit >

Putem presupune ca.

(***) Fie k cel mai mic indice pentru care x_k y_k. Demonstram y_k<x_k .

Exista urmatoarele posibilitati:

1. k<j : Atunci x_k=1. Dar y_k x_k deci y_k<1. Rezulta y_k<x_k.

k=j

Daca y_j x_j atunci M==>M. Imposibil. Deci y_j<x_j adica y_k<x_k.

k>j

Imposibil.

Crestem acum y_k pina la x_k si descrestem y_k+1, y_k+2, .., y_n atit cit este necesar astfel incit

(capacitatea totala ramine M). Se obtine o solutie Z=(z₁,z₂,.,z_n) cu z_i=x_i , i=1,.,k si ( Suma ponderilor descresterilor y_k+1, y_k+2, .., y_n este egala cu ponderea cresterii lui y_k ).

Pentru Z avem :

In relatia anterioara au fost utilizate inegalitatile p_i/w_i p_i+1/w_i+1 , i=1.n-1.

Daca Z=X rezulta o inegalitate imposibila : >. Deci presupunerea initala X nu este optimala este falsa.

Daca Z X atunci repetam (***) cu Z in locul lui Y si continuam procesul pina cind obtinem Z = X adica ipoteza X nu este optimala falsa.

Complexitatea: O(n)