curs12 mate

Algoritmi si structuri de date Curs 12

Metode si tehnici de programare

Metoda Greedy

Metoda Greedy (greedy = lacom) se aplica, ın general, pentru rezolvarea problemelor ın care secere sa se determine o submultime B a unei multimi A cu n elemente, cu respectarea anumitorrestrictii specifice problemei. B se numeste solutie posibila. Se cere apoi sa se determine osolutie posibila care sa optimizeze (maximizeze sau minimizeze) o anumita functie obiectiv data.Aceasta solutie se numeste solutie optima.

Metoda Greedy furnizeaza o modalitate de rezolvare a problemelor de optim ın care se poateobtine optimul global prin alegeri succesive ale optimului local. Astfel problema este rezolvatafara a se reveni la deciziile luate deja. Din acest motiv, metoda Greedy se mai numeste tehnicaalegerii local optimale. Ideea de baza a tehnicii Greedy este urmatoarea: multimea B esteconstruita succesiv, ıncepand cu primul element, la fiecare pas fiind selectat un nou elementdin A (cel care pare a fi cel mai potrivit conform criteriului de optim) si adaugat ın B. Odatace s-a facut o alegere, aceasta nu mai poate fi schimbata – nu se mai poate reveni si ınlocuiun element al lui B cu o alta valoare din A. Tehnica Greedy nu conduce ıntotdeauna la osolutie optima – ceea ce pare optim la un anumit pas (local), poate fi dezastruos la nivel global.Uneori solutiile obtinute cu aceasta tehnica sunt sub-optimale, adica aproximeaza suficient debine solutia optima. Algoritmii de tip greedy sunt simpli, intuitivi si eficienti. In practica, existasituatii cand o solutie aproximativa a unei probleme poate fi multumitoare, ıntrucat algoritmulgreedy care furnizeaza solutia poate fi usor de implementat si este eficient. Cealalta varianta, agenerarii prin tehnica Backtracking a tuturor solutiilor si apoi a selectarii solutiei optime, poate fiextrem de ineficienta datorita complexitatii foarte mari. Intrucat tehnica Greedy nu garanteazadeterminarea solutiei optime, pentru fiecare algoritm ın parte trebuie demonstrata corectitudineaacestuia.

Desi atat metoda Greedy cat si metoda Backtracking ofera solutii sub forma de vector, cele douametode se deosebesc esential prin:

• tehnica Backtracking ofera toate solutiile problemei, ın timp ce metoda Greedy ofera osingura solutie;

• tehnica Greedy nu dispune de mecanismul ıntoarcerii, specific metodei Backtracking.

Aplicatia 1. Minimizarea timpului mediu de asteptare. O singura statie de servire (procesor,pompa de benzina, frizer etc.) trebuie sa satisfaca cererile a n clienti. Cunoscand timpul deservire necesar fiecarui client (pentru clientul i este necesar un timp ti, i = 1, n), sa se determineo ordine a servirii clientilor astfel ıncat timpul total de asteptare sa fie minim.

Timpul total de asteptare este suma timpilor de asteptare pentru fiecare client ın parte. Dacanotam cu wi, timpul de asteptare pentru clientul i, i = 1, n si timpul total de asteptare cu T ,

atunci T =n∑

i=1

wi.

A minimiza timpul total de asteptare este acelasi lucru cu a minimiza timpul mediu de asteptare,care este T/n.

1


Clientii sunt indentificati prin numere de la 1 la n.

Problema poate fi rezolvata folosind tehnica backtracking, generand astfel toate solutiile posibilesi alegand apoi pe cea optima, adica pe cea care minimizeaza timpul total de asteptare. De fapt,prin aceasta metoda se vor generara toate permutarile multimii {1, 2, 3, ..., n} si pentru fiecaresolutie ın parte se va calcula timpul total de asteptare. Se va alege solutia pentru care T esteminim. De exemplu, presupunem ca sunt 3 clienti avand timpii de servire t1 = 3, t2 = 7 si t3 = 2.Sunt posibile 3! = 6 modalitati de servire. Acestea sunt:

