Metoda Greedy - Aplicatii

Metoda Greedy

I.1.1         Descrierea metodei

Metoda Greedy ("Lacom") se aplica in probleme ce constau in determinarea unei submultimi a unei multimi date, submultime care trebuie sa indeplineasca anumite criterii. Vom numi o astfel de submultime solutie posibila. De regula, in problemele practice, exista mai multe solutii posibile (submultimi care indeplinesc criteriile), atunci se defineste si un criteriu de optim cu ajutorul caruia sa alegem una dintre acestea, pe care o vom numi solutie optima.

Esential este faptul ca metoda Greedy nu urmareste sa genereze toate solutiile posibile si sa aleaga dintre acestea pe cea care optimizeaza criteriul de optim (posibilitate care necesita spatiu mare de memorie si timp de calcul indelungat), ci presupune alegerea a cate unui element din multimea data urmand sa il includa ("inghita") eventual in solutia optima. Modalitatea de alegere a cate unui element depinde de natura problemei, iar metoda Greedy presupune demonstrarea faptului ca, in urma alegerilor facute, se va obtine o solutie finala optima. Spre deosebire de alte metode, odata ce un element a fost ales (a fost construit un optim local), asupra acestei decizii nu se mai poate reveni (Backtracking sau Branch and Bound).

Un exemplu elocvent este acela in care criteriul de optim este dat sub forma unei functii de cost care trebuie maximizata. Metoda Greedy va consta in alegerea de fiecare data a acelui element al multimii date care face sa creasca cat mai mult functia de cost. Evident, fara demonstratie, o asemenea abordare, nu va conduce obligatoriu la o solutie finala optima (optim local nu implica intotdeauna optim global), de aceea, in aceasta situatie, metoda Greedy trebuie privita numai ca o sugestie de rezolvare.

Timpul de calcul

Un avantaj major al metodei Greedy este dat de timpul de calcul. Astfel, determinarea unei submultimi a unei multimi cu n elemente presupune cel mult n teste pentru alegerea fiecarui element, cum sunt cel mult n alegeri, rezulta un timp polinomial O(n²). In majoritatea situatiilor, este necesar ca elementele multimii date sa fie ordonate, insa ordonarea se face la inceput, deci timpul necesar acesteia, de ordin O(nlog₂n) se aduna, deci nu influenteaza timpul final.

I.1.2         Exemplu - Programarea activitatilor

Exista mai multe forme ale problemei programarii activitatilor, problema ce isi gaseste aplicatii in domenii vaste ce presupun organizare de activitati, inclusiv in stiinta calculatoarelor, incluzand aici si sistemele de operare.

Sa consideram un garaj auto al unei firme de taxiuri ce are un singur angajat (mecanic). La un moment dat in curtea garajului se afla mai multe masini care urmeaza a fi verificate de mecanic. Acesta poate lucra la orice masina, in orice ordine, dar nu la mai multe in acelasi timp si poate trece la masina urmatoare numai dupa ce a terminat-o pe cea curenta. Odata ce mecanicul incepe lucrul, poarta curtii garajului se inchide (nu mai intra masini pentru verificare). Este bine inteles faptul ca daca o masina asteapta pentru verificare trei ore, iar verificarea sa dureaza o ora, in tot acest timp de 4 ore, ea nu aduce nici un profit firmei, astfel ca se pune problema programarii pentru verificare a cat mai multor masini, astfel ca pierderile (timpul total de asteptare) sa fie minime.

Pentru un sistem cu n masini exista n! posibilitati de rezolvare, insa generarea tuturor acestora si alegerea dintre ele a acelora optime intarzie decizia si poate duce la alte pierderi ale firmei. Prin urmare va trebui luata rapid o decizie!

De exemplu,

Tabel V . Activitati si duratele lor

Daca activitatile ar fi programate in ordinea [1,2,3,4], atunci:

Tabel V . Exemplu de programare a activitatilor

Iata alte trei ordonari ale activitatilor, alaturi de timpii corespunzatori de asteptare:

