Algoritmi GREEDY

Pusi in fata unei probleme pentru care trebuie sa elaboram un algoritm, de multe ori "nu stim cum sa incepem". Ca si in orice alta activitate, exista cateva principii generale care ne pot ajuta in aceasta situatie. Ne propunem sa prezentam in urmatoarele capitole tehnicile fundamentale de elaborare a algoritmilor. Cateva din aceste metode sunt atat de generale, incat le folosim frecvent, chiar daca numai intuitiv, ca reguli elementare in gandire.

1 Tehnica greedy

Algoritmii greedy (greedy = lacom) sunt in general simpli si sunt folositi la probleme de optimizare, cum ar fi: sa se gaseasca cea mai buna ordine de executare a unor lucrari pe calculator, sa se gaseasca cel mai scurt drum intr-un graf etc. In cele mai multe situatii de acest fel avem:

• O multime de candidaţi (lucrari de executat, varfuri ale grafului etc)

• O functie care verifica daca o anumita multime de candidati constituie o soluţie posibila, nu neaparat optima, a problemei

• O functie care verifica daca o multime de candidati este fezabila, adica daca este posibil sa completam aceasta multime astfel incat sa obtinem o solutie posibila, nu neaparat optima, a problemei

• O funcţie de selecţie care indica la orice moment care este cel mai promitator dintre candidatii inca nefolositi

• O functie obiectiv care da valoarea unei solutii (timpul necesar executarii tuturor lucrarilor intr-o anumita ordine, lungimea drumului pe care l-am gasit etc); aceasta este functia pe care urmarim sa o optimizam (minimizam/maximizam)

Pentru a rezolva problema noastra de optimizare, cautam o solutie posibila care sa optimizeze valoarea functiei obiectiv. Un algoritm greedy construieste solutia pas cu pas. Initial, multimea candidatilor selectati este vida. La fiecare pas, incercam sa adaugam acestei multimi cel mai promitator candidat, conform functiei de selectie. Daca, dupa o astfel de adaugare, multimea de candidati selectati nu mai este fezabila, eliminam ultimul candidat adaugat; acesta nu va mai fi niciodata considerat. Daca, dupa adaugare, multimea de candidati selectati este fezabila, ultimul candidat adaugat va ramane de acum incolo in ea. De fiecare data cand largim multimea candidatilor selectati, verificam daca aceasta multime nu constituie o solutie posibila a problemei noastre. Daca algoritmul greedy functioneaza corect, prima solutie gasita va fi totodata o solutie optima a problemei. Solutia optima nu este in mod necesar unica: se poate ca functia obiectiv sa aiba aceeasi valoare optima pentru mai multe solutii posibile. Descrierea formala a unui algoritm greedy general este:

Un exemplu simplu de algoritm greedy este algoritmul folosit pentru rezolvarea urmatoarei probleme. Sa presupunem ca dorim sa dam restul unui client, folosind un numar cat mai mic de monezi. In acest caz, elementele problemei sunt:

• candidatii: multimea initiala de monezi de 1, 5, si 25 unitati, in care presupunem ca din fiecare tip de moneda avem o cantitate nelimitata

• solutie posibila: valoarea totala a unei astfel de multimi de monezi selectate trebuie sa fie exact valoarea pe care trebuie sa o dam ca rest

• multime fezabila: valoarea totala a unei astfel de multimi de monezi selectate nu este mai mare decat valoarea pe care trebuie sa o dam ca rest

• functia de selectie: se alege cea mai mare moneda din multimea de candidate ramasa

• functia obiectiv: numarul de monezi folosite in solutie; se doreste minimizarea acestui numar

Se poate demonstra ca algoritmul greedy va gasi in acest caz mereu solutia optima (restul cu un numar minim de monezi). Pe de alta parte, presupunand ca exista si monezi de 12 unitati sau ca unele din tipurile de monezi lipsesc din multimea initiala de candidati, se pot gasi contraexemple pentru care algoritmul nu gaseste solutia optima, sau nu gaseste nici o solutie cu toate ca exista solutie. Evident, solutia optima se poate gasi incercand toate combinarile posibile de

monezi. Acest mod de lucru necesita insa foarte mult timp.

Un algoritm greedy nu duce deci intotdeauna la solutia optima, sau la o solutie. Este doar un principiu general, urmand ca pentru fiecare caz in parte sa determinam daca obtinem sau nu solutia optima.

2 Minimizarea timpului mediu de aşteptare

O singura statie de servire (procesor, pompa de benzina etc) trebuie sa satisfacă cererile a n clienti. Timpul de servire necesar fiecarui client este cunoscut in prealabil: pentru clientul i este necesar un timp ti, 1 < i < n. Dorim sa minimizam timpul total de asteptare

ceea ce este acelasi lucru cu a minimiza timpul mediu de asteptare, care este T/n. De exemplu, daca avem trei clienti cu t1 = 5, t2 = 10, t3 = 3, sunt posibile sase ordini de servire. In primul caz, clientul 1 este servit primul, clientul 2 asteapta

pana este servit clientul 1 si apoi este servit, clientul 3 asteapta pana sunt serviţi clienţii 1, 2 si apoi este servit. Timpul total de asteptare a celor trei clienti este 38.

Algoritmul greedy este foarte simplu: la fiecare pas se selecteaza clientul cu timpul minim de servire din multimea de clienti ramasa. Vom demonstra ca acest algoritm este optim. Fie

o permutare oarecare a intregilor {1, 2, n}. Daca servirea are loc in ordinea I, avem

Presupunem acum ca I este astfel incat putem gasi doi intregi a < b cu

Interschimbam pe ia cu ib in /; cu alte cuvinte, clientul care a fost servit al b-lea va fi servit acum al a-lea si invers. Obtinem o noua ordine de servire J, care este de preferat deoarece

Prin metoda greedy obtinem deci intotdeauna planificarea optima a clientilor. Problema poate fi generalizata pentru un sistem cu mai multe statii de servire.