(1, 2, 3), T = 3 + (3 + 7) + (3 + 7 + 2) = 25(1, 3, 2), T = 3 + (3 + 2) + (3 + 2 + 7) = 20(2, 1, 3), T = 7 + (7 + 3) + (7 + 3 + 2) = 29(2, 3, 1), T = 7 + (7 + 2) + (7 + 3 + 5) = 28(3, 1, 2), T = 2 + (2 + 3) + (2 + 3 + 7) = 19(3, 2, 1), T = 2 + (2 + 7) + (2 + 7 + 3) = 23

In prima solutie generata cu algoritmul backtracking, clientul 1 este servit primul, deci w1 = 3,timpul de asteptare incluzand si timpul de servire. Clientul 2 asteapta pana este servit clientul1 si apoi este servit si el, deci w2 = 3 + 7 = 10. Clientul 3 asteapta pana sunt serviti clientii 1si 2 si apoi este servit si el, deci w3 = 3 + 7 + 2 = 12. Asadar, timpul total de asteptare a celortrei clienti este T = 3 + 10 + 12 = 25. Observam ca timpul cel mai mic de asteptare este 19 sieste oferit de solutia (3, 1, 2). Asadar aceasta este solutia optima: mai ıntai va fi servit clientul3, apoi clientul 1 si la final, clientul 2.

Tehnica Greedy este mai eficienta din punctul de vedere al timpului de executie si al simplitatii.Algoritmul bazat pe aceasta tehnica este foarte simplu: la fiecare pas se selecteaza clientul cutimpul minim de servire din multimea de clienti ramasa. Complexitatea acestui algoritm estelogaritmica. In scopul obtinerii solutiei optime, vom sorta crescator sirul timpilor de servire. Sepoate demonstra ca acest algoritm conduce ıntotdeauna la solutia optima.

Datele de intrare vor fi citite dintr-un fisier text timpi.txt. Pe prima linie a fisierului se aflanumarul n al clientilor. Linia a doua a fisierului contine n numere naturale, separate prin spatii,reprezentand timpii de servire a clientilor, ti, i = 1, n .Datele de iesire (ordinea optima de servire a clientilor si timpul total de asteptare) vor fi scrisela sfarsitul aceluiasi fisier.

#include<iostream>#include<f stream>#define dim 100using namespace std ;

struct Cl i en t{

// t = t impu l de s e r v i r e//nr = numarul de ord ineint t , nr ;

} ;

2


void s o r t I n s e r a r e D i r e c t a ( C l i en t vec to r [ ] , int n){

int i , j ;C l i en t aux ;for ( i = 1 ; i < n ; i++){

aux = vecto r [ i ] ;j = i − 1 ;while ( ( j >= 0) && ( aux . t < vec to r [ j ] . t ) ){

vec to r [ j +1] = vecto r [ j ] ;j = j − 1 ;

}vec to r [ j +1] = aux ;

}}

void timp ( C l i en t c [ ] , int n , o fstream &fout ){

// c l i e n t i i sunt in ord ine cresca toare , dupa t imp i i de s e r v i r eint i , j ;int T = 0 ;for ( i = 0 ; i < n ; i++){

fout<<c [ i ] . nr<<” ” ;for ( j = 0 ; j <= i ; j++)

T += c [ j ] . t ;}fout<<endl<<”Timpul t o t a l de a s t ep ta r e e s t e ”<<T<<endl ;

}

int main ( ){

int n ;C l i en t c [ dim ] ;i f s t r e a m f i n ( ” t impi . txt ” ) ;i f ( ! f i n ){

cout<<” Eroare l a de s ch ide r ea f i s i e r u l u i . ”<<endl ;e x i t ( 1 ) ;

}f i n>>n ;for ( int i = 0 ; i < n ; i++ ){

f i n>>c [ i ] . t ;c [ i ] . nr = i + 1 ;

3


}f i n . c l o s e ( ) ;s o r t I n s e r a r e D i r e c t a ( c , n ) ;o f s t ream fout ( ” t impi . txt ” , i o s : : app ) ;timp ( c , n , f out ) ;f out . c l o s e ( ) ;return 0 ;

}

