Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda greedy

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Functii trigonometrice
Tablouri multi-dimensionale
Alocarea dinamica a memoriei
Operatorul de fortare a tipului sau de conversie explicita (expresie cast)
Modifica informatia nodului cu info=para din lista
Pointeri si adrese
Setarea ecranului in mod text
Sterge valoarea primelor m nodurilor din lista
Instructiunea break
Operatori logici la nivel de bit

TERMENI importanti pentru acest document

Metoda greedy

Prezentarea metodei




In general, metoda greedy (in traducere “avida”) se aplica problemelor in care, pentru o multime data M = , se cere determinarea unei submultimi a sa care sa indeplineasca anumite conditii.

O solutie a problemei se numeste solutie posibila. Cum, in general, exista mai multe solutii posibile se cere sa se determine una singura conform unui criteriu. Acest criteriu se numeste criteriu de optimizare si solutia determinata se numeste solutie optima.

Metoda greedy construieste solutia optima pas cu pas prin determinarea la fiecare pas a unei solutii partiale numita solutie acceptabila. O solutie acceptabila are urmatoarea proprietate: daca S este o solutie acceptabila si S atunci este o solutie acceptabila. Se presupune ca multimea vida Ř este intotdeauna solutie acceptabila.

Daca metoda greedy rezolva problema, atunci ultima solutie acceptabila determinata este solutie posibila care este si optima.

Pentru a rezolva problema sunt necesare urmatoarele:

multimea initiala M;

o functie c1 care exprima criteriul de selectie a unui element mj inca neselectat din multimea M pentru a fi adaugat eventual la solutia acceptabila S;

o functie t1 care testeaza daca elementul selectat mj este acceptabil;

o functie t2 care testeaza daca noua solutie acceptabila S := S este solutie posibila;

o functie c2 care exprima criteriul de optimizare.

Observatii

Metoda greedy nu determina toate solutiile posibile si abia apoi sa o aleaga pe cea optima dintre acestea (ceea ce ar necesita timp de calcul si spatiu de memorie mari), ci incearca sa determine de la bun inceput o solutie posibila care sa fie si optima.

Functia c1 este de obicei obtinuta din functia c2, uneori aceste doua functii sunt chiar identice. De aceea, solutiile acceptabile sunt solutii optime locale. Dar, prin optimizari locale succesive, nu se obtine totdeauna in final solutia optima globala. Uneori metoda nu furnizeaza nici macar o solutie posibila.

In functie de modul de selectare al elementelor din multimea M se obtin doua variante ale metodei greedy pe care le prezentam in continuare sub forma unor proceduri.

PROCEDURA GREEDY1(M, n, S);

BEGIN

S :=

FOR i := 1 TO n DO

ESELECT(M, i, mj);

EACCEPT(S, mj, v1);

IF v1 = 1 THEN

SACCEPT(S, mj);

SPOSIBIL(S, v2);

IF v2 = 1 THEN EXIT;

ENDIF;

ENDFOR;

END.

Procedura ESELECT selecteaza, conform criteriului c1, elementul mj I si efectueaza interschimbarea dintre mi si mj.

Procedura EACCEPT determina, conform testului t1 valoarea lui v1:

daca mj este element acceptabil,

in caz contrar.

Procedura SACCEPT determina noua solutie acceptabila S := S

Procedura SPOSIBIL determina, conform restului t2, valoarea lui v2:

daca S este solutie posibila,

in caz contrar.

A doua varianta a metodei greedy este urmatoarea:

PROCEDURA GREEDY2(M, n, S);

BEGIN

PERM(M);

S :=

FOR i:=1 TO n DO

EACCEPT(S, mi, v1);

IF v1=1 THEN

SACCEPT(S, mi);

SPOSIBIL(S, v2);

IF v2=1 THEN EXIT;

ENDIF;

ENDIF;

ENDFOR;

END.

Procedura PERM efectueaza conform unui criteriu o permutare a elementelor multimii M.

Observatii

