Metoda greedy

METODA GREEDY

• Prezentare generala

Cu toate ca este practic imposibil sa fie data forma unei probleme rezolvabila cu tehnica Greedy, vom incerca totusi.

Sa consideram o multime A cu n elemente. Se cere o submultime a sa cu mn elemente astfel incat sa fie indeplinite anumite conditii.

Exemplu: se considera o multime de n numere reale. Se cere o submultime a sa, astfel incat suma elementelor sale sa fie maxima.

Pentru rezolvare vom alege un prim element al multimii de numere reale. Daca este posibil , acesta va fi adaugat solutiei, initial vide.Posibilitatea ca acesta sa fie adaugat este data de semnul numarului. Se allege un al doilea numar, cu care se procedeaza in mod asemanator. Algoritmul se incheie cand au fost alese si eventual adaugate toate elementele multimii.

Pentru a rezolva o problema cu Greedy, solutia se construieste dupa regula:

Pentru fiecare element care urmeaza sa fie adaugat solutiei finale , se efectueaza o alegere a sa din elementele multimii A, iar daca este posibil, acesta este adaugat. Algoritmul se termina fie cand a fost gasita solutia ceruta , fie cand s-a constatat inexistenta acasteia.

Intuitiv, alegem un element, al doilea pana cand obtinem ce dorim sau pana cand au fost testate toate elementele multimii. De aici provine si numele metodei (greedy=lacom).

Tehnica GREEDY poate fi privita ca o particularizare a tehnicii BACKTRACKING in care se renunta la mecanismul de intoarcere.

Sa analizam , in parallel, cele doua tehnici, pentru a putea stabilii asemanarile si diferentele existente intre ele:

T    Ambele tehnici ofera solutii sub forma de vector.

T    Tehnica Backtracking poate oferii toate solutiile problemei, in timp ce tehnica Greedy ofera o singura solutie.

T    Tehnica Greedy nu dispune de mecanismul intoarcerii, specific tehnicii backtracking.

Aceasta este diferenta esentiala dintre cele doua tehnici, diferenta care are consecinte uriase in ceea ce priveste aplicabilitatea lor.

Consecinta 1.

Este necesar ca cel care eleboreaza un algoritm greedy sa stie faptul ca, procedand in modul ales de el, ajunge la rezultatul dorit. Pentru fiecare problema in parte, dup ace se identifica un algoritm, este obligatoriu sa se demonstreze ca acesta conduce la solutia optima. Demonstratia faptului ca se ajunge la solutia optima este specifica fiecarei probleme in parte.

Consecinta 2.

Tehnica Greedy conduce la timp de calcul polynomial.

Motivul care conduce la acest tip de calcul, tine de mecanismul tehnicii. Sa presupunem ca multimea din care se face alegerea are n elemente si ca solutia are tot n elemente. Se fac n alegeri, la fiecare alegere se fac n teste, rezulta un algoritm cu timp 0.

De multe ori, este necesar ca elementele multimii A sa fie sortate, pentru ca apoi sa alegem din acestea, iar sortarea necesita un timp minim 0. Insa sortarea se efectueaza la inceput. Prin urmare, acest timp se aduna, deci nu influenteaza rezultatul.

T    Pentru problemele care nu se cunosc algoritmi care necesita timp polynomial, se cauta solutii, chiar daca nu sunt optime, dar apropiate de acestea, dar care au fost obtinute in timp util. multe din aceste solutii sunt obtinute cu Greedy.

Astfel de algoritmi se numesc algoritmi euristici.

PROBLEMA RUCSACULUI

O persoana are un rucsac cu care poate transporta o greutate maxima G. Persoana are la dispozitie n obiecte si cunoaste pentru fiecare obiect greutatea si castigul care se obtine in urma transportului sau la destinatie. Se cere sa se precizeze ce obiecte trebuie sa transporte persoana in asa fel incat castigul sa fie maxim.