Aplicatia 2. Problema spectacolelor. In singura sala de spectacole a unui teatru trebuie sa fieprogramate cat mai multe spectacole dintre cele n posibile. Pentru fiecare spectacol i, i = 1, n,se cunoaste intervalul ın care se poate desfasura [si, fi) (si reprezinta ora si minutul de ınceput,iar fi ora si minutul de final al spectacolului i). Sa se determine un program care sa permitaspectatorilor participarea la un numar cat mai mare de spectacole.

Spectacolele le vom identifica prin numere de la 1 la n. Vom sorta spectacolele crescator dupamomentul de ıncheiere a acestora. Algoritmul greedy va fi urmatorul: mai ıntai selectam spectacolcare se termina cel mai devreme. La fiecare pas selectam primul spectacol disponibil, care nu sesuprapune cu cele deja selectate, deci care ıncepe dupa ce se termina ultimul spectacol selectat.

Datele de intrare se vor citi dintr-un fisier text spectacole.txt ın care, pe prima linie, se afla nu-marul de spectacole n. Pe urmatoarele n linii se vor afla cate 4 valori, primele doua reprezentandora si minutul ınceperii spectacolului curent, iar ultimele doua reprezentand ora si minutul ter-minarii spectacolului.Datele de iesire, numerele de ordine ale spectacolelor care ındeplinesc restrictiile problemei, vorfi afisate la sfarsitul aceluiasi fisier, separate prin spatii.


struct Spectaco l{

// s = momentul i n c e p e r i i s p e c t a c o l u l u i// f = momentul i n c h e i e r i i s p e c a t c o l u l u i//nr = numarul curentint s , f , nr ;

} ;

