RSS

Metoda Greedy

15 Jan

De alegerea strategiei depinde atat timpul de rezolvare cat si calitatea solutiei gasite

Prezentarea metodei

Problema: Fie A o multime de N elemente. Se cere sa se determine o submultime a sa care sa indeplineasca maximizeze/minimizeze o expresie (functie obiectiv )data. Aceasta solutie, daca exista, se numeste solutie optima.

Ideea metodei: La fiecare pas se alege un element care imi face solutia partiala cat mai buna. Se presupune ca facand mereu alegerea cea mai buna la moment, am sansa (dar nu certitudinea) obtinerii solutiei optime, in final.
Exemplu : sortarea prin selectie

Algoritmi clasici:

Problema platii unui salariu. Sa se plateasca un salariu dat cu numar minim de monezi, daca sa cunosc tipurile de monezi existente. Monedele sunt in numar nelimitat (variante cu/fara atingerea solutiei optime).
Cazul 1. Se atinge solutia optima.
Suma= 360; Monedele sunt 100, 50, 20,10,3
360=3*100+1*50+1*10+0*3
Cazul 2. Nu se atinge solutia optima
Suma= 365; Monedele sunt 100, 50, 20,10,3
365=3*100+1*50+1*10+1*3 NEPLATIT 2
Optim ar fi fost:
365=3*100+1*50+0*10+5*3

Problema rucsacului. Un hot are la dispozitie un rucsac cu care poate transporta o greutate maxima Gmax. Hotul are de ales din n obiecte si intentioneaza sa obtina un castig maxim in urma singurului transport pe care il poate face. Cunoscand, pentru fiecare obiect i greutatea Gi si castigul Ci pe care hotul l-ar obtine transportand obiectul respectiv in intregime, scrieti un program care sa determine o incarcare optima a rucsacului.

Problema spectacolelor. Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole ce pot fi jucate in singura sala pe care o are la dispozitie. Stiind ca i s-au propus n (n <= 100) spectacole si pentru fiecare spectacol i-a fost anuntat intervalul in care se poate desfasura [Si ,Fi] (Si reprezinta ora si minutul de inceput,iar Fi ora si minutul de final al spectacolului i), scrieti un program care sa permita spectatorilor vizionarea unui numar cat mai mare de spectacole.

Problema comis-voiajorului. Se cunosc distantele dintre mai multe orase. Un comis-voiajor pleaca dintr-un oras si doreste sa se intoarca in acelasi oras, dupa ce a vizitat fiecare din celelalte orase exact o data. Problema este de a minimiza lungimea drumului parcurs. (Indicatie. La fiecare pas se alege orasul nou, cel mai apropiat).

Tema : joc3, startreck, baby, reactivi. (http://campion.edu.ro)

 

2 responses to “Metoda Greedy

  1. Larisa

    17/10/2012 at 23:08

    Adica , dacă avem un container cu volumul de 400 de unități și 5 obiecte ce cu volumele ( și respectiv costurile acestora) :
    1)80=40
    2)120=60
    3)240=120
    4)40=20
    5)160=100
    , e corect să afirmăm că valoarea optimă-i 46 ( a obiectelor 4,3,2)? Întrucît se încadrează exact în limetele volumului de capacitate , unde totodată suma maximă posibilă .?!

     
  2. mchelariu71

    18/10/2012 at 08:29

    conform algoritmului, daca prima valoare e volumul si a doua e pretul, intr-adevar obiectele sunt ordonate dupa raportul volum/pret. in ordinea de acolo, introducem in sac, cat se poate: 1, 2, 4,5 pana acoperim cele 400 de unitati.
    aici mai poate fi o discutie. daca putem folosi partial un obiect. daca da, atunci obiectul 3 va putea fi folosit si atunci vom avea 80/40, 120/60, 200/120 adica 400 unitati.

     

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

 
%d bloggers like this: