Greedy

Metoda Greedy
“De alegerea strategiei depinde atât timpul de rezolvare cât și calitatea soluției gasite“

1. Descrierea metodei

Se dă o mulţime A cu n elemente şi se cere să se determine o submulţime a sa(B) care satisface anumite restricţii. Această submulţime se numeşte soluţie posibilă. Se cere să se determine o soluţie posibilă care fie să maximizeze fie să minimizeze o anumită funcţie obiectiv dată. Această soluţie posibilă se numeşte soluţie optimă.
Metoda Greedy lucrează în paşi astfel:
  1. se iniţializează mulţimea soluţiilor (B) cu mulţimea vidă
  2. se alege un anumit element x din A
  3. se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor, dacă da atunci va fi adăugat
  4. procedeul continuă astfel, repetitiv, cu pasul 2 până când au fost determinate toate elementele din mulţimea soluţiilor
Observaţie. Metoda Greedy nu caută să determine toate soluţiile posibile ( care ar putea fi prea numeroase) şi apoi să aleagă din ele pe cea optimă, ci caută să introducă direct un element x în soluţia optimă.
2. Ideea metodei: La fiecare pas se alege un element care face solutia partiala cat mai buna. Se presupune ca facand mereu alegerea cea mai buna la moment, avem sansa (dar nu certitudinea) obtinerii solutiei optime, in final.
Algoritmii Greedy sunt foarte eficienți, dar nu conduc în mod necesar la o soluție 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 însoțit de o demonstrație a corectitudinii sale . Demonstrația faptului că o anumită problemă are proprietatea alegerii Greedy se face de obicei prin inducție matematică

O întrebare firească este aceea dacă algoritmul Greedy duce totdeauna la soluţie optimă? Evident că nu Sunt situaţii când soluţia găsită nu este optimă. Mai mult, pentru cele mai multe din probleme nu se cunosc algoritmi Greedy de rezolvare. Spre deosebire de Backtracking, algoritmul Greedy nu permite atunci când s-a oservat că nu se poate ajunge la soluţie pentru o anumită secvenţă de elemente, revenirea înapoi, pe nivelele anterioare. Pentru problemele care nu duc la soluţia optimă este necesar să se caute soluţii, chiar dacă nu optime, dar cât mai apropiate de acestea.
Între metoda Greedy şi metoda Backtracking putem enumera următoarele diferenţe:
• ambele tehnici oferă soluţii sub formă de vector
• tehnica Backtracking oferă toate soluţiile problemei, în timp ce Greedy oferă o singură soluţie
• tehnica Greedy nu dispune de mecanismul întoarcerii, specific tehnicii Backtracking
Algoritmi clasici: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.
rucsac.cpp


Problema platii unui salariu. Sa se plateasca un salariu dat cu numar minim de monezi, daca se 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

#include
using namespace std;
int n,i,aux,ok,s,a[100], nr[100];
main()
{
cout<<“Suma=”;cin>>s;
cout<<“Numarul de bancnote:“;cin>>n;
for(i=1;i<=n;i++)
{
cout<<“a[”<>a[i];
nr[i]=i;
}
do
{
ok=1;
for(i=1;i<=n-1;i++)
if(a[nr[i]] {
aux=nr[i];
nr[i]=nr[i+1];
nr[i+1]=aux;
ok=0;
}
}
while(ok==0);
for(i=1;i<=n;i++)
cout< i=1;
cout< do
{
if(s/a[nr[i]]>0)
{cout< s=s%a[nr[i]];}
i++;
}
while(i<=n);
}
Problema spectacolelor
Managerul artistic al unui festival trebuie să selecteze o mulțime cât mai amplă de spectacole ce pot fi jucate în singura sală pe care o are la dispoziție. Ştiind că i s-au propus n≤100 spectacole şi pentru fiecare spectacol i i-a fost anunțat 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) scrieți 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.
Soluție
Ordonăm spectacolele crescător după ora de final. Selectăm inițial primul spectacol (deci cel care se termină cel mai devreme). La fiecare pas selectăm primul spectacol neselectat, care nu se suprapune cu cele deja selectate (deci care începe după ce se termină ultimul spectacol selectat).
#include
int inceput[100], sfarsit[100], nr[100];
int main()
{int n, i, h, m, ok, ultim, aux;
cout << “n= “; cin >> n; citire
cout<<“Introduceti inceputul si sfarsitul spectacolelor”;
for (i=1; i<=n; i++)
{nr[i]=i;
transform timpul in minute
cin>>h>>m; inceput[i]=h*60+m;
cin>>h>>m; sfarsit[i]=h*60+m;} ordonez spectacolele crescator dupa ora de final
do
{ok=1;
for (i=1; i
if (sfarsit[nr[i]]>sfarsit[nr[i+1]])
{aux=nr[i];nr[i]=nr[i+1];nr[i+1]=aux; ok=0;}
}
while (ok==0);
cout << “Spectacolele selectate sunt:”<
ultim=1;
for ( i=2; i<=n; i++)
if (inceput[nr[i]]>=sfarsit[nr[ultim]])
{cout <
cout<
return 0;}

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).
comis.cpp
Problema partitiilor de numere prime// Se da un sir de numere naturale citite pe rand pana la intalnirea numarului 0.Sa se determine un grup maxim de elemente ale sirului cu proprietatea ca elementele sunt numerele prime iar suma lor e egala cu cel mult un numar m dat .

part.cpp