Metoda greedy

Metoda greedy

Prezentarea metodei

In general, metoda greedy (in traducere "avida") se aplica problemelor in care, pentru o multime data M = , se cere determinarea unei submultimi a sa care sa indeplineasca anumite conditii.

O solutie a problemei se numeste solutie posibila. Cum, in general, exista mai multe solutii posibile se cere sa se determine una singura conform unui criteriu. Acest criteriu se numeste criteriu de optimizare si solutia determinata se numeste solutie optima.

Metoda greedy construieste solutia optima pas cu pas prin determinarea la fiecare pas a unei solutii partiale numita solutie acceptabila. O solutie acceptabila are urmatoarea proprietate: daca S este o solutie acceptabila si S atunci este o solutie acceptabila. Se presupune ca multimea vida este intotdeauna solutie acceptabila.

Daca metoda greedy rezolva problema, atunci ultima solutie acceptabila determinata este solutie posibila care este si optima.

Pentru a rezolva problema sunt necesare urmatoarele:

multimea initiala M;

o functie c₁ care exprima criteriul de selectie a unui element m_j inca neselectat din multimea M pentru a fi adaugat eventual la solutia acceptabila S;

o functie t₁ care testeaza daca elementul selectat m_j este acceptabil;

o functie t₂ care testeaza daca noua solutie acceptabila S := S este solutie posibila;

o functie c₂ care exprima criteriul de optimizare.

Observatii

Metoda greedy nu determina toate solutiile posibile si abia apoi sa o aleaga pe cea optima dintre acestea (ceea ce ar necesita timp de calcul si spatiu de memorie mari), ci incearca sa determine de la bun inceput o solutie posibila care sa fie si optima.

Functia c₁ este de obicei obtinuta din functia c₂, uneori aceste doua functii sunt chiar identice. De aceea, solutiile acceptabile sunt solutii optime locale. Dar, prin optimizari locale succesive, nu se obtine totdeauna in final solutia optima globala. Uneori metoda nu furnizeaza nici macar o solutie posibila.

In functie de modul de selectare al elementelor din multimea M se obtin doua variante ale metodei greedy pe care le prezentam in continuare sub forma unor proceduri.

PROCEDURA GREEDY1(M, n, S);

BEGIN

S :=

FOR i := 1 TO n DO

ESELECT(M, i, m_j);

EACCEPT(S, m_j, v1);

IF v1 = 1 THEN

SACCEPT(S, m_j);

SPOSIBIL(S, v2);

IF v2 = 1 THEN EXIT;

ENDIF;

ENDFOR;

END.

Procedura ESELECT selecteaza, conform criteriului c₁, elementul m_j I si efectueaza interschimbarea dintre m_i si m_j.

Procedura EACCEPT determina, conform testului t₁ valoarea lui v1:

daca m_j este element acceptabil,

in caz contrar.

Procedura SACCEPT determina noua solutie acceptabila S := S

Procedura SPOSIBIL determina, conform restului t₂, valoarea lui v2:

daca S este solutie posibila,

in caz contrar.

A doua varianta a metodei greedy este urmatoarea:

PROCEDURA GREEDY2(M, n, S);

BEGIN

PERM(M);

S :=

FOR i:=1 TO n DO

EACCEPT(S, m_i, v1);

IF v1=1 THEN

SACCEPT(S, m_i);

SPOSIBIL(S, v2);

IF v2=1 THEN EXIT;

ENDIF;

ENDIF;

ENDFOR;

END.

Procedura PERM efectueaza conform unui criteriu o permutare a elementelor multimii M.

Observatii

In procedura Greedy1 ordinea in care trebuie selectate elementele se stabileste in mod dinamic la fiecare pas prin procedura ESELECT, iar in procedura GREEDY2 aceasta ordine se stabileste de la inceput prin procedura PERM.

Procedurile GREEDY1 si GREEDY2 sunt prezentate pentru cazul general. Ele pot fi adaptate pentru fiecare problema rezolvabila cu aceasta metoda.

Teorema 4.1

Metoda greedy are complexitatea O(n²).

Demonstratie

Instructiunea FOR itereaza de cel mult n ori. Complexitatea unei iteratii a instructiunii FOR este O(n). Deci complexitatea metodei este O(n²).

Probleme rezolvate

Problema G1

Problema submultimii cu valoare maxima.

Se da o multime M = cu elemente numere reale. Sa se determine o submultime a sa, astfel incat sa fie maxima.

Rezolvare

Daca m_i ≤ 0 oricare ar fi m_i I M atunci S = }. Daca exista m_i > 0, m_i I M, atunci rezolvam problema cu metoda greedy. In acest caz elementele problemei sunt urmatoarele.

multimea M = a elementelor de numere reale date;

o solutie acceptabila este o submultime cu proprietatea ca , k = 1, ., p;

o solutie posibila este o solutie acceptabila S care contine toate elementele m_i din M cu m_i ≥ 0;

o solutie optima este o solutie posibila; vom determina solutia optima cu toate elementele m_i > 0;

criteriul de selectie este evident m_i > 0.

Procedura este urmatoarea:

PROCEDURA SUBMAX(M,n,S);

BEGIN

S :=

FOR i := 1 TO n DO

IF m_i > 0 THEN

S:=S ;

ENDIF;

ENDFOR;

END.

Codul sursa al programului C care implementeaza algoritmul de mai sus este:

#include<stdio.h>

#include<limits.h>

void main()

max=-INT_MAX;

k=0;

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

if(a[i]>0)

s[++k]=a[i];

else

if (a[i]>max)

max=a[i];

if(k==0)

s[++k]=max;

printf('Elementele care formeaza suma maxima: ');

