Metoda Greedy
Proiect pentru Atestat Informatică
Metoda Greedy
Metoda Greedy este o metodă care poate fi uneori folosită în rezolvarea problemelor de următorul tip:
Se dă o mulțime A. Să se determine o submulțime B a lui A astfel încât să fie îndeplinite anumite condiții – acestea depinzând de problema propriu-zisă.
Algoritm general
O rezolvare generală de tip Greedy a problemei de mai sus este următoarea:
| PSEUDOCOD |
|---|
B ← ∅
terminat ← FALSE
Execută
Alege convenabil x ∈ A
Dacă x poate fi adăugat în B atunci
B ← B ∪ {x}
Altfel
terminat ← TRUE
SfârșitDacă
Cât timp terminat = FALSE
|
| C++ |
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> A = {1, 2, 3, 4, 5};
vector<int> B;
bool terminat = false;
while (terminat == false) {
if (A.empty())
break;
int x = A.back();
A.pop_back();
bool exista = false;
for (int i = 0; i < B.size(); i++)
if (B[i] == x)
exista = true;
if (!exista) {
B.push_back(x);
} else {
terminat = true;
}
}
for (int i = 0; i < B.size(); i++)
cout << B[i] << " ";
return 0;
}
|
Altfel spus, pornim de la mulțimea vidă și adăugăm în mod repetat în B elemente până când acest lucru nu mai este posibil.
Observații
- Elementul adăugat este ales ca optim local – de aici numele Greedy (lacom).
- Odată adăugat în soluția B, elementul rămâne până la final; nu există revenire ca în Backtracking.
- Alegerea optimului local nu garantează întotdeauna soluția globală optimă.
- Schema prezentată este vagă și nu poate fi standardizată.
- Există relativ puține probleme care pot fi rezolvate cu metoda Greedy.
- Complexitatea metodei este de regulă polinomială.
- Se folosesc două situații principale pentru metoda Greedy:
- Când știm că rezolvarea este corectă.
- Când soluțiile exacte sunt exponențiale, iar Greedy dă o soluție acceptabilă.
- De regulă, elementele mulțimii A sunt ordonate înainte de alegerea optimului local.
Probleme celebre rezolvabile cu metoda Greedy
- Problema spectacolelor
- Problema continuă a rucsacului
- Algoritmul lui Dijkstra pentru drumuri de cost minim
- Algoritmul lui Prim și Algoritmul lui Kruskal pentru arbore parțial de cost minim
Greedy euristic
Există probleme pentru care folosim metoda Greedy pentru o soluție acceptabilă, chiar dacă soluția optimă necesită algoritmi exponențiali.
Exemplu: Săritura calului
Se consideră o tablă de șah cu n linii și m coloane. Un cal trebuie să parcurgă tabla fără să treacă de două ori prin aceeași poziție.
Strategie Greedy pentru tabla mare:
- Pleacă de la poziția inițială
(i_start, j_start) - Cât timp este posibil:
- Alege o poziție vecină în L unde calul nu a mai fost
- Marchează poziția și devine poziția curentă
- Succesul depinde de alegerea poziției vecine.
O strategie bună: alegi poziția vecină cu număr minim de vecini neparcurși. Dacă există mai mulți vecini eligibili, poți alege primul, ultimul, cel mai sus, cel mai jos sau aleatoriu.
Despre algoritmii Greedy
Algoritmii Greedy sunt caracterizați de metoda lor de funcționare: la fiecare pas se alege cel mai bun candidat posibil, după evaluarea tuturor acestora. Metoda determină întotdeauna o singură soluție, asigurând un optim local, dar nu întotdeauna și global. Tehnica Greedy este una de optimizare, rulând mai rapid decât un Backtracking, dar nefiind întotdeauna cea mai bună.
Când nu aveți o idee mai bună legată de o problemă, în timpul unui concurs, o implementare Greedy ar putea aduce în jur de 30% din punctaj. Există situații în care acești algoritmi clachează, cum ar fi problema comisului voiajor sau problemele NP-complete.
Metoda Greedy are și avantaje: poate fi aplicată multor probleme: determinarea celor mai scurte drumuri în grafuri (Dijkstra), determinarea arborelui minimal de acoperire (Prim, Kruskal), codificarea arborilor Huffman, planificarea activităților, problema spectacolelor și problema fracționară a rucsacului.
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.
Date de intrare
Prima linie conține n. Următoarele n linii conțin ora și minutul începerii și terminării fiecărui spectacol.
Date de ieșire
Se vor scrie numerele de ordine ale spectacolelor selectate.
Descrierea soluției
Vom sorta crescător spectacolele după ora de final. Selectăm inițial spectacolul care se termină cel mai devreme, apoi alegem următorul care nu se suprapune.
Implementare C++
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("spectacole.in");
ofstream g("spectacole.out");
int n, inceput[100], sfarsit[100], nr[100];
void citeste() {
int ora, min, i;
f >> n;
for (i = 0; i < n; ++i) {
nr[i] = i;
f >> ora >> min;
inceput[i] = ora * 60 + min;
f >> ora >> min;
sfarsit[i] = ora * 60 + min;
}
f.close();
}
void sorteaza() {
int aux, schimb, i;
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 rezolva() {
int ultim, i;
g << nr[0] + 1 << " ";
for (ultim = 0, i = 1; i < n; ++i)
if (inceput[nr[i]] >= sfarsit[nr[ultim]]) {
g << nr[i] + 1 << " ";
ultim = i;
}
g << endl;
}
int main() {
citeste();
sorteaza();
rezolva();
return 0;
}
Problema fracționară a rucsacului
Dispunem de un rucsac cu capacitatea M și N obiecte definite prin greutate și valoare. Se cere maximizarea valorii totale.
Descrierea soluției
Ordonăm obiectele descrescător după raportul valoare/greutate. Le adăugăm integral cât timp încap, iar ultimul obiect poate fi adăugat parțial.
Implementare C++
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int o[100], N, M;
float val[100], greu[100], x[100], Gr;
void citeste() {
int i;
f >> N >> M;
for (i = 0; i < N; ++i) {
o[i] = i;
f >> val[i] >> greu[i];
}
f.close();
}
void sort() {
int i, aux, schimb;
do {
schimb = 0;
for (i = 0; i < N - 1; ++i)
if (val[o[i]] / greu[o[i]] < val[o[i+1]] / greu[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 = M; i < N && Gr > 0; ++i) {
if (greu[o[i]] <= Gr) {
x[o[i]] = 1;
Gr -= greu[o[i]];
} else {
x[o[i]] = Gr / greu[o[i]];
Gr = 0;
}
}
}
void afisare() {
int i;
for (i = 0; i < N; ++i)
if (x[i] > 0) g << i + 1 << " " << x[i] * 100 << endl;
g.close();
}
int main() {
citeste();
sort();
rezolva();
afisare();
return 0;
}
Precizări
Problema discretă a rucsacului se rezolvă optim prin programare dinamică. În cazul problemei comisului voiajor, Greedy nu garantează soluția optimă. Backtracking explorează mai multe variante, dar are timp de execuție mai mare.
Servicii
Realizare site-uri web, design și programare.