Tabel V . Exemple de programare a activitatilor

Oricare ar fi ordinea de programare a activitatilor, timpul total minim de asteptare este 10 (2+1+4+3), insa, asa cum se observa in tabelul de mai sus, o ordonare defectuoasa poate chiar tripla timpul total de asteptare.

O idee naturala este aceea de a considera activitatile in ordine crescatoare a duratelor lor -in exemplul nostru: [2,1,4,3]- si de a le trata in aceasta ordine. Daca este verificata mai intai masina cu cea mai mica durata de servire, atunci masina care urmeaza are cel mai scurt timp de asteptare inainte de a fi servita samd.

Daca generarea tuturor posibilitatilor de ordonare ducea la un algoritm exponential: O(n!), prin alegerea la fiecare pas a activitatii cel mai putin durabile, se obtine un algoritm de complexitate O(n*log2n), ordinul fiind dat de utilizarea unui algoritm performant de sortare.

Inainte de a trece la implementarea si exploatarea algoritmului elaborat, trebuie demonstrat ca alegerea celei mai scurte activitatii duce la obtinerea solutiei optime (caracterizata prin timp total de asteptare minim):

cu metoda Greedy se obtine o solutie de forma: [d1,d2,,dn], unde d_i este durata activitatii prelucrata a i-a, astfel ca d1<d2<.<dn. Vom demonstra prin reducere la absurd ca aceasta este solutia optima. Sa presupunem ca exista o solutie de programare a masinilor [d1,d2,,dn] optima, in care activitatile nu sunt in ordine crescatoare a duratelor lor. Atunci, exista un k<n, astfel incat d_k>d_k+1. Daca inversam aceste doua activitati k si k+1, obtinem o noua solutie in care toate activitatile prelucrate in urma activitatii k, vor intarzia cu d_k-d_k+1 mai putin pana sa fie servite, solutie care, evident, este mai buna decat cea considerata, contrazicand astfel ipoteza prin care activitatile nu sunt in ordine crescatoare a duratelor lor, qued.

I.1.3         Aplicatii

I.1.3.1   Problema continua a rucsacului - metoda Greedy

Problema rucsacului este o problema clasica de optimizare. Sa presupunem ca sunteti castigatorul unui concurs care, ca premiu, va permite sa intrati intr-un magazin si sa alegeti ce obiecte doriti, dar a caror greutate totala sa nu depaseasca greutatea dvs. Timpul nu este limitat. Dupa ce alegeti obiectele, magazinul va va recompensa cu bani in valoarea obiectelor pe care le-ati ales. Cum si ce obiecte alegeti?

Problema rucsacului are doua forme care necesita rezolvari diferite. Pe de o parte se poate considera ca obiectele pot fi sectionate, deci se pot lua in rucsac procente din ele [problema continua a rucsacului], pe de alta parte obiectele sunt intregi si nu pot fi sectionate, ele sunt luate sau nu in rucsac[problema 0/1 a rucsacului].

Metoda Greedy ofera solutie optima numai in cazul formei continue a problemei rucsacului.

Solutie:

Presupunem ca fiecarui obiect ii corespund doua valori: greutatea, respectiv castigul obtinut prin adaugarea sa in rucsac. Asadar dispunem de doi vectori G=(g_i) _i=1..n si C=(c_i) _i=1..n . De asemenea se cunoaste greutatea totala Greutate a rucsacului.

Ideea algoritmului Greedy este de a alege obiectele in ordine descrescatoare a eficientei lor (eficienta obiectului i fiind data de raportul castig/greutate: c_i /g_i.), pana cand rucsacul se umple. Asadar, vom sorta vectorii G si C dupa eficienta si vom alege, cata vreme mai este spatiu in rucsac, obiectele care incap integral. Cand in rucsac nu mai incape nici un obiect in intregime, este luat urmatorul obiect in proportia in care incape.

De exemplu, sa presupunem ca rucsacul are Greutate=5 si dispunem de 4 obiecte, astfel:

