Prezentarea metodei Greedy

Metoda de programare Greedy se aplică problemelor de optimizare. Aceasta metoda constă în faptul că se construieşte solutia optimă pas cu pas, la fiecare pas fiind selectat în solutie elementul care pare „cel mai bun/cel mai optim” la momentul respectiv, în speranta că această alegere locală va conduce la optimul global.
Algoritmii Greedy sunt foarte eficienti, dar nu conduc în mod necesar la o solutie optimă. Şi nici nu este posibilă formularea unui criteriu general conform căruia să putem stabili exact dacă metoda Greedy rezolvă sau nu o anumită problemă de optimizare. Din acest motiv, orice algoritm Greedy trebuie însotit de o demonstratie a corectitudinii sale . Demonstratia faptului că o anumită problemă are proprietatea alegerii Greedy se face de obicei prin inductie matematică.

Metoda Greedy se aplică problemelor pentru care se dă o mulţime A cu n elemente şi pentru care trebuie determinată o submulţime a sa, S cu m elemente, care îndeplinesc anumite condiţii, numite si conditii de optim. Algoritmul in limbaj natural al metodei de programare Greedy are urmatoarea structura:
Algoritm Greedy:
se dă o mulţime A
se cere o submulţime S din multimea A care sa:
să îndeplinească anumite condiţii interne (să fie acceptabilă)
să fie optimală (să realizeze un maxim sau un minim).
Principiul metodei Greedy:
se iniţializează mulţimea soluţiilor S cu mulţimea vidă, S=Ø
la fiecare pas se alege un anumit element x∈A (cel mai promiţător element la momentul respectiv) care poate conduce la o soluţie optimă
se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor:
dacă da atunci
va fi adăugat şi mulţimea soluţiilor devine S=S∪{x} – un element introdus în mulţimea S nu va mai putea fi eliminat
altfel
el nu se mai testează ulterior
procedeul continuă, până când au fost determinate toate elementele din mulţimea soluţiilor
Aplicatii:

1. Sumă maximă: Se dă o mulţime A={a1, a2, . . ., an} cu elemente reale. Să se determine o submulţime a lui S astfel încât

suma elementelor submulţimii să fie maximă.( Sursa C++ )
produsul elementelor submultimii sa fie maxima (Sursa C++)
Exemplu: daca N=10 si elemntele multimii A sunt (-3, 7, 9, -2, 19, 20, -10, 15, -20, -5). Rezultatul asteptate este:

suma maxima are valoarea 70 si se obtine adunand doar valorile strict pozitive : 7+9+19+20+15
produsul maxim are valoarea 1077300000 si se obtine inmultind cele mai mici numere negative (se vor inmulti un numar par de valori negative) si toate nuerele strict pozitive : (-20)*(-10)*(-5)*(-3)*7*9*15*19*20

2. Problema spectacolelor

Managerul artistic al unui festival trebuie să selecteze o multime cât mai amplă de spectacole ce pot fi jucate în singura sală pe care o are la dispozitie. Ştiind că i s-au propus n≤100 spectacole şi pentru fiecare spectacol i i-a fost anuntat intervalul în care se poate desfăşura [si, fi) (si reprezintă ora şi minutul de început, iar fi ora şi minutul de final al spectacolului i)
Scrieti un program care să permită spectatorilor vizionarea unui număr cât mai mare de spectacole.

De exemplu, dacă vom citi n=5 şi următorii timpi:
12 30 16 30
15 0 18 0
10 0 18 30
18 0 20 45
12 15 13 0

Spectacolele selectate sunt: 5 2 4. Rezolvare

3. Problema continua a rucsacului. ( Sursa C++)

Un hot neprevăzător are la dispozitie un singur rucsac cu care poate transporta o greutate maximă Gmax. Hotul are de ales din n≤50 obiecte şi, evident, intentionează să obtină un câştig maxim în urma singurului transport pe care îl poate face. Cunoscând pentru fiecare obiect i greutatea gi şi câştigul ci pe care hotul l-ar obtine transportând obiectul respectiv în întregime, scrieti un program care să determine o încărcare optimală a rucsacului. Obiectele nu pot fi sectionate

De exemplu, pentru n=5, GMax=100 şi câştigurile-greutătile următoare:
(1000 120), (500 20), (400 200), (1000 100), (25 1) se va afişa pe ecran:

Maximizarea valorilor unei expresii (Sursa C++)

Se dau n numere întregi, nenule b1, b2, …, bn şi m numere întregi nenule a1, a2, …, am , cu m<=n. Să se determine o submulţime a mulţimii B={ b1, b2, …, bn } care să maximizeze valoarea expresiei

E= a1* x1 + a2 * x2+…+ am * xm

ştiind că n mai mare sau egal cu m şi că xi apartine multimii { b1, b2, …, bn }

Exemplu: Pentru m=5 şi multimea A={5, 9, -4, 2, -3}, si n=8 şi multimea B={6, 1, -2, 4, -3, -5, -1, 8} expresia este:

E= 5*x1 + 9*x2 – 4*x3 + 2*x4 – 3*x5

Problema comisului voiajor. (Sursa C++)

Un comis voiajor trebuie să viziteze un număr n de oraşe şi să se întoarcă în oraşul de plecare astfel încât să nu treacă de două ori prin acelaşi loc. Cunoscând legăturile dintre oraşe şi distanţele corespunzătoare, să se afişeze traseul de lungime minimă pe care să-l parcurgă comisul voiajor.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s