O precizare in plus transforma aceasta problema in alte doua probleme distincte. Aceasta precizare se refera la faptul ca obiectele pot fi sau nu taiate pentru transportul la destinatie. In prima situatie, problema poarta numele de problema continua a rucsacului, iar in a doua avem problema discreta a rucsacului. Aceste doua probleme se rezolva diferit, motiv pentru care ele sunt prezentate separat. Varianta continua a problemei rucsacului este tratata in acest paragraf iar cea discreta va fi tratata cu ajutorul programarii dinamice.

Problema continua a rucsacului, in care persoana are posibilitatea sa taie obiectele. In acest fel, se poate obtine o incarcare mai eficienta a rucsacului.

Algoritmul este urmatorul:

• Se calculeaza, pentru fiecare obiect in parte, eficienta de transport rezultata prin impartirea castigului la greutate;
• Obiectele se sorteaza in ordine descrescatoare a eficientei de transport si se preiau in calcul in aceasta ordine;
• Castigul initial va fi 0, iar greutatea ramasa de incarcat va fi greutatea rucsacului;
• atat timp cat nu a fost completata greutatea maxima a rucsacului sin u au fost luate in considerare toate obiectele se procedeaza astfel:

dintre obiectele neincarcate se selecteaza acela cu cea mai ridicata

eficienta de transport si avem doua posibilitati:

* acesta incape in totalitate in rucsac, deci se scade din greutatea ramasa de incarcat greutatea obiectului, la castig se cumuleaza castigul datorat transportului acestui obiect; se tipareste 1, in sensul ca intregul obiect a fost incarcat;

* obiectul nu incape in totalitate in rucsac, caz in care se calculeaza ce parte din el poate fi transportata, se cumuleaza castigul obtinut cu transportul acestei parti din obiect, se tipareste procentul care s-a incarcat din obiect, iar greutatea ramasa de incarcat devine 0.

Vom considera un exemplu numeric.

Greutatea care poate fi transportata cu ajutorul rucsacului este 3.

Avem la dispozitie 3 obiecte. Greutatea si castigul pentru fiecare obiect sunt prezentate mai jos:

Eficienta de transport este 1 pentru primul obiect, 4 pentru al doilea si 2 pentru al treilea.

In concluzie, obiectul 2 se incarca in intregime in rucsac, obtinand un castig de 4 si ramane o capacitate de transport de doua unitati de greutate. Se incarca din obiectul 3 (care este al doilea in ordinea eficientei de transport) pentru care se obtine castigul 4. Castigul obtinut in total este 8. Se remarca strategia GREEDY prin alegerea obiectului care va fi transportat, alegere asupra careia nu se revine.

program rucsac;

type vector=array [1..9] of real;

var c, q, ef: vector;

n, I, man1: integer;

gv, man, castig; real

inv: Boolean;

ordine: array [1..9] of integer;

begin

write (greutatea ce poate fi transportata);

readln (gv);

write ( numarul de obiecte=);

readln (n);

for i:=1 to n do

write (c[,i,]=);

readln (c[i]);

write (g[,i,]=);

readln (g[i]);

ordine [i]:=i;

ef[i] := c[i]/g[i]

end;

repeat

inv:= false;

for i:=1 to n-1 do if ef[i]<ef[i+1]

then

begin

man:=ef[i];

ef[i]:=ef[i=1];

ef[i=1]:= man;

man:=c[i];

c[i]:=c[i=1];

c[i=1]:=man;

man:=g[i];

g[i]:=g[i=1];

g[i=1]:=man;

inv:=true;

man1:=ordine[i];

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

ordine[i+1]:=man1

end

until not inv;

castig:=0;

i:=1;

while (gv>0) and (i<=n) do

begin

if gv>g[i]

then

begin

writeln (obiectul ,ordine[i], ,1);

gv:=gv-g[i];

castig:=castig+c[i]

end

else

begin

writeln (obiectul, ordine[i],,gv/g[i]:1:2);

