Tehnica GreedyEste o optiune ce tine de specificul problemei cu implicatii asupra

complexitatii. Se bazeaza pe statistica datelor de la intrare din care se

extrag caracteristici ale datelor=>alegerea strategiei.

Strategia Greedy=strategia in care optimul local se considera optim

general. Este o strategie constructiva prin adaugarea treptata de

solutii locale care construiesc solutia finala.Problema=problemele

locale care dau solutii ce se asambleaza in solutia finala. Obs: cand

strategia nu duce la o solutie(in cazul neliniaritatilor)

Se da o multime A si se cere (B inclus in A) care are criteriile

obligatorii si se cer si criteriile de optimalitate neobligatorii.Solutia

este de a alege un elem. din A succesiv care maximalizeaza

optimalitatea in momentul alegerii lui=>se construieste B prin

respectarea criteriilor obligatorii.Solutiile cu ajutorul alg. Dextra.

Problemele au urmatoarea structura:

- Se da o multime A={a1 a2, …, an}

- Se cere sa determinam o submultime B a multimii A,

care indeplineste anumite conditii pentru a fi acceptata

in calitate de solutie.

Analiza Algoritmurilor

Pentru a putea decide care dintre algoritmii ce

rezolvă aceeaşi problemă este mai bun, este

nevoie să definim un criteriu de apreciere a

valorii unui algoritm. In general, acest criteriu se

referă la timpul de calcul şi la memoria necesară

unui algoritm.

- tehnica Greedy poate fi privită ca un caz particular al

tehnicii Backtracking, în care se renunţă la mecanismul

de întoarcere;

- ambele tehnici oferă soluţii sub formă de vector;

-tehnica Backtracking poate oferi toate soluţiile

problemei, în timp ce tehnica Greedy oferă o singură

soluţie;

-tehnica Greedy nu dispune de mecanimul întoarcerii,

specific tehnicii Backtracking.

Greedy - Backtracking

- tehnica Greedy conduce mai repede la o solutie.

- problemele de tip Greedy pot fi rezolvate prin metoda trierii , generînd consecutiv cele 2n submulîimi ale

mulţimii A;

- Dezavantajul metodei trierii constă în faptul că timpul

cerut pentru executarea algoritmului respectiv este

foarte mare.

Greedy – Metoda trierii

De remarcat:

• Cel care elaborează un algoritm Greedy, procedînd în modul ales de el, ajunge la

rezultatul dorit.

• Pentru fiecare problemă în parte, după ce se identifică un algoritm, este obligatoriu

să se demonstreze că aceata conduce la soluţia optimă.

• Demonstraţia faptul că se ajunge la soluţia optimă este specifică fiecărei probleme

în parte.

• Tehnica Greedy conduce la timp de calcul polinomial.

· Pentru a rezolva o problemă cu Greedy, soluţia se

construieşte, după regula:

Pentru fiecare element care urmeză să fie adăugat soluţiei

finale, se efectuează o alegere a sa din elementele mulţimii A

(după un mecanism specific fiecărei probleme în parte), iar dacă

este posibil, aceasta este adăugat.

Algoritmul se termină fie cînd a fost găsită soluţia cerută, fie

cînd s-a constatat inexistenţa acesteia.

Pentru a evita trierea tuturor submultimilor multimii A în

metoda Greedy se utilizează un criteriu (o regulă) care asigură

alegerea directă a elementelor necesare.

De obicei regulile de selecţie nu sunt indicate în mod explicit în condiţia problemei si totul

depinde de ingeniozitatea programatorului.

Schema generală a unui algoritm bazat pe metoda

Greedy:

While ExistaElemente dobegin

AlegeUnElement(x);

IncludeElementul(x)

end.

NU întotdeauna există un algoritm de tip Greedy care găseşte

soluţia optimă.

Există probleme pentru care nu se cunosc astfel de algoritmi. Mai

mult, pentru cele mai multe probleme, nu se cunosc algoritmi

Greedy.

Nu tuturor problemelor li se pot aplica algoritmi de

tip Greedy.

Pentru problemele pentru care nu se cunosc