for(i=1;i<=k;i++)

printf('%d ',s[i]);

printf('n');

Problema G2

Problema restului de plata.

Avand la dispozitie o multime de monede, cum poate fi achitat un rest de plata folosind un numar minim de monede.

Rezolvarea cu metoda greedy

Sa notam cu R restul care trebuie achitat si cu M = multimea bancnotelor pe care le avem la dispozitie. Evident ca M si presupunem ca fiecare bancnota m_i I M exista intr-un numar suficient de mare. Avem:

Elementele problemei sunt urmatoarele:

multimea M = a bancnotelor pe care le avem la dispozitie;

o solutie acceptabila este o submultime de bancnote astfel incat

o solutie posibila este o solutie acceptabila S_j astfel incat ; fie P = multimea solutiilor posibile;

o solutie optima este o solutie posibila S_p astfel incat s_p = min, unde s_i corespunde la S_i din P, i=1, , q;

criteriul de selectie al bancnotelor din multimea M este evident m_j = max, m_j n-a fost inca selectata. Adica, se selecteaza moneda care are valoarea cea mai mare.

In continuare sa consideram doua cazuri concrete.

In cazul 1 consideram R = 131, M= si notam prin R_i restul curent de plata.

Rezulta solutia optima S_p = , n_p = , s_p=5.

In cazul 2 consideram: R = 340, M =

In acest caz nu s-a ajuns la o solutie posibila, desi exista solutie posibila, anume 340 = 3x100 + 2x20. Aceasta solutie posibila ar fi fost gasita daca s-ar fi facut revenire si s-ar fi modificat una dintre selectiile anterioare. Dar metoda greedy nu accepta reveniri.

Rezolvarea problemei prin metoda greedy, respectiv prin procedura GREEDY2, este prezentata in procedura ACHIT

PROCEDURA ACHIT(M, n, S, N);

BEGIN

ORD(M);

S := ; N :=

FOR i := 1 TO n DO

EACCEPT(R, m_i, n_i, v1);

IF v1 = 1 THEN

SACCEPT(S, m_i, N, n_i);

SPOSIBIL(R, v2);

IF v2 = 1 THEN

EXIT;

ENDIF;

ENDIF;

ENDFOR;

END.

Procedura ORD ordoneaza descrescator multimea M si se obtine o permutare a acestei multimi.

Procedura EACCEPT calculeaza n_i := [R / m_i], R := R - n_i * m_i si valoarea lui v1 in modul urmator:

Procedura SACCEPT determina: S := S , N := N

Procedura SPOSIBIL determina valoarea lui v2 in modul urmator:

Remarcam faptul ca procedura ACHIT poate fi elaborata fara a face apel la alte proceduri.

Codul sursa al programului este:

#include<stdio.h>

void AfisSol(int s[20], int nr[20], int dim)

void ordonare(int m[20], int n)

void eaccept(int m, int& rest, int& nr, int& v1)

void saccept(int& k, int s[20], int nr[20], int m, int r)

void achit(int n, int m[20], int rest, int s[20], int nr[20], int& k)

}

void main()

printf('Suma de platit:');

scanf('%d',&rest);

achit(n, m, rest, s, nr, dim);

AfisSol(s, nr, dim);

Problema G3

Problema continua a rucsacului

Un hot sparge un magazin in care gaseste n obiecte divizibile (poate fi luata si numai o parte dintr-un obiect) care il tenteaza. Din pacate, greutatea lor totala depaseste capacitatea sacului pe care hotul il are la dispozitie. Prin urmare, el este nevoit sa aleaga doar cateva din cele n obiecte. Hotul alege obiectele in functie de greutatea si valoarea lor, in asa fel incat valoarea finala a furtului sa fie maxima. Datele de intrare se gasesc in fisierul sac.in: pe prima linie un numar real reprezentand capacitatea rucsacului, pe a doua linie numarul n de obiecte, iar pe urmatoarele n linii se gasesc cate doua numere reale reprezentand valoarea, respectiv greutatea fiecarui obiect. Sa se afiseze obiectele furate de hot.

Rezolvare

Elementele problemei sunt urmatoarele.

n obiecte identificate prin valorile V = , si greutatile G = lor; capacitatea sacului C;

o solutie acceptabila este o submultime formata din k obiecte cu proprietatea ca unde k n ;

o solutie posibila este o solutie acceptabila care indeplineste conditia unde k n;

o solutie optima este solutia posibila;

criteriul de selectie este: dupa ce au fost selectate k obiecte se alege un obiect p astfel incat .

Procedura este urmatoarea:

PROCEDURA SAC(V, G , n, C);

BEGIN

ARRAY V(n), G(n), E(n);

FOR i := 1 TO n DO

e_i := v_i / g_i;

ORDONARE(V, G, E);

i := 1;

WHILE C - g_i > 0 DO

WRITE(Obiectul: v_i, g_i);

C := C - g_i ;

i := i + 1;

ENDWHILE;

IF C > 0 THEN

WRITE(O parte din obiectul (v_i, g_i): C * v_i / g_i, C);

ENDIF;

END.

Codul sursa al programului C care implementeaza algoritmul de mai sus este:

#include<stdio.h>

typedef struct

obiect;

void main()

printf('capacitatea rucsacului: ');

scanf('%lf',&capac);

// Se ordoneaza obiectele in functie de raportul

// utilitate / greutate folosind metoda

// prin selectia minimului

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

//se porneste de la primul obiect

i=1;

//cat timp nu s-au term obiectele si

//rucsacul nu e plin

while (i<=n && capac>0)

//daca greut obiectului este mai mare decat

//capacitatea ramasa ob se alege intreg

if(o[i].greut<=capac)

else