universitatea constantin brâncuşi” târgu-jiu facultatea de ... · proiectarea algoritmilor -...

38
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

Upload: others

Post on 21-Oct-2019

18 views

Category:

Documents


2 download

TRANSCRIPT

Page 1: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 2: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

2 2 Proiectarea Algoritmilor - curs

Curs 13

Metoda

Greedy

Page 3: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 4: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 5: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 6: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 7: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul 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.

Page 8: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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).

Page 9: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 10: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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ă.

Page 11: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 12: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 13: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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}.

Page 14: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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 .

Page 15: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 16: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 17: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 18: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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ã.

Page 19: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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

Page 20: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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)

Page 21: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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;

Page 22: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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];

}

Page 23: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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);

Page 24: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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;

}

Page 25: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

25 25 Proiectarea Algoritmilor - curs

Page 26: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 27: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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; };

Page 28: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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];

}

Page 29: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

29 29 Proiectarea Algoritmilor - curs

Page 30: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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.

Page 31: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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];

}

Page 32: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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]<<" ";

}

Page 33: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

33 33 Proiectarea Algoritmilor - curs

Page 34: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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).

Page 35: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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;

}

Page 36: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

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++;

}

}

Page 37: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

37 37 Proiectarea Algoritmilor - curs

Page 38: Universitatea Constantin Brâncuşi” Târgu-Jiu Facultatea de ... · Proiectarea Algoritmilor - curs 7 13.1. Prezentarea generala a metodei • In functie de specificul problemei,

13

38 38 Proiectarea Algoritmilor - curs

Întrebări?