Metoda "greedy"

Metoda "greedy" este o metoda ce permite determinarea unei singure solutii care corespunde unui anumit criteriu de optim, in cazul problemelor in care solutia se construieste ca o submultime a unei multimi date. Ordinul de complexitate al unui astfel de algoritm este redus considerabil prin faptul ca se incearca obtinerea solutiei printr-o singura parcurgere a multimii din care se construieste solutia optima, cu toate ca in practica, inainte de aplicarea metodei, se fac prelucrari asupra acestei multimi care maresc ordinul de complexitate.

Problema. Se da o multime A de cardinal n (n si o functie f: P(A) R. Sa se determine o submultime BI P(A) de cardinal k B = , (1 k n), astfel incat k-uplul (b₁,b₂,,b_k) sa optimizeze functia f

Solutie. Familia partilor multimii finite A, notata P(A) se numeste spatiul solutiilor problemei. Conditia de optim pe care trebuie sa o indeplineasca o solutie este exprimata printr-un set de relatii intre anumite elemente ale multimii A, relatii exprimate prin functia f. O solutie care poate conduce la obtinerea unei solutii optime se numeste solutie posibila. Pot exista mai multe solutii care satisfac conditiile de optim, dar se doreste obtinerea macar a uneia dintre acestea.

Construirea unei solutii optime consta din determinarea unei succesiuni de solutii posibile care imbunatatesc progresiv valoarea functiei f, conducand catre optim. Solutiile posibile au proprietatea ca orice submultime a unei solutii posibile este o solutie posibila. Prin urmare si multimea vida poate fi considerata ca o solutie posibila.

Descriere metoda:

Algoritmul prezentat mai sus conduce la obtinerea unei solutii (macar o solutie exista intotdeauna), pornind de la multimea vida si cautand in fiecare pas sa imbunatatim solutia deja obtinuta. Aceasta tehnica de obtinere a solutiei, care a dat si denumirea, oarecum ironica, a metodei (greedy = lacom), in cele mai frecvente cazuri conduce la indepartarea involuntara de optim, cunoscut fiind faptul (plastic exprimat prin "lacomia pierde optimalitatea"), ca optimul local nu atrage optimul global.

Acest aspect al tehnicii "greedy" a condus la disocierea algoritmilor elaborati prin metoda "greedy" in:

algoritmi cu atingerea optimului global;

algoritmi ale caror solutii converg catre optimul global (evident, fara atingerea acestuia in toate situatiile). Aceasta din urma categorie de algoritmi genereaza solutii 'multumitoare' in majoritatea cazurilor, dar si solutii 'catastrofale' in alte cazuri.

Disocierea in cele doua categorii se realizeaza prin modalitatea de alegere a elementelor din multimea A. De aceea, este frecvent folosita o prelucrare (reordonare) prealabila a elementelor multimii A care sa modifice ordinea alegerii elementelor submultimii B

procedura greedy

k := 0 - k este numarul de elemente din B

B :=

repeta

alege a I A

daca B este solutie posibila atunci

k::= k + 1

B := B

sfdaca

pana cand nu se mai pot alege elemente din A

sfarsit

Exemplul care urmeaza scoate in evidenta cele doua aspecte ale metodei: atingerea optimului sau numai apropierea de acesta.

Exemplu (functia "greedy"). Se da o submultime A a lui R, cu n elemente si o functie f de forma f(x₁,x₂,,x_k) = c₁x₁ + c₂x₂ + + c_kx_k (c_iIR, 0 k n). Sa se gaseasca o submultime B A de cardinal k pentru care functia f ia valoare maxima.

In programul Pascal:

fisierul de intrare 'multime.txt' va avea forma:

a₁, a₂, , a_n - multimea A

c₁, c₂, , c_n - coeficientii functiei f

iesirea va fi:

Solutia : x = ( b₁, b₂, , b_k)

Valoarea maxima a functiei este v

Solutie. Aceasta problema constituie un exemplu ilustrativ complet, pentru cazul in care prin aplicarea metodei 'greedy' se obtine valoarea optima a functiei f. Algoritmul necesita o pregatire prealabila a multimii A in vederea aplicarii procedurii de alegere succesiva a elementelor submultimii B

se va ordona crescator multimea A

pornind de la B := vom selecta elementele din A astfel:

cat timp printre coeficientii c_i ai functiei f exista numere negative (carora nu li s-a asociat un element din A, ca valoare pentru x_i - ul corespunzator), executam: celui mai mic coeficient neasociat unui element din A, ii atasam cel mai mic numar din A inca neselectat;

pentru ceilalti coeficienti (pozitivi) ai functiei f carora nu li s-a asociat un element din A (ca valoare pentru x_i), se alege, pentru cel mai mare coeficient neasociat unui element din A, cel mai mare numar din A inca neselectat.

Vom ilustra algoritmul cu un exemplu numeric.

Exemplu. Fie multimea de numere A = (deja ordonata) si functia f de forma f(x₁,x₂,x₃,x₄,x₅,x₆,x₇) = 3x₁ + 6x₂ - x₃ - 9x₄ - 9x₅ + 3x₆ + 8x₇. Solutia problemei va fi un vector x = (b₁,b₂,b₃,b₄,b₅,b₆,b₇) ale carui componente sunt elemente din A. Succesiunea alegerii valorilor componentelor vectorului x pune in evidenta "tehnica greedy":

- corespunzator celui mai mic element negativ dintre coeficientii functiei f alegem primul element din A, deci b₄ = -8

- corespunzator celui mai mic element negativ dintre coeficientii functiei f pentru care nu s-a ales inca o valoare pentru elementul vectorului x, alegem urmatorul element din A, deci b₅ = -7

- continuam alegerea elementelor lui x pana cand tuturor coeficientilor negativi ai functiei f li s-a asociat componenta corespunzatoare in vectorul x. Obtinem x = (b₁,b₂,-5,-8,-7,b₆,b₇);

- corespunzator celui mai mare element pozitiv dintre coeficientii functiei f alegem ultimul element din A, deci b₇ = 8

- corespunzator celui mai mare element pozitiv dintre coeficientii functiei f pentru care nu s-a ales inca o valoare pentru elementul vectorului x, alegem elementul anterior celui ales la pasul precedent, deci b₂ = 7

- continuam alegerea elementelor lui x pana cand tuturor coeficientilor functiei f li s-a asociat componenta corespunzatoare in vectorul x

Obtinem in final x = (5,7,-5,-8,-7,3,8). Valoarea maxima a functiei este

f(5,7,-5,-8,-7,3,8) = 270

Programul Pascal care implementeaza algoritmul este urmatorul:

program functie_greedy;

var a,c,x : array [1..15] of shortint;

i,j,k,n,r,l : byte;

h : shortint;

s : integer;

t : boolean;

f : text;

procedure min(var val : shortint; var poz : byte);

var minim : shortint;

i : byte;

begin

minim := 127;

poz := 0;

for i := 1 to k do

if (c[i] < minim) and (c[i] <> 0) then

begin

minim := c[i] ;

poz := i;

end;

val := minim;

end;

procedure max(var val : shortint; var poz:byte);

var maxim : shortint;

i:byte;

begin

maxim := -128;

poz := 0;

for i := 1 to k do

if (c[i] > maxim) and (c[i] <> 0) then

begin

maxim := c[i] ;

poz := i;

end;

val := maxim;

end;

begin

assign (f,'multime.txt');

reset(f);

i := 0;

while not eoln(f) do

begin

i := i + 1;

read(f,a i );

end;

n := i;

readln(f);

i := 0;

while not eoln(f) do

begin

i := i + 1;

read(f,c i );

end;

k := i;

close(f);

repeat

t := true;

for i := 1 to n-1 do

if ( a[i] >a[i + 1] then

begin

h := a[i] ;

a[i] := a[i + 1] ;

a[i + 1] := h;

t := false;

end;

until t;

write ('Multimea A : ');

for i := 1 to n do

write (a[i] ,',');

writeln (chr(8),' ');

i := 1;

r := 1;

s := 0;

min(h,l);

while (h<0) and (r< k) do

begin

x[l] := a[i] ;

s := s + c[l] *x[l] ;

c[l] := 0;

i := i + 1;

r := r + 1;

min(h,l);

end;

if ( r < k ) then

begin

i := n;

max(h,l);

while ( r < k ) do

begin

x[l] := a[i] ;

s := s + c[l] * x[l] ;

c[l] := 0;

i := i - 1;

r := r + 1;

max(h,l);

end;

end;

write ('Solutie : x (');

for i := 1 to k do

write (x[i] ,',');

writeln (chr(8),')');

write (' Valoarea maxima a functiei este ',s);

readln;

end.

Pentru fisierul de intrare "multime.txt":

iesirea va fi: x = (5,7,-5,-8,-7,3,8) si valoarea maxima a functiei este