13
1 1
Lect. univ. dr. Adrian Runceanu
PROIECTAREA
ALGORITMILOR
Universitatea “Constantin Brâncuşi” Târgu-Jiu
Facultatea de Inginerie
Departamentul de Automatică, Energie şi Mediu
13
2 2 Proiectarea Algoritmilor - curs
Curs 13
Metoda
Greedy
13
3 3 Proiectarea Algoritmilor - curs
Conţinutul cursului
13.1. Prezentarea generala a metodei
13.2. Schema generala a metodei
13.3. Implementari ale metodei
13
4 4 Proiectarea Algoritmilor - curs
13.1. Prezentarea generala a metodei
• Algoritmii de tip greedy, backtracking si de programare dinamicã se aplicã unor probleme a cãror solutie poate fi exprimatã sub forma unui vector de numere întregi (cu valori între 1 si n).
• Intr-o problemã de optimizare trebuie gãsitã solutia optimã dintre toate solutiile posibile.
• Alte clase de probleme cu solutie vectorialã sunt probleme de enumerare a tuturor solutiilor posibile si probleme de decizie, la care trebuie spus dacã existã sau nu cel putin o solutie.
13
5 5 Proiectarea Algoritmilor - curs
13.1. Prezentarea generala a metodei
• Metoda Greedy se poate aplica unor
probleme de optimizare cu solutie vectorialã,
ca alternativã mai eficientã la o cãutare
exhaustivã (de tip 'backtracking').
• Un algoritm Greedy este un algoritm iterativ
(nerecursiv) care determinã în fiecare pas k o
componentã x[k] a vectorului solutie si nu mai
revine ulterior la aceastã alegere.
13
6 6 Proiectarea Algoritmilor - curs
13.1. Prezentarea generala a metodei
• Numele metodei ('Greedy'= lãcomie) sugereazã modul de lucru:
– la stabilirea valorii lui x[k] se alege dintre candidatii posibili pe acela care este optim în pasul k, deci un optim local.
• In general, aceastã alegere precipitatã, grãbitã si care nu tine seama de valorile ce vor fi stabilite în pasii urmãtori pentru x[k+1],..x[n] nu poate garanta solutia optimã a problemei.
13
7 7 Proiectarea Algoritmilor - curs
13.1. Prezentarea generala a metodei
• In functie de specificul problemei, un algoritm
greedy poate conduce la solutia optimã sau la o
solutie destul de bunã, desi suboptimalã.
• Rezultatul unui algoritm greedy pentru o
problemã datã depinde si de datele concrete ale
problemei, sau chiar de ordinea introducerii lor.
• De exemplu, în problema exprimãrii unei sume de
bani printr-un numãr minim de monede de valori date
rezultatul (optim sau suboptim) depinde de valorile
monedelor si de valoarea sumei.
13
8 8 Proiectarea Algoritmilor - curs
13.1. Prezentarea generala a metodei
• Algoritmul greedy foloseste monedele în
ordinea descrescãtoare a valorilor lor, deci “se
repede” la monedele de valoare maximã, care
vor fi în numãr mai mic pentru aceeasi sumã.
• Fie monede de valori 11,5 si 1:
– pentru suma 12 rezultatul algoritmului greedy va
fi optim (douã monede de valori 11 si 1)
– dar pentru suma 15 rezultatul algoritmului
greedy nu va fi optim (5 monede de valori
11,1,1,1,1 în loc de 3 monede de valori 5,5,5).
13
9 9 Proiectarea Algoritmilor - curs
Conţinutul cursului
13.1. Prezentarea generala a metodei
13.2. Schema generala a metodei
13.3. Implementari ale metodei
13
10 10 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
• Pentru a exemplifica această metodă
considerăm o mulţime A cu n elemente.
• Problema care ar trebui rezolvată constă din
determinarea unei submulţimi B a lui A.
• Aceasta trebuie să îndeplinească anumite
condiţii pentru a fi acceptată ca soluţie.
• Dintre toate submulţimile acceptate (numite
soluţii posibile), se va alege una singură numită
soluţie optimă.
13
11 11 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
• Dintre soluţiile posibile trebuie aleasă cea optimă tinând cont de proprietatea următoare:
• Dacă B este soluţie posibilă şi CB atunci şi C este soluţie posibilă.
• Multimea este întotdeauna soluţie posibilă.
• Iniţial se porneşte de la mulţimea vidă.
• Se alege într-un anumit fel un element din A, neales la paşii precedenţi.
• Dacă acestă adăugare la soluţia parţial construită conduce la o soluţie posibilă atunci construim noua soluţie posibilă prin adăugarea elementului – procedura Greedy1.
13
12 12 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
procedure Greedy1 (A, n, B) begin B<- for i=1 to n do begin ALEGE(A, i, x) POSIBIL(B, x, v) if v=1 then ADAUG(B, x) end end
13
13 13 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
• Procedura ALEGE selectează un element x =
aj { aI, . . ., an } şi efectuează interschimbarea ai
aj.
• Procedura POSIBIL verifică dacă B {x} este
soluţie posibilă, caz în care variabila booleană v
va lua valoarea 1, altfel ea va lua valoarea 0.
• Procedura ADAUG înlocuieşte pe B cu B {x}.
13
14 14 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
• Procedura ALEGE nu precizează deloc cum
se selectează un element x, de aceea trebuie
stabilită o procedură de prelucrare ( PREL ),
care va preciza ordinea în care vor fi
introduse elementele lui A în soluţie -
procedura Greedy2 .
13
15 15 Proiectarea Algoritmilor - curs
13.2. Schema generala a metodei
procedure Greedy2(A, n, B) begin PREL B<- for i=1 to n do begin POSIBIL(B, ai, v ) if v=1 then ADAUG(B, ai) end end
13
16 16 Proiectarea Algoritmilor - curs
Conţinutul cursului
13.1. Prezentarea generala a metodei
13.2. Schema generala a metodei
13.3. Implementari ale metodei
13
17 17 Proiectarea Algoritmilor - curs
13.3.1. Algoritm Greedy pentru problema
rucsacului
Problema rucsacului, sau problema selectiei optime, se poate enunta astfel:
Fiind date n obiecte, fiecare cu greutatea g[i] si valoarea v[i] si un rucsac cu capacitatea totalã Gt, sã se determine ce obiecte trebuie selectate pentru a fi luate în rucsac astfel încât greutatea lor totalã sã nu depãseascã Gt si valoarea lor sã fie maximã.
Problema poate avea douã variante :
- varianta fractionarã, dacã se pot lua pãrti din fiecare obiect;
- varianta 0/1, dacã nu se pot lua decât obiecte întregi.
13
18 18 Proiectarea Algoritmilor - curs
13.3.1. Algoritm Greedy pentru problema
rucsacului
• In varianta 0/1 vectorul solutie are n componente si fiecare x[k] poate fi 1 sau 0 dupã cum obiectul k a fost sau nu selectat.
• Un algoritm greedy ordoneazã obiectele dupã valoarea lor unitarã (dupã raportul v[i]/g[i]) si verificã fiecare obiect din aceastã listã de candidati dacã mai are loc sau în rucsac.
• Pentru problema fractionarã metoda greedy conduce sigur la solutia optimã, dar pentru varianta 0/1 nu este garantatã solutia optimã.
13
19 19 Proiectarea Algoritmilor - curs
Lista candidatilor este lista obiectelor, ordonatã dupã valoarea lor specificã.
Exemplu numeric: n=3, Gt=15
Solutia greedy spune cã trebuie selectat obiectul 1, valoarea selectiei fiind 20.
Vectorul solutie: x[1]=1, x[2]=0, x[3]=0
Solutia optimã este cea care ia obiectele 2 si 3, cu valoarea totalã 22 si greutatea totalã 14:
x[1]=0, x[2]=1, x[3]=1
i 1 2 3
g[i] 10 6 8
v[i] 20 10 12
v[i]/g[i] 2.0 1.66 1.5
13
20 20 Proiectarea Algoritmilor - curs
Implementarea acestui algoritm:
#include<iostream.h>
float c[20],g[20],ef[20];
// c - vectorul in care se trec castigurile pt. fiecare obiect in parte
// g - vectorul in care se trec greutatile fiecarui obiect
// ef - vectorul eficientei transportului fiecarui obiect
// de fapt, eficienta este castigul impartit la greutate (castigul obtinut prin transportul unitatii de greutate)
13
21 21 Proiectarea Algoritmilor - curs
int ordine[20];
// ordine - vector folosit la sortarea in ordine
descrescatoare a eficientei de transport
int i, n, aux1, invers;
// n - numarul de obiecte
// i - contor de lucru
// aux1 - variabila de interschimbare
// invers - variabila folosita la sortarea vectorului
ordine
float gr, aux, castig;
13
22 22 Proiectarea Algoritmilor - curs
int main(void)
{
cout<<"Greutatea ce poate fi transportata ";
cin>>gr;
cout<<endl<<" Dati numarul de obiecte ";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<endl<<"cost["<<i<<"]= "; cin>>c[i];
cout<<"greutate["<<i<<"]= "; cin>>g[i];
ordine[i] = i;
ef[i] = c[i] / g[i];
cout<<"eficienta pt. obiectul "<<i<<" este "<<ef[i];
}
13
23 23 Proiectarea Algoritmilor - curs
do{
invers=0;
for(i=1;i<=n-1;i++)
if(ef[i] < ef[i+1])
{
//sortam vectorul ef
aux=ef[i]; ef[i]=ef[i+1]; ef[i+1]=aux;
//sortam vectorul c
aux=c[i]; c[i]=c[i+1]; c[i+1]=aux;
//sortam vectorul g
aux=g[i]; g[i]=g[i+1]; g[i+1]=aux;
invers=1;
//sortam vectorul ordine aux1=ordine[i];
ordine[i]=ordine[i+1];
ordine[i+1]=aux1;
}
}while(invers!=0);
13
24 24 Proiectarea Algoritmilor - curs
castig=0;i=1;
cout<<endl;
cout<<"Posibilitatea de incarcare eficienta a rucsacului este : "<<endl;
while( (gr > 0) && (i <= n) )
{
if(gr > g[i])
{
cout<<"se incarca obiectul "<<ordine[i]<<" : "<<1<<endl;
gr=gr-g[i];
castig=castig+c[i];
}
else
{
cout<<"se incarca obiectul "<<ordine[i]<<" : "<<gr/g[i]<<endl;
gr=0;
castig=castig+c[i]*gr/g[i];
}
i++;
}
cout<<"Castig total = "<<castig;
}
13
25 25 Proiectarea Algoritmilor - curs
13
26 26 Proiectarea Algoritmilor - curs
13.3.2. Algoritm Greedy pentru problema
submultimii de suma data
Se da o multime de numere pozitive, P
si un numar M.
Se cere determinarea unei submultimi
a lui P a carui suma a elementelor sa fie
cel mult M.
13
27 27 Proiectarea Algoritmilor - curs
#include <iostream.h>
int main()
{
int n, p[200], rez[200], k, M, i, j, sum, temp, x;
cout<<"introduceti n: "; cin>>n;
for (i=0; i<n; i++)
{
cout<<"p["<<i<<"]=";
cin>>p[i];
}
cout<<"Introduceti suma: "; cin>>M;
/* incepem abordarea greedy a problemei */
/* ordonam crescator multimea de numere p */
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (p[i]>p[j])
{ temp = p[i]; p[i] = p[j]; p[j] = temp; };
13
28 28 Proiectarea Algoritmilor - curs
k = 0;
sum = 0;
for (i=0; i<n; i++)
{
x = p[i]; /* alege(A, i , x) */
if ( sum + x <= M )
{
rez[k++] = x;
sum += x;
}
else break;
}
cout<<"submultimea rezultat: ";
for (i=0; i<k; i++) cout<<" "<<rez[i];
}
13
29 29 Proiectarea Algoritmilor - curs
13
30 30 Proiectarea Algoritmilor - curs
13.3.3. Algoritm Greedy pentru problema
determinarii sumei maxime
Se da o multime X= { x1, x2, . . ., xn }
cu elemente reale.
Sa se determine o submultime a lui X
astfel încât suma elementelor submultimii
sa fie maxima.
13
31 31 Proiectarea Algoritmilor - curs
13.3.3. Algoritm Greedy pentru problema
determinarii sumei maxime
#include <iostream.h>
int n,i,k;
float s[20],x[20];
int main(void)
{
cout<<"Dati numarul de elemente n = ";cin>>n;
cout<<endl<<"Dati elementele vectorului "<<endl;
for(i=1;i<=n;i++)
{
cout<<"x["<<i<<"]= ";
cin>>x[i];
}
13
32 32 Proiectarea Algoritmilor - curs
13.3.3. Algoritm Greedy pentru problema
determinarii sumei maxime
k=0;
for(i=1;i<=n;i++)
if(x[i]>0)
{
k++;
s[k]=x[i];
}
cout<<"Submultimea ceruta este formata din : ";
for(i=1;i<=k;i++) cout<<s[i]<<" ";
}
13
33 33 Proiectarea Algoritmilor - curs
13
34 34 Proiectarea Algoritmilor - curs
13.3.4. Algoritm Greedy pentru problema
determinarii a k divizori
Fiind dat numarul natural k > 1, se cere
sa se determine cel mai mic numar natural
n având exact k divizori naturali proprii
(diferiti de 1 si n).
13
35 35 Proiectarea Algoritmilor - curs
13.3.4. Algoritm Greedy pentru problema
determinarii a k divizori
#include<iostream.h>
int n,i,k,s,v;
int verif(int n,int k)
{
int i=0,j;
for(j=2;j<=n-1;j++)
if(n%j==0) i++;
if(i==k) v=1;
else v=0;
return v;
}
13
36 36 Proiectarea Algoritmilor - curs
int main(void)
{
cout<<"Dati numarul de divizori k > 1 ";cin>>k;
cout<<endl<<"Cel mai mic numar care are exact "<<k<<" divizori este "<<endl;
n=k+2;
s=0;
while(s==0)
{
v=verif(n,k);
if(v==1)
{
cout<<n;
s=1;
}
n++;
}
}
13
37 37 Proiectarea Algoritmilor - curs
13
38 38 Proiectarea Algoritmilor - curs
Întrebări?