In procedura Greedy1 ordinea in care trebuie selectate elementele se stabileste in mod dinamic la fiecare pas prin procedura ESELECT, iar in procedura GREEDY2 aceasta ordine se stabileste de la inceput prin procedura PERM.

Procedurile GREEDY1 si GREEDY2 sunt prezentate pentru cazul general. Ele pot fi adaptate pentru fiecare problema rezolvabila cu aceasta metoda.

Teorema 4.1

Metoda greedy are complexitatea O(n2).

Demonstratie

Instructiunea FOR itereaza de cel mult n ori. Complexitatea unei iteratii a instructiunii FOR este O(n). Deci complexitatea metodei este O(n2).

Probleme rezolvate

Problema G1

Problema submultimii cu valoare maxima.

Se da o multime M = cu elemente numere reale. Sa se determine o submultime a sa, astfel incat sa fie maxima.

Rezolvare

Daca mi ≤ 0 oricare ar fi mi I M atunci S = }. Daca exista mi > 0, mi I M, atunci rezolvam problema cu metoda greedy. In acest caz elementele problemei sunt urmatoarele.

multimea M = a elementelor de numere reale date;

o solutie acceptabila este o submultime cu proprietatea ca , k = 1, …, p;

o solutie posibila este o solutie acceptabila S care contine toate elementele mi din M cu mi ≥ 0;

o solutie optima este o solutie posibila; vom determina solutia optima cu toate elementele mi > 0;

criteriul de selectie este evident mi > 0.

Procedura este urmatoarea:

PROCEDURA SUBMAX(M,n,S);

BEGIN

S :=

FOR i := 1 TO n DO

IF mi > 0 THEN

S:=S ;

ENDIF;

ENDFOR;

END.

Codul sursa al programului C care implementeaza algoritmul de mai sus este:

#include<stdio.h>

#include<limits.h>

void main()

max=-INT_MAX;

k=0;

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

if(a[i]>0)

s[++k]=a[i];

else

if (a[i]>max)

max=a[i];

if(k==0)

s[++k]=max;

printf('Elementele care formeaza suma maxima: ');

for(i=1;i<=k;i++)

printf('%d ',s[i]);

printf('n');

Problema G2

Problema restului de plata.

Avand la dispozitie o multime de monede, cum poate fi achitat un rest de plata folosind un numar minim de monede.

Rezolvarea cu metoda greedy

Sa notam cu R restul care trebuie achitat si cu M = multimea bancnotelor pe care le avem la dispozitie. Evident ca M si presupunem ca fiecare bancnota mi I M exista intr-un numar suficient de mare. Avem:

Elementele problemei sunt urmatoarele:

multimea M = a bancnotelor pe care le avem la dispozitie;

o solutie acceptabila este o submultime de bancnote astfel incat

o solutie posibila este o solutie acceptabila Sj astfel incat ; fie P = multimea solutiilor posibile;

o solutie optima este o solutie posibila Sp astfel incat sp = min, unde si corespunde la Si din P, i=1, , q;

criteriul de selectie al bancnotelor din multimea M este evident mj = max, mj n-a fost inca selectata. Adica, se selecteaza moneda care are valoarea cea mai mare.

In continuare sa consideram doua cazuri concrete.

In cazul 1 consideram R = 131, M= si notam prin Ri restul curent de plata.

Ri

mi



nri

131

31

50

31

10

1

1

0

Rezulta solutia optima Sp = , np = , sp=5.

In cazul 2 consideram: R = 340, M =

Ri

mi

nri

340

100

3

40

50

0

40

30

1

10

20

0

10

In acest caz nu s-a ajuns la o solutie posibila, desi exista solutie posibila, anume 340 = 3x100 + 2x20. Aceasta solutie posibila ar fi fost gasita daca s-ar fi facut revenire si s-ar fi modificat una dintre selectiile anterioare. Dar metoda greedy nu accepta reveniri.