algoritmi care necesită timp polinomial, se caută

soliţii, chiar dacă nu optime, atunci apropiate de

acestea, dar care au fost obţinute în timp util.

Multe din aceste soliţii sunt obţinute cu Greedy.

Astfel de agoritmi se numesc algoritmi euristici.

Probleme pentru care Greedy obţine soluţia

optimă

1. Suma componentelor prime : Fie a o variabilă indexată, ale cărei componente

A(1) , A(2),…, A(n)sunt numere naturale nenule. Să se determine suma componentelor care sunt numere prime. Atunci când un număr prim se repetă, el va fi luat în consideraţie o singură dată.

Solutie

2. Problema spectacolelor:

Într-o sală într-o zi trebuie planificate n spectacole. Pentru fiecare spectacol se cunoaşte intervalul în care se desfăşoară: (st, sf). Se cere să se planifice un număr maxim de spectacole astfel încît să nu se suprapună.

Solutie3. Memorarea optimala a fisierelor pe benzi

Se cere o aranjare optima a n fisiere cu lungimile L1, L2, ... ,Ln pe o banda

magnetica in ipoteza ca timpul de citire al unui fisier este proportional cu

lungimea sa, iar pe banda citirea fisierului k implica si citirea celor k-1 fisiere

precedente. Presupunem ca frecventa de citire a unui fisier este aceeasi pentru

toate fisierele. Aranjarea optima a fisierelor pe o banda magnetica înseamna

gasirea acelei dispuneri a fisierelor care sa permita obtinerea unui timp mediu de

citire minim.

Solutie

nume_1 date fis_1 EOF nume_2 Date fis_2 EO

F

...... EO

F

Vom identifica fisierele printr-un numar natural cuprins оntre [1, n], iar

lungimea fisierului i prin valoarea Lpi.

1 2 n

Lp1 Lp2............................... Lpn

Metoda Greedy are două componente:

- stabilirea soluţiei de început;

- optimizarea acesteia.

Să luăm un exemplu concret , pe baza căruia vom ilustra cum se ‘’construieşte’’ soluţia.

Fie secvenţa :

8, 7, 8, 4, 9, 7, 5, 5, 4, 8, 7, 5, 9.

Deoarece A (1) este 8, nefiind număr prim se porneşte cu soluţia iniţială S:=0 (dacă A (1)

ar fi fost număr prim, am fi pornit cu soluţia s:=A(1)).

Apoi valorile lui S vor fi:

S:=0

S:=0+7=7

S:=7+5=12

De remarcat caracterul constructiv al soluţiei. Un termen curent (fie acesta A( i )) contribuie

la valoarea lui S dacă îndeplineşte două condiţii :

- este un număr prim;

- n-a mai fost utilizat.

Dacă in prealabil ordonăm crescător secvenţa considerată obţinem:

4, 4, 5, 5, 5, 7, 7, 7, 8, 8, 8, 9, 9

şi astfel se “vede’’ mult mai uşor repetabilitatea unui numar prim( faţă de situaţia iniţială

când pentru a constata dacă un număr prim a fost sau nu utilizat trebuie să parcurgem

întreaga secvenţă de fiecare dată ).

Pe baza afirmaţiilor anterioare rezultă un model de rezolvare pentru problema

propusă, model care dă structura generală a metodei Greedy :

Citire ( n , A);

Ordonare ( n , A );

If A [1] = NumarPrim Then S := A[1]

Else S:=0;

I := 2;

While I n do

begin

If (A[ I] <> A(I-1) )and (A [I] =Numarprim ) Then S := S +A [I]

I := I+1;

End;

Fie o planificare optimă a spectacolelor (un număr maxim k de

spectacole i1, i2,...,ik unde i1, i2,...,ik{1,2,…N} şi spectacolul ij are

loc înaintea spectacolului i j+1). O astfel de planificare îndeplineşte

condiţia: spectacolul ij+1 începe după terminarea spectacolului ij.

o consecinţă imediată a condiţiei de mai sus este: spectacolul ij ia

sfîrşit înaintea terminării spectacolului ij+1(consecinţa nu implică

un efort de gîndire deosebit).

Vom construi o soluţie după următorul algoritm:

P1. Sortăm spectacolele după ora terminării lor;

P2 . Primul spectacol programat este cel care se termină cel

mai devreme;

P3. Alegem primul spectacol dintre cele care urmează în şir

după ultimului spectacol programat care îndeplineşte condiţia

că începe după ce s-a terminat ultimul spectacol programat;

P4. Dacă tentativa de mai sus a eşuat (nu am găsit un astfel de

spectacol) algoritmul se termină, astfel se programează

spectacolul găsit şi algoritmul se reia de la pasul 3.

Lemă. Algoritmul de mai sus conduce la soluţie optimă (număr maxim de spectacole

programate).

Demonstraţie:

Fie s1, s2,...,sl spectacole ordonate ca mai sus şi o soluţie optimă i1, i2,...,ik.

Dacă l=k rezultă că soliţia găsită este optimă;

Dacă l>k rezultă că soluţia i1, i2,...,ik nu este optimă (se contrazice ipoteza);

Dacă l<k procedăm ca mai jos.

Presupunem că i1s1. În acest caz putem înlocui i1 (în cadrul soluţiei opime) cu s1 (s1

este primul spectasol care se termină şi dacă ar figura pe altă poziţie în cadrul soluţiei

optime, se contrazice ipoteza). În concluzie, soluţia s1, i2,...,ik rămîne optimă.

Fie lt primul indice pentru care stit. Soluţia s1, s2,...,st-1 it... este optimă. Înlocuim it

cu st. Înlocuirea este posibilă pentru că:

St nu figurează în cadrul soluţiei optime între primele t-1 componente;

St nu figurează între ultimile poziţii ale soluţiei optime (începînd cu poziţia t+1) pentru

că în acest caz înseamnă că st începe după terminarea lei it, caz în care se contrazic

modul în care a fost obţinut de algoritm alegerea lui st.

Procedînd astfel, la un mment dat soluţia optimă aete de forma: s1, s2,...,sl...ik.

Aceasta înseamnă că după sl a mai fost posibil să adăugăm alte spectacole. Se

contrazicemodul de obţinere al soluţiei de către algoritm. De aici rezultă k=i şi că

algoritmul obţine soluţia optimă.

Program SPECT;

Type spectacol=array[1..2, 1..10] of integer; ordine=array[1..10] of integer;

var s:spectacol; o:ordine; n,i,h1,m1,h2,m2:integer;

procedure sortare; var gata:boolean; m,i:integer;

begin

repeat

gata:=true;

for I:=1 to n-1 do if s[2,o[i]]>s[2,[I+1]] then

begin

m:=o[i]; o[i]:=o[I+1]; o[I+1]:=m; gata:=false

end

until gata; end;

begin

write(‘n’); readln(n);

for I:=1 to n do

Begin o[i]:=i; write(‘ora de ]nceput pentru spestacolul’,I,’(hhmm)=’);

readln(h1,m1); s[1,i]:=h1*60+m1; write(‘ora de sfrsit pentru

spestacolul’,I,’(hhmm)=’); readln(h2,m2); s[2,i]:=h1*60+m2;

end;

sortare; writeln(‘ordinea spectacolelor este ’); writeln(o[1]);

for I:=2 to n do

if s[1,o[i]]>=s[2,o[I-1]]

then writeln(o[i]); end.

Tehnica Greedy conduce la timp de calcul polinomial.

Motivul care conduce la acest timp de calcul, tine de

mecanismul tehnicii.

Să presupunem că mulţimea din care se face alegerea

are n elemente si că soluţia are tot n elemente (caz maxim). Se

fac n alegeri, la fiecare alegere se fac n teste, rezulta un

algoritm cu timp O(n2).

De multe ori este necesar ca elementele mulţimii A să

fie sortate, pentru ca apoi să alegem din acestea, iar sortarea

necesita un timp minim O(n * log2n). Insă sortarea se

efectuează la început. Prin urmare, acest timp se adună, deci

nu influenţează rezultatul.