castig:=castig+c[i]*gv/g[i];

gv:=0

end;

i:=i+1

end;

writeln(castig total=, castig:3:2)

end.

PROBLEMA MAXIM (maximizarea valorilor unei expresii).

Se dau n numere intregi nenule b₁, b₂,,b_n si m numere intregi nenule a₁, a₂,,a_m. Sa se determine o submultime a multimii B= care sa maximizeze valoarea expresiei:

E=a₁x₁+a₂x₂++a_nx_n,

Stiind ca nm si ca x₁.

Rezolvare.

Vom sorta crescator cele doua multimi de numere intregi A siB.

Pentru inceput, vom considera m=n.

Demonstratie.

O posibilitate de cuplare poate fi scrisa sub forma de permutare. Fie permutarea:

=, unde i₁, i₂,i_m sunt tot numerele 1, 2,m, luate in alta ordine. Pentru permutarea considerate suma va fi:

E=a₁b₍₁₎+a₂b(2)+a_nb_(m).

Vom arata ca dintre toate permutarile, permutarea identical este cea care maximizeaza suma (Atentie! Numerele sunt sortate b₁<b₂<b_n caz in care permutarii identice Ii corespunde sirul b1,b2,b_n).

Fie o permutare oarecare, diferita de cea identica. Privind permutarea ca un sir de numere naturale. De exemplu, permutarea =, o privim ca pe un sir de 5 numere naturale: 3, 1, 2, 5, 4. Sortam crescator sirul retinand in acelasi timp rezultatele partiale:

Astfel obtinem:3, 1, 2, 5, 4

1, 3, 2, 5, 4

1, 2, 3, 5, 4

1, 2, 3, 4, 5

Evident, cu orice permutare a multimilor primelor m numere naturale, putem proceda asemanator. Se obtine astfel un sir de permutari, sir caracterizat de faptul ca ultimul sau element edte permutarea identical: _{, 1}.._k=e.

Fie E₁ si E_i+1 sumele associate celor doua permutari. Avem E< E.

Cele doua sume sumt identice, exceptie facand doi termeni (cei care au fost inversati cand s-a obtinut permutarea).

Dupa simplificari ramane:

A_kb₁+a_k+1b_i+k<a_kb_i+1+a_kb_i+1+a_k+1b₁, unde b₁<b_i+1, a_k<a_k=1.

Inegalitatea se transforma in:

A_k(b_i-b_i+1)-a_k+1(b_i-b_i+1)<0; si apoi im (a_k-a_k+1)(b_i-b_i+1)<0, inegalitate evidenta.

Reconsiderand sumele avem:

E<E<E<.E_e

Exemplu n=3, m=3.

a₁=7, a₂=-5, a₃=2;

b₁=-1, b₂=2, b₃=-3.

Sortam a si b si obtinem in urma sortarii:

a₁=-5, a₂=2, a₃=7;

b₁=-3, b₂=-1, b₃=2;

E_max=-5(-3)+2(-1)+72=27.

Proba. Scriem b in celelalte moduri cu putinta:

-1, 2, -3 E=-5(-1)+ 2(2)+7(-3)=-12,27;

2, -1, -3 E=-52+2(-1)+7(-3)=-33<27;

2, -3, -1 E=-52+2(-3)+7(-1)=-23<27;

-1, -3, 2 E=-5(-1)+2(-3)+72=23<27;

-3, 2, -1 E=-5(-3)+22+7(-1)=12<27.

Trecem la cazul general, n>m.

Sortam elementele celor doua multimi.

1)      Sa presupunem ca elementele multimii A sunt numere intregi positive (naturale). Consideram elementele ordonate ale multimii B ca un sir de numere intregi in secventa strict crescatoare. Din start, trebuie selectat un subsir de m elemente. Conform rezultatului obtinut anterior, subsirul trebuie sa fie strict crescator. Cum elementele multimii b sunt ordonate crescator, ramane conditia ca alegerea sa fie un subsir cu m componente. Evident, putem allege mai multe subsiruri care indeplinesc conditia ceruta. Din ipoteza, elementele multimii A, ordonate sunt positive. Dupa cum se stie, produsul unui numar natural, cu un numar intreg este cu atat mai mare, cu cat acesta din urma este mai mare. In aceste conditii, subsirul ales va fi alcatuit din ultimile m elemente ale sirului de n elemente ale multimii B, ordonate crescator.

2)      Sa presupunem ce elementele multimii A sunt negative. Produsul dintre un numar negative si altul, este cu atat mai mare, cu cat acesta din urma este mai mic. Prin urmare, subsirul ales este subsirul format din primele m elemente ale sirului b.

3)      In cazul general, cand multimea A are k elemente negative si p elemente positive (k+p=m) vom allege primele k elemente ale subsirului A si ultimele p elemente ale subsirului B.

Exemplu:

a₁=-3, a₂=-1, a₃=2;

b₁=1, b₂=2, b₃=3, b₄=4.

E_max=-31+(-1)2+24=3

Alte posibilitati:

E=-31+(-1)2+23=1<3;

E=-32+(-1)3+24=-1<3;

E=-31+(-1)3=24=2<3.

Conform algoritmului propus, prezentam programul de mai jos:

program IoanMaxim;

type vector=array[1..9] of integer;

var a,b: vector;

m, n, i, ind, Maxim: integer;

procedure sortare (var v: vector; n: integer);

var gata: boolean;

i, m: integer;

begin

repeat

gata:= true;

for i:=1 to n-1 do

if v[i] .v[i=1}

then

begin

m:=v[i];

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

v[i+1]:=m;

gata:=false

end

until gata;

end;

begin

write (m=); readln (m);

for i:=1 to m do

begin

write (a[,i,]=); readln (a[i]);

end;

write (n=); readln (n);

for i:=1 to n do

begin

write (b[,i,]=); readln (b[i]);

end;

sortare (a, m);

sortare(b, n);

ind:=0;

while a[ind+1]<0 do ind:=ind+1;

Maxim:=0;

for i:=1 to ind do

begin

writeln (a[i],*, b[n-m+i]);

Maxim:= Maxim+a[i]*b[n-m+i];

end;

for i:=ind+1 to m do

begin

writeln (a[i],*,b[n-m+i];

end;

writeln (Maxim=, Maxim);

end.

Eficienta algoritmului Greedy este evidenta. Prima idee ar fi fost sa selectam toate submultimile de m elemente ale multimii de n elemente si pe ecestea sa le permutam, retinand valoarea maxima. In acedt fel, aveam de probat A multimi. Pentru aceasta problema mecanismul de alegere a fost prezentat si orice element ales este si posibil de adaugat.

Probleme la care Greedy nu conduce la solutia optima

_{Am aratat faptul ca exista probleme pentru care nu se cunosc algoritmi care sa conduca in timp polinomial la solutia optima. In astfel de cazuri se renunta la opimalitate, se cauta solutii apropiate de cea optima dar care sa nu fie obtinute in timp util. De multe ori, pentru obtinerea lor se foloseste tehnica Greedy. Evident, in astfel de cazuri nu se mai pune problema unei demonstratii.}

Problema colorarii hartilor

N tari sunt date precizandu-se relatiile de vecinatate. Se cere sa se determine o posibilitate de colorare a hartii, astfel incat sa nu existe tari vecine colorate la fel.

Se stie faptul ce pentru colorarea unei harti sunt necesare cel mult 4 culori. Din pacate nu se cunosc algoritmi polinomiali care sa poata colora o harta prin utilizarea a numai 4 culori.Totusi, colorarea hartilor este o problema reala. Presupunand un numar mare de tari suntem obligati sa folosim o metoda euristica, in care sa obtinem o colorare admisibila, chiar daca nu utilizeaza un numar minim de culori.

Algoritmul propus este urmatorul:

-tara 1 va avea culoarea 1;

-presupunem colorate primele i-1 tari:

tara i va fi colorata cu cea mai mica culoare, cu un numar atasat mai mare sau egal cu 1, astfel incat niciuna din tarile vecine sa nu fie colorata la fel.

program colorare;

var a:array [1..50, 1..50] of integer;

c:array[1..50] of integer;

n, i, j,c1: integer;

gasit: boolean;

begin

write (numar tari:); readln (n);

for i:=1 to n do

for j:=1 to i-1 do

begin

write (a[,i,,,j,]=); readln (a[i,j]);

a[i, j]:= a[i, j]

end;

c[1]:=1;

for i:=2 to n do

begin

c1:=1;

repeat

gasit:=false;

for j:=1 to i-1 do

if (a[i,j]=1) and (c1=c[j])

then gasit:= true;

if not gasit then c[i]:=c1

else c1:=c1+1;

until not gasit;

end;

for i:=1 to n do

writeln (tara,i, culoarea ,c[i]);

end.

Problema comis voiajorului

Un comis-voiajor pleaca dintr-un oras, trebuie sa viziteze un numar de orase si sa se intoarca in orasul de plecare cu efort minim.

O modalitate de rezolvare a acestei probleme este de a genera toate ciclurile si de a-l retine pe cel de drum minim. O astfel de abordare conduce la un algoritm neperformant. Din acest motiv, aceasta solutie nu are valoare practica.

Pentru aceasta poblema nu se cunosc algoritmi care sa nu necesite un timp exponential. Iata motivul pentru care renuntam la conditia de optimalitate si ne marginim sa gasim un ciclu care sa treaca prin toate orasele cu un cost, pe cat posibil, redus.

Algoritmul este urmatorul:

se citeste matricea costurilor A si nodul de pornire v₁;

daca v₁,v₂,v_k este un lant seja ales, dupa caz, se procedeaza astfel:

-daca X=(v₂,v₂,,v_k), se alege muchia (v_k,v₁);

-daca X(v₂,v₂,,v_k), se alege muchia de cost minim care are o extremitate in v_k, iar cealalta in v_k+1.

Observatie:

Odata ci muchia se selecteaza si un nod. La fieare pas se selecteaza un nod. Din acest motiv algoritmul prezentat se incadreaza in tehnica GREEDY.

Pentru graficul din figura urmatoare se considera nodul de pornire 1.

Dintre toate michiile care au extremitatea in nodul 1 se alege muchia (1,2) pentru ca aceasta are costul minim(1).

Dintre toate cu extremitatea in nodul 2 se alege michia (2,3).

In continuare, se aleg muchiile (3,5), (5,4), (4,1) si astfel se obtine graful din figura urmatoare:

Acest graf nu are costul minim. De exemplu, graful din figura de mai jos are costul 15.

In program, vectorul S retine nodurile selectate (S(i)=1, daca nodul i a fost selectat si S(i)=0 in caz contrar).

program cv;

type matrice= array [1..9, 1..9] of integer;

vector= array [1..9] of integer;

var a;matrice;

s:vector;

n,i,j,v,v1,v2,min,cost:integer;

begin

write (n=);

readln(n);

for i:=1 to n-1 do

for j:=i+1 to n do begin

write (a[,i,,,j,]=);

readln (a[i,j];

a[i,j]:=a[i,j]

end;

for i:=1 to n do begin

s[i]:=0;

a[i,j]:=0

end;

write (Nodul de pornire este=);

readln(v);

s[v]:=1;

v2:=v;

cost:=0;

writeln (v0;

for i:=1 to n-1 do begin

min:=30000;

for j:=1 to n do

if (a[v2, j]<>0) and (s[j]=0) and (min>a[v2, j])

then

begin

min:=a[i,j];

v1:=j

end;

v2:=v1;

s[v2]:=1;

cost:= cost+min:

writeln (v0;

writeln (Cost total=,cost)

end.