void s o r t I n s e r a r e D i r e c t a ( Spec taco l vec to r [ ] , int n){

int i , j ;Spec taco l aux ;for ( i = 1 ; i < n ; i++){

aux = vecto r [ i ] ;j = i − 1 ;

4


while ( ( j >= 0) && ( aux . f < vec to r [ j ] . f ) ){



}}

void program ( Spectaco l v [ ] , int n , o fstream &fout ){

fout<<endl<<v [ 0 ] . nr<<” ” ;//u = indexu l u l t imu l u i s p e c t a c o l adaugat in programint i , u = 0 ;for ( i = 1 ; i < n ; i++)

i f ( v [ i ] . s >= v [ u ] . f ){

fout<<v [ i ] . nr<<” ” ;u = i ;

}fout<<endl ;

}

int main ( ){

int n ;int h , m;Spec taco l v [ dim ] ;i f s t r e a m f i n ( ” s p e c t a c o l e . txt ” ) ;i f ( ! f i n ){


}f i n>>n ;for ( int i = 0 ; i < n ; i++ ){

v [ i ] . nr = i + 1 ;f i n>>h>>m;// transformam or e l e in minutev [ i ] . s = h ∗ 60 + m;f in>>h>>m;v [ i ] . f = h ∗ 60 + m;

}f i n . c l o s e ( ) ;s o r t I n s e r a r e D i r e c t a (v , n ) ;

5


ofstream fout ( ” s p e c t a c o l e . txt ” , i o s : : app ) ;program (v , n , f out ) ;f out . c l o s e ( ) ;return 0 ;

}

Aplicatia 3. Problema rucsacului. O persoana are un rucsac ın care se poate ıncarca o greutatemaxima G. Persoana are la dispozitie n obiecte. Pentru fiecare obiect se cunoaste greutatea sa sicastigul care s-ar obtine daca obiectul ar fi transportat ın ıntregime. Sa se determine ce obiectear trebui sa aleaga persoana pentru a le transporta astfel ıncat castigul total sa fie maxim, faraa se depasi greutatea maxima a rucsacului.

Facem urmatoarele notatii pentru fiecare obiect i, i = 1, n:

• gi – greutatea obiectului;

• ci – castigul ce s-ar obtine daca obiectul ar fi transportat ın ıntregime;

• si =cigi

– castigul unitar.

Vom considera urmatoarele doua cazuri:

1. toate obiectele pot fi fractionate (se poate lua orice parte din obiectul i);

2. obiectele nu pot fi fractionate (orice obiect i poate fi transportat sau ın ıntregime sau deloc).

Vom nota cu xi cantitatea din obiectul i ce este ıncarcata ın rucsac pentru a fi transportata.Notam cu x = (x1, x2, ..., xn) vectorul solutiei. Solutia optima va trebui sa satisfaca urmatoareleconditii, ın functie de cazul considerat:

1.n∑

i=1

gixi = G, unde xi ∈ [0, 1], i = 1, n (se permite fractionarea obiectelor);

2.n∑

i=1

gixi ≤ G, unde xi ∈ {0, 1}, i = 1, n (nu se permite fractionarea obiectelor).

Pentru ambele cazuri, solutia optima trebuie sa maximizeze castigul total, Ct =n∑

i=1

cixi.

Vom sorta obiectele ın ordinea descrescatoare a castigurilor unitare.

Pentru primul caz, ın care se permite fractionarea obiectelor, se vor ıncarca obiectele pe catposibil ın ıntregime, ıncepand cu obiectul de castig unitar maxim, continuand apoi cu urmatorul,respectand ordinea considerata, pana se ajunge la greutatea maxima a rucsacului. In acest cazse poate demonstra ca algoritmul Greedy conduce la solutia optima a problemei.

Pentru al doilea caz, se adauga ın rucsac obiectele dupa aceasi regula, doar ca nu se permitefractionarea acestora. Incarcarea ın rucsac a obiectelor are loc fie pana cand greutatea totala

6


a obiectelor alese este egala cu capacitatea maxima a rucsacului (solutia este optima), fie maiexista loc ın rucsac, dar nu mai pot fi ıncarcate alte obiecte, deoarece greutatea individuala a aces-tora depaseste capacitatea ramasa disponibila a rucsacului (solutia obtinuta nu este ıntotdeaunaoptima).

Obiectele sunt indentificate prin numere de la 1 la n.

Datele de intrare vor fi citite dintr-un fisier rucsac.txt. Pe prima linie a fisierului se afla numaruln al obiectelor disponibile si numarul real G, reprezentand capacitatea maxima a rucsacului.Linia a doua a fisierului contine n numere reale, separate prin spatii, reprezentand greutatile giale obiectelor. Linia a treia are, separate prin spatii, n numere reale, corespunzatoare castigurilorci oferite de transportul obiectelor.Datele de iesire vor fi scrise, pentru ambele cazuri studiate, la sfarsitul aceluiasi fisier, astfel: maiıntai sunt listate obiectele ce vor fi ıncarcate ın rucsac, identificate prin numarul lor de ordine sieste afisat, de asemenea, castigul total obtinut ca urmare a transportului acestora.


struct Obiect{

int nr ; //numarul curent a l o b i e c t u l u idouble g , c , s ;

} ;

void s o r t I n s e r a r e D i r e c t a ( Obiect vec to r [ ] , int n){

int i , j ;Obiect aux ;for ( i = 1 ; i < n ; i++){

aux = vecto r [ i ] ;j = i − 1 ;while ( ( j >= 0) && ( aux . s > vec to r [ j ] . s ) ){



}}

void rucsac1 (double G, Obiect v [ ] , int n , o fstream &fout ){

double C = 0 , part ;int i = 0 ;

7


fout<<”Cazul 1 . Este permisa f r a c t i o n a r e a o b i e c t e l o r . ”<<endl ;while (G > 0 && i < n){

i f (G >= v [ i ] . g ){

// incarcam i n t e g r a l o b i e c t u l v [ i ]G −= v [ i ] . g ;C += v [ i ] . c ;fout<<” Obiectu l ”<<v [ i ] . nr<<” complet ”<<endl ;

}else{

// incarcam p a r t i a l o b i e c t u l v [ i ]part = G / v [ i ] . g ;C += v [ i ] . c ∗ part ;fout<<” Obiectu l ”<<v [ i ] . nr<<” p a r t i a l ”

<<100∗part<<” %”<<endl ;G = 0 ;

}i++ ;

}fout<<” Cas t i gu l t o t a l : ”<<C<<endl ;

}

void rucsac2 (double G, Obiect v [ ] , int n , o fstream &fout ){

double C = 0 , G1 = 0 ;fout<<”Cazul 2 . Nu e s t e permisa f r a c t i o n a r e a o b i e c t e l o r . ”<<endl ;for ( int i = 0 ; i < n ; i++){

i f (G1 + v [ i ] . g <= G){

// incarcam i n t e g r a l o b i e c t u l v [ i ]G1 += v [ i ] . g ;C += v [ i ] . c ;fout<<” Obiectu l ”<<v [ i ] . nr<<endl ;

}}fout<<” Cas t i gu l t o t a l : ”<<C<<endl ;

}

int main ( ){

double G;int n ;Obiect vec [ dim ] ;

8


i f s t r e a m f i n ( ” rucsac . txt ” ) ;i f ( ! f i n ){


}f i n>>n ;f i n>>G ;for ( int i = 0 ; i < n ; i++ )

f in>>vec [ i ] . g ;for ( int i = 0 ; i < n ; i++ ){

f i n>>vec [ i ] . c ;vec [ i ] . s = vec [ i ] . c / vec [ i ] . g ;vec [ i ] . nr = i + 1 ;

}f i n . c l o s e ( ) ;s o r t I n s e r a r e D i r e c t a ( vec , n ) ;o f s t ream fout ( ” rucsac . txt ” , i o s : : app ) ;rucsac1 (G, vec , n , f out ) ;fout<<endl ;rucsac2 (G, vec , n , f out ) ;f out . c l o s e ( ) ;return 0 ;

}

Exemplul 1.rucsac.txt

5 10

1 4 3 5 2

2 9 10 15 1

Cazul 1. Este permisa fractionarea obiectelor.

Obiectul 3 complet

Obiectul 4 complet

Obiectul 2 partial 50 %

Castigul total: 29.5

Cazul 2. Nu este permisa fractionarea obiectelor.

Obiectul 3

Obiectul 4

Obiectul 1

Castigul total: 27

Exemplul 2.rucsac.txt

9


3 7

5 3 4

6 3 4

Cazul 1. Este permisa fractionarea obiectelor.

Obiectul 1 complet

Obiectul 2 partial 66.6667 %

Castigul total: 8

Cazul 2. Nu este permisa fractionarea obiectelor.

Obiectul 1

Castigul total: 6

Solutia returnata de algoritm, pentru cazul ın care nu este permisa fractionarea obiectelor, nueste optima. Optim ar fi sa se aleaga obiectele 2 si 3, care ar da un castig total egal cu 7, maimare decat cel furnizat de algoritm.

Aplicatia 4. Un vanzator trebuie sa dea rest unui client o suma de bani S, avand la dispozitiebancnote de valori b1, b2, ..., bn ın numar nelimitat. Stiind ca vanzatorul intentioneaza sa foloseascaun numar cat mai mic de bancnote, sa se afiseze o modalitate de plata a restului.

Cum vanzatorul vrea sa folosesca un numar cat mai mic de bancnote, strategia lui ar trebui safie urmatoarea: mai ıntai, sa aleaga, pe cat posibil, bancnota cea mai mare, ın numar maximposibil. In acest fel va acoperi o mare parte a sumei cu bancnote putine. Apoi, la fiecare pas,pentru plata sumei ramase ar trebui sa urmeze aceeasi regula: sa aleaga bancnota de valoare ceamai mare posibila, ın numar maxim.

Vom ordona sirul bancnotelor ın ordinea descrescatoare a valorilor acestora. Notam cu xi numarul

de bancnote de valoare bi folosite pentru plata restului, atunci S =n∑

i=1

xibi. Daca Sr este suma

ramasa de plata la un moment dat si cea mai mare bancnota disponibila este de valoare bi(bi ≤ Sr), atunci vor fi folosite un numar de [Sr/bi] bancnote de acest fel.

Problema nu are ıntotdeauna solutie. De exemplu, daca restul de plata este S = 19 si suntdisponibile bancnote de valoare 5 si 10, atunci nu se poate gasi nici o combinatie de bancnotepentru plata restului.

Datele de intrare vor fi citite din fisierul text rest.txt. Pe prima linie a fisierului se afla numaruln al bancnotelor disponibile si suma de plata S, separate prin spatii. Linia a doua a fisieruluicontine n numere naturale, separate prin spatii, reprezentand valorile bi ale bancnotelor.Datele de iesire, numarul de bancnote din fiecare tip folosit la plata restului, vor fi scrise lasfarsitul aceluiasi fisier.


struct Bancnota

10


{//x = numarul de bancnote ce sunt f o l o s i t eint valoare , x ;

} ;

void s o r t I n s e r a r e D i r e c t a ( Bancnota vec to r [ ] , int n){

int i , j ;Bancnota aux ;for ( i = 1 ; i < n ; i++){

aux = vecto r [ i ] ;j = i − 1 ;while ( ( j >= 0) && ( aux . va l oa r e > vec to r [ j ] . va l oa r e ) ){



}}

void plataRest ( int S , Bancnota b [ ] , int n , o fstream &fout ){

int i = 0 ;while (S > 0 && i < n){

i f (b [ i ] . va l oa r e <= S){

// fo l o s im bancnota b [ i ]b [ i ] . x = S / b [ i ] . va l oa r e ;S = S − b [ i ] . x ∗ b [ i ] . va l oa r e ;

}i++ ;

}i f (S == 0){

fout<<”Pentru p la ta r e s t u l u i s−au f o l o s i t : ”<<endl ;for ( int i = 0 ; i < n ; i++)

i f (b [ i ] . x != 0)fout<<b [ i ] . x<<” bancnote de va loa r e ”

<<b [ i ] . va loare<<endl ;}else

fout<<”Fara s o l u t i e ! ”<<endl ;}

11


int main ( ){

int n , S ;Bancnota b [ dim ] ;i f s t r e a m f i n ( ” r e s t . txt ” ) ;i f ( ! f i n ){


}f i n>>n ;f i n>>S ;for ( int i = 0 ; i < n ; i++ ){

f i n>>b [ i ] . va l oa r e ;b [ i ] . x = 0 ;

}f i n . c l o s e ( ) ;s o r t I n s e r a r e D i r e c t a (b , n ) ;o f s t ream fout ( ” r e s t . txt ” , i o s : : app ) ;p lataRest (S , b , n , f out ) ;f out . c l o s e ( ) ;return 0 ;

}

Exemplul 1.rest.txt

2 65

10 25

Fara solutie!

Acest algoritm de tip greedy nu furnizeaza o solutie corespunzatoare datelor de intare de maisus. Observam ca totusi aceasta exista: plata sumei cu un numar minim de bancnote se facefolosind o bancnota de valoare 25 si 4 de valoare 10. In schimb, algoritmul selecteaza 2 bancnotede 25 (acesta e numarul maxim: 65/25) si ramane fara nicio posibilitate de a plati suma ramasa(= 15).

Daca printre bancnote exista si unele de valoare 1, atunci acest algoritm furnizeaza ıntotdeaunao solutie.

Exemplul 2.rest.txt

3 65

12


10 25 1

Pentru plata restului s-au folosit:

2 bancnote de valoare 25



Pe de alta parte, chiar daca suma S poate fi platita cu bancnotele disponibile, aceasta metodanu asigura obtinerea optimului global. Rezolvarea exacta a problemei se face folosind tehnicaBacktracking, cautand astfel toate solutiile posibile ale problemei si alegand-o apoi pe cea optima.

Exemplul 3.rest.txt

4 129

12 5 1 25




Algoritmul furnizeaza o solutie de plata a restului cu 9 bancnote. Dar suma poate fi platita cu7 bancnote (solutia optima): 129 = 4 ∗ 25 + 2 ∗ 12 + 1 ∗ 5.

Daca bancnotele disponibile sunt de valori egale cu puterile unui numar natural k ≥ 2, k0, k1, k2,..., kn−1, disponibile ın numar nelimitat, atunci algoritmul de tip greedy furnizeaza solutia optimaa problemei.

Exemplul 4.rest.txt

6 139

1 4 2 16 8 32






Asadar, un algoritm greedy nu conduce ıntotdeauna la solutia optima si, ın unele cazuri, nicimacar la o solutie a problemei. Este doar o tehnica generala, urmand ca pentru fiecare caz ınparte sa determinam daca obtinem sau nu solutia optima.

13

curs12 mate

Documents