Metoda Greedy

In urmatorul articol voi prezenta cateva aplicatii ale acestei tehnici importante de programare denumita stiintific Greedy.

1. Descriere
2. Prezentare
3. Probleme clasice rezolvate prin metoda Greedy
4. Exercitii

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

Observatie: Metoda Greedy nu cauta sa determine toate solutiile posibile ( care ar putea fi prea numeroase) si apoi sa aleaga din ele pe cea optima, ci cauta sa introduca direct un element x in solutia optima.Acest lucru duce la eficienta algorimilor Greedy,insa nu conduc in mod necesar la la o solutie optima si nici nu este posibila formularea unui criteriu general conform caruia sa putem stabili excat daca metoda Greedy rezolva sau nu o anumita problema de optimizare.Acest motiv duce la insotirea fiecarei rezolvari prin metoda Greedy a unei demonstratii matematice(in general prin inductie).

3. Probleme clasice rezolvate prin metoda Greedy

3.1 Problema spectacolelor

A. Problema :
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.

B. Exemplu :

spectacole.in

5
12 30 16 30
15 0 18 0
10 0 18 30
18 0 20 45
12 15 13 0

spectacole.out

5 2 4

C. Solutie
Ordonam spectacolele crescator dupa ora de final.Selectam initial primul spectacol(cel care se termina cel mai devreme).La fiecare pas selectam primul spectacol neselectat,care nu se suprapune cu cele deja selectate(cele care incep dupa ce se termina ultimul spectacol).

#include <stdio.h>

int n,inceput[100],sfarsit[100],nr[100];

void citeste();
void sorteaza();
void rezolva();

int main()
{
    freopen("spectacole.in","r",stdin);
    freopen("spectacole.out","w",stdout);

    citeste();
    sorteaza();
    rezolva();    

    fclose(stdin); fclose(stdout);
    return 0;
}

void rezolva()
{
  int ultim,i;
  for(ultim = 0,i = 1; i < n; i++)     if(inceput[nr[i]] >= sfarsit[nr[ultim]]) // selectam spectacolul ce ne avantajeaza
    {
         printf("%d ",nr[i]+1); ultim = i;
    }
    printf("\n");

}

void sorteaza()   //ordonam crescator spectacolele dupa ora de final
{
    int schimb,i,aux;
    do
    {
        schimb = 0;
        for(i = 0; i < n-1; i++)           if(sfarsit[nr[i]] > sfarsit[nr[i+1]])
          {
              aux = nr[i];
              nr[i] = nr[i+1];
              nr[i+1] = aux;
              schimb = 1;
          }
    }while(schimb);
}

void citeste()
{
   int i,m,h;
   scanf("%d",&n);
   for(i = 0; i < n; i++)
   {
        nr[i] = i+1;
        scanf("%d %d",&h,&m);
        inceput[i] = h * 60 + m;   //pentru fiecare spectacol transformam ora de inceput in minute

        scanf("%d %d",&h,&m);   //pentru fiecare spectacol transformam ora de sfarsit in minute
        sfarsit[i] = h * 60 + m;
   }
}

3.2 Problema rucsacului

A. Problema :
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.

B. Exemplu :

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.

#include<stdio.h>
int o[50]; //ordinea obiectelor
float c[100],g[100],x[100],Gr,GMax;
int n;

void citeste();
void sorteaza();
void rezolva();
void afiseaza();

int main()
{

   freopen("rucsac.in","r",stdin);
   freopen("rucsac.out","w",stdout);

   citeste();
   sorteaza();
   rezolva();
   afiseaza();

   fclose(stdin); fclose(stdout);
   return 0;
}

void citeste()
{
     scanf("%d%e",&n,&GMax);
     for(int i = 0; i < n; i++)
     {
        o[i] = i;
        scanf("%e%e",&c[i],&g[i]); //citim valorile
     }
}

void sorteaza()
{
   int i,schimb,aux;
   do  //ordonam obiectele descrescator dupa castigul unitar
   {
       schimb = 0;
       for(i = 0; i < n-1; i++)
         if(c[o[i]]/g[o[i]] < c[o[i+1]]/g[o[i+1]])
         {
            aux = o[i];
            o[i] = o[i+1];
            o[i+1] = aux;
            schimb = 1;
         }
   }while(schimb);
}

void rezolva()
{
   int i;
   for(i = 0,Gr = GMax; i < n && Gr > g[o[i]]; i++)
   {
         x[o[i]] = 1; Gr-= g[o[i]];
   }
}

void afiseaza()
{
   for(int i = 0; i < n; i++)
     if(x[i]) printf("%d %e \n",i+1,x[i] * 100);
}

Aceasta tehnica este folosita intr-un mare numar de probleme si aplicatii printre care putem aminti :

• 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

Aceste tehnici vor fi prezentate si discutate in timp. 🙂