Metoda Greedy

1.Descriere

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplica la o varietate larga de probleme.In general,aceasta metoda se aplica problemelor de optimizare.Specificul acestei metode consta in faptul ca se construieste solutia optima pas cu pas,la fiecare pas fiind selectat(sau „inghitit”) in solutie elementul care pare „cel mai bun”la momentul respectiv,in speranta ca va duce la solutie optima globala.

2.Prezentare

Se da o multime A cu n elemente si se cere sa se determine o submultime a sa(B) care satisface anumite restrictii. Aceasta submultime se numeste solutie posibila. Se cere sa se determine o solutie posibila care fie sa maximizeze fie sa minimizeze o anumita functie obiectiv data. Aceasta solutie posibila se numeste solutie optima.
Metoda Greedy lucreaza in pasi astfel:
1. Multimea B este vida la inceput
2. Se alege un element din A care pare a fi solutia optima la pasul i
3. Se verifica daca elementul ales poate fi adaugat la multimea solutiilor, daca da atunci va fi adaugat

4. Procedeul continua astfel, repetitiv, pana cand au fost determinate toate elementele din multimea solutiilor

3. Problemă rezolvată prin metoda Greedy

Un hot nepravazator are la dispozitie un singur rucsac cu care poate transporta o greutate maxima Gmax.Hotul are de ales din n <= 50 obiecte si,evident,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,in ipoteza ca hotul poate incarca in rucsac orice parte dintr`un obiect.
rucsac.in
5 100

1000 120
500 20
400 200
1000 100
25 1

rucsac.out

2 100.00%
4 79.00%
5 100.00%

C. Solutie :
Vom reprezenta o solutie a problemei ca un vector x cu n componente,in care retinem pentru fiecare obiect fractiunea incarcata in rucsac de hot.Deci vectorull x trebuie sa indeplineasca urmatoarele conditii :
1. Xi E [0,1], V i E { 1,2,…n }; //unde E = apartine si V = oricare ar fi
2. G1 * X1 + G2 * X2 + .. + Gn * Xn <= GMax;
3. f(x) = C1 * X1 + C2 * X2 + … + Cn * Xn este maxima.
Ordonam obiectele descrescator dupa castigul pe unitatea de greutate(valoare care constituie o masura a eficientei transportarii obiectelor). Cat timp este posibil (incap in rucsac),selectam obiectele in intregime.Completam rucsacul cu un fragment din urmatorul obiect ce nu a fost deja selectat.

Program Rucsac;

Var     g:array [1..10] of integer;

          i,n,Gm,R, aux : integer;

         ok:boolean;

begin

 writeln('nr obiecte'); readln(n); 

writeln(‘capacitate  rucsac'); readln(R);

 writeln(' Obiectele de luat în rucsac:' );

 for  i:=1 to n do

        read (g[i]);

ok:=false;

while(ok=false) do

 begin

 ok:=true;

 for i:=1 to n-1 do

 if g[i]>g[i+1]   then

        begin

         aux:=g[i];

         g[i]:=g[i+1];

         g[i+1]:=aux;

         ok:=false;

        end;

  end;

writeln;
  for  i:=1 to n do
     write( g[i], '*');

Gm:=0 ;

  i:=1;

     while ( Gm +g[i]<=R ) do

     begin

      Gm:=Gm+g[i];

      i:=i+1;

     end;

  writeln('sunt‘ ,i-1,‘ obiecte cu greutate‘ , Gm,‘) ;

   writeln ( ‘  a ramas‘ , R-Gm,‘ loc liber‘ ) ;

Utilizarea metodei Greedy în rezolvarea problemelor:

·         Minimizarea timpului mediu de asteptare

·         Interclasarea optima a sirurilor ordonate

·         Coduri Huffman

·         Cele mai scurte drumuri care pleaca din acelasi punct

·         Problema comis-voiajorului

·         Arbori partiali de cost minim