Tabel V . Obiectele ce pot fi luate in rucsac

Este evident ca alegerea va fi: obiectele 1 si 3 sunt luate integral, din obiectul 4 se ia numai jumatate (cat mai incape), iar obiectul 2, cel mai putin rentabil, este ignorat. Castigul total al alegerii facute va fi 24+9+ . Intr-adevar, conform algoritmului vom avea:

Tabel V . Alegerea obiectelor in rucsac

Observatii:

Daca X este vectorul solutie in care retinem cate parti luam din fiecare obiect, atunci avem:

castigul corespunzator solutiei va fi dat de relatia:

.

referitor la greutatea rucsacului, avem ca:

Problema continua a rucsacului - metoda Greedy

#include <iostream.h>

void BubbleSort(int*G, int*C, int*E, int n)

}

double Rucsac(int greutate,int*G, int*C, double*X, int n)

return castig;

main()

BubbleSort(G,C,E,n);

cout<<'Castig='<<Rucsac(greutate,G,C,X,n);

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

cout<<endl<<'Obiectul ('<<G[i]<<','<<C[i]<<

') a fost luat in proportie de: '<<X[i];

delete[]G;delete[]C;delete[]E;delete[]X;

return 0;

Demonstrarea faptului ca algoritmul de mai sus conduce la solutia optima este similara celei de la programarea activitatilor, de aceea o vom lasa in sarcina cititorului.

I.1.3.2   Problema 0/1 a rucsacului - metoda Backtracking combinata cu Greedy

Forma 0/1 a problemei rucsacului necesita o alta abordare. Solutia Greedy prezentata mai sus duce la urmatorul rezultat:

Tabel V . Alegerea obiectelor in rucsac cu algoritmul Greedy

Au fost alese obiectele 1 si 3 obtinandu-se castigul 24+9 . Aceasta nu este solutia optima in cazul 0/1 al problemei: alegerea obiectelor 2, 3, 4 ar fi umplut rucsacul si ar fi obtinut un castig mai bun, de 35. De fapt, solutia optima a problemei este: 2, 3 cu castigul maxim 38.

Pentru a obtine solutia optima putem utiliza metoda Backtracking: generam o prima varianta de alegere si o retinem ca solutie optima, apoi generam mai departe alta solutie si, daca aceasta obtine un castig mai bun decat cea presupusa optima, o inlocuim. Evident, dupa generarea tuturor solutiilor (caracteristica a metodei Backtracking), solutia retinuta va fi cea cu castigul cel mai bun.

Pentru a limita spatiul solutiilor, in care se face cautarea, conditiile functiei de continuare trebuie inasprite. In acest sens vom utiliza si metoda Greedy, astfel:

• calculam castigul corespunzator presolutiei de ordin k (adunand castigurile obiectelor luate pana acum in rucsac):
• 
• facem o estimare a castigului care poate fi obtinut continuand cu aceasta presolutie: utilizam algoritmul Greedy aplicat pentru forma continua pentru restul de obiecte: k+1, ., n si determinam castigul care mai poate fi obtinut:
• 
• adunam cele doua castiguri (cel al presolutiei si cel estimat ) si daca suma nu depaseste castigul solutiei optime curente, renuntam sa mai generam aceasta presolutie.

Pentru simplitate, presupunem ca obiectele sunt deja sortate descrescator in raport cu eficienta.

Problema 0/1 a rucsacului - metoda Backtracking combinata cu Greedy

#include<iostream.h>

int n,*XOpt,*X,*G,*C,greutate;

int COpt=0;

int castig (int k)

int cont(int k)

if(castig(k)+castig_estimat<=COpt)

return 0;

return 1;

void retsol()

void Back(int k)

main()

Back(0);

cout<<'Castig='<<COpt;

cout<<endl<<'S-au luat in rucsac obiectele :';

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

if(XOpt[i])

cout<<' ('<<G[i]<<','<<C[i]<<') ';

delete[]G;delete[]C;delete[]X;

return 0;