Rezolvarea problemei prin metoda greedy, respectiv prin procedura GREEDY2, este prezentata in procedura ACHIT

PROCEDURA ACHIT(M, n, S, N);

BEGIN

ORD(M);

S := ; N :=

FOR i := 1 TO n DO

EACCEPT(R, mi, ni, v1);

IF v1 = 1 THEN

SACCEPT(S, mi, N, ni);

SPOSIBIL(R, v2);

IF v2 = 1 THEN

EXIT;

ENDIF;

ENDIF;

ENDFOR;

END.

Procedura ORD ordoneaza descrescator multimea M si se obtine o permutare a acestei multimi.

Procedura EACCEPT calculeaza ni := [R / mi], R := R - ni * mi si valoarea lui v1 in modul urmator:

Procedura SACCEPT determina: S := S , N := N

Procedura SPOSIBIL determina valoarea lui v2 in modul urmator:

Remarcam faptul ca procedura ACHIT poate fi elaborata fara a face apel la alte proceduri.

Codul sursa al programului este:

#include<stdio.h>

void AfisSol(int s[20], int nr[20], int dim)

void ordonare(int m[20], int n)

void eaccept(int m, int& rest, int& nr, int& v1)

void saccept(int& k, int s[20], int nr[20], int m, int r)

void achit(int n, int m[20], int rest, int s[20], int nr[20], int& k)

}

void main()

printf('Suma de platit:');

scanf('%d',&rest);

achit(n, m, rest, s, nr, dim);

AfisSol(s, nr, dim);

Problema G3

Problema continua a rucsacului

Un hot sparge un magazin in care gaseste n obiecte divizibile (poate fi luata si numai o parte dintr-un obiect) care il tenteaza. Din pacate, greutatea lor totala depaseste capacitatea sacului pe care hotul il are la dispozitie. Prin urmare, el este nevoit sa aleaga doar cateva din cele n obiecte. Hotul alege obiectele in functie de greutatea si valoarea lor, in asa fel incat valoarea finala a furtului sa fie maxima. Datele de intrare se gasesc in fisierul sac.in: pe prima linie un numar real reprezentand capacitatea rucsacului, pe a doua linie numarul n de obiecte, iar pe urmatoarele n linii se gasesc cate doua numere reale reprezentand valoarea, respectiv greutatea fiecarui obiect. Sa se afiseze obiectele furate de hot.

Rezolvare

Elementele problemei sunt urmatoarele.

n obiecte identificate prin valorile V = , si greutatile G = lor; capacitatea sacului C;

o solutie acceptabila este o submultime formata din k obiecte cu proprietatea ca unde k n ;

o solutie posibila este o solutie acceptabila care indeplineste conditia unde k n;

o solutie optima este solutia posibila;

criteriul de selectie este: dupa ce au fost selectate k obiecte se alege un obiect p astfel incat .

Procedura este urmatoarea:

PROCEDURA SAC(V, G , n, C);

BEGIN

ARRAY V(n), G(n), E(n);

FOR i := 1 TO n DO

e := vi / gi;

ORDONARE(V, G, E);

i := 1;

WHILE C – gi > 0 DO

WRITE(Obiectul: vi, gi);

C := C – gi ;

i := i + 1;

ENDWHILE;

IF C > 0 THEN

WRITE(O parte din obiectul (vi, gi): C * vi / gi, C);

ENDIF;

END.

Codul sursa al programului C care implementeaza algoritmul de mai sus este:

#include<stdio.h>

typedef struct

obiect;

void main()

printf('capacitatea rucsacului: ');

scanf('%lf',&capac);

// Se ordoneaza obiectele in functie de raportul

// utilitate / greutate folosind metoda

// prin selectia minimului

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

//se porneste de la primul obiect

i=1;

//cat timp nu s-au term obiectele si

//rucsacul nu e plin

while (i<=n && capac>0)

//daca greut obiectului este mai mare decat

//capacitatea ramasa ob se alege intreg

if(o[i].greut<=capac)

else






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1342
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site