Algoritmi de optim local ('Greedy')
Prezentarea metodei Greedy
Algoritmii de tip greedy, backtracking si de programare dinamicã se aplicã unor probleme a cãror solutie poate fi exprimatã sub forma unui vector de numere întregi (cu valori între 1 si n).
Intr-o problemã de optimizare trebuie gãsitã solutia optimã dintre toate solutiile posibile. Alte clase de probleme cu solutie vectorialã sunt probleme de enumerare a tuturor solutiilor posibile si probleme de decizie, la care trebuie spus dacã existã sau nu cel putin o solutie.
Metoda Greedy se poate aplica unor probleme de optimizare cu solutie vectorialã, ca alternativã mai eficientã la o cãutare exhaustivã (de tip 'backtracking'). Complexitatea unui algoritm greedy este polinomialã. Un algoritm Greedy este un algoritm iterativ (nerecursiv) care determinã în fiecare pas k o componentã x[k] a vectorului solutie si nu 14514w221o mai revine ulterior la aceastã alegere.
Numele metodei ('Greedy'= lãcomie) sugereazã modul de lucru: la stabilirea valorii lui x[k] se alege dintre candidatii posibili pe acela care este optim în pasul k, deci un optim local.
In general, aceastã alegere precipitatã, grãbitã si care nu tine seama de valorile ce vor fi stabilite în pasii urmãtori pentru x[k+1],..x[n] nu poate garanta solutia optimã a problemei.
In functie de specificul problemei, un algoritm greedy poate conduce la solutia optimã sau la o solutie destul de bunã, desi suboptimalã. Rezultatul unui algoritm greedy pentru o problemã datã depinde si de datele concrete ale problemei, sau chiar de ordinea introducerii lor.
De exemplu, în problema exprimãrii unei sume de bani printr-un numãr minim de monede de valori date rezultatul (optim sau suboptim) depinde de valorile monedelor si de valoarea sumei. Algoritmul greedy foloseste monedele în ordinea descrescãtoare a valorilor lor, deci “se repede” la monedele de valoare maximã, care vor fi în numãr mai mic pentru aceeasi sumã.
Fie monede de valori 11,5 si 1. Pentru suma 12 rezultatul algoritmului greedy va fi optim (douã monede de valori 11 si 1), dar pentru suma 15 rezultatul algoritmului greedy nu va fi optim (5 monede de valori 11,1,1,1,1 în loc de 3 monede de valori 5,5,5).
Dacã existã mai multe solutii optime egale ca valoare, algoritmul greedy produce numai una din aceste solutii. De exemplu, în cazul drumului de cost minim dintre douã noduri dintr-un graf algoritmul greedy atribuit lui Dijkstra produce o singurã solutie; toate drumurile de cost minim pot fi gãsite numai printr-un algoritm ‘Backtracking’.
Simplificând putem spune cã metoda greedy conduce la solutia optimã pentru problemele care au proprietatea de optim local, adicã solutia optimã pentru problema de dimensiune n contine în ea solutiile optime pentru probleme de acelasi tip dar de dimensiune mai micã. Metoda greedy se aplicã si pentru probleme care nu satisfac aceastã conditie, pentru cã ea produce o solutie bunã, destul de apropiatã de solutia optimã într-un timp mult mai scurt decât o metodã “backtracking”.
In aceste cazuri metoda greedy este consideratã ca o metodã euristicã, care “ghiceste” solutia bunã fãrã sã facã o analizã exhaustivã a tuturor solutiilor posibile. O solutie 'bunã' este o solutie al cãrui cost este cel putin jumãtate din costul solutiei optime.
Schema generalã a unui algoritm Greedy
Incercarea de a folosi o schemã generalã de algoritm greedy, care apoi sã fie adaptatã fiecãrei probleme specifice, are avantajul cã pune în evidentã strategia comunã tuturor programelor bazate pe algoritmi greedy, dar si dezavantajul unor programe neoptimizate. De aceea, în literaturã programele de tip greedy apar în forme foarte diferite si exploateazã particularitãtile problemei rezolvate pentru a realiza un cod sursã minim si un timp minim de executie.
O procedurã greedy generalã contine un ciclu principal în care, la fiecare pas, se alege o valoare pentru o componentã a solutiei x[k]. Alegerea se face dintr-o listã de candidati, listã care poate fi unicã pentru toti pasii, sau se modificã (se genereazã din nou) la fiecare pas. Vom considera o functie “genCand” care genereazã aceastã listã de candidati si care este apelatã la fiecare pas, desi uneori poate fi scoasã în afara ciclului (lista se genereazã o singurã datã). Functia “optim” va selecta candidatul optim din lista de candidati “cand”.
Lista de candidati este, ca tip abstract de date, o coadã cu prioritãti, pentru a permite extragerea rapidã a candidatului optim (maxim sau minim) dintr-o colectie dinamicã, la care se pot adãuaga noi candidati. Teoretic, cea mai bunã implementare a unei cozi cu prioritãti este un vector “heap”, dar din motive de simplitate se foloseste deseori un vector.
Un vector ordonat de candidati este suficient atunci când lista initialã de candidati nu se mai modificã prin adãugarea altor candidati. O alternativã la ordonare o reprezintã selectarea si eliminarea valorii maxime (sau mimine) din vector, la fiecare pas din ciclul principal greedy.
Selectarea unui candidat ca valoare pentru x[k] antreneazã dupã sine si alte operatii, specifice problemei, care vor fi reunite în functia “include”. Functia “posibil” verificã anumite conditii specifice problemei în functie de care candidatul optim este sau acceptat în solutie.
Functia generalã “greedy” presupune cã elementele vectorului solutie se determinã în ordinea x[1],x[2],..x[n], desi existã cazuri în care ordinea determinãrii acestor componente este alta.
// variabile globale
int n; // lungime vector solutie
int x[NX]; // vector solutie
// algoritm greedy general
void greedy()
Aceastã functie poate fi folositã ca atare si completatã cu subprogramele dependente de aplicatie : genCand, init, posibil, include, optim, solutie. Eventual, mai intervine o secventã care determinã valoarea lui x[k] în functie de candidatul optim selectat.
De observat cã determinarea componentelor vectorului solutie nu se face neapãrat în ordinea x[1], x[2], x[3],...x[n]. Un exemplu în acest sens îl constituie algoritmul greedy pntru colorarea nodurilor unui graf cu numãr minim de culori.
O altã posibilitate este de a scrie fiecare program bazat pe un algoritm greedy fãrã a defini aceste functii si exploatând la maxim particularitãtile problemei date, dar având ca model strategia greedy generalã descrisã anterior.
Algoritm Greedy pentru problema restului
Problema restului cere exprimarea unei sume de bani (un rest de platã) printr-un numãr minim de monede cu valori date.
Fie n tipuri de monede cu valori c[1],c[2],..c[n] si o sumã R. O solutie este un vector x[1], x[2], ..x[n] , unde x[k] este numãrul de monede de valoare c[k] necesar pentru achitarea sumei R. deci, R= x[1]*c[1] + x[2]*c[2] + ... + x[n]*c[n]. O parte din valorile x[k] pot fi zero, dacã nu se folosesc monedele corespunzãtoare.
Vectorul solutie, în aceastã problemã, poate fi considerat ca un vector de lungime fixã (egalã cu numãrul de monede distincte) sau ca un vector de lungime variabilã, cu x[k] egal cu numãrul de monede stabilit în pasul k si considerat complet la exprimarea întregii sume de platã.
Algoritmul greedy încearcã sã foloseascã monedele în ordinea descrescãtoare a valorii lor, deci începe cu moneda de valoare maximã si determinã numãrul maxim de monede de acest tip pentru suma de plata, apoi încearcã cu moneda imediat inferioarã s.a.m.d.
Lista de candidati este lista monedelor disponibile, ordonatã descrescãtor; la fiecare pas se extrage primul element din listã. Pentru anumite valori ale monedelor, acest algoritm conduce la solutia optimã pentru orice sumã R. Complexitatea este O(n).
Vom exemplifica cu o instantã a a problemei pentru care solutia greedy nu este si solutia optimã. Lista ordonatã de monede: c[1]=11, c[2]=5, c[3]=1. Suma de platã R= 15.
Solutia greedy : x[1]= 1, x[2]=0, x[3]= 4 (5 monede)
Solutia optimã : x[1]= 0, x[2]=3, x[3]= 0 (3 monede)
// alg. greedy ptr. determinare numar minim de monede
#define M 20 // nr. maxim de monede diferite
int c[M], x[M] ; // c = valori monede, x= num†r monede
int n,rest ; // rest = suma de plata
int greedy_rest ()
else // putea lipsi instr. if...else
x[k]=0;
}
return (rest==0 ? 1 : -1); // -1 daca rest > 0
void main ()
Lista valorilor monedelor se introduce în ordine descrescãtoare sau se ordoneazã în programul principal, înainte de apelarea functiei “greedy_rest”. Evolutia programului pentru exemplul anterior este urmãtoarea:
k c[k] x[k] R nm
initial 15 0
1 11 1 4 1
2 5 0 4 1
3 1 4 0 5
Algoritm Greedy pentru problema rucsacului
Problema rucsacului, sau problema selectiei optime, se poate enunta astfel:
Fiind date n obiecte, fiecare cu greutatea g[i] si valoarea v[i] si un rucsac cu capacitatea totalã Gt, sã se determine ce obiecte trebuie selectate pentru a fi luate în rucsac astfel încât greutatea lor totalã sã nu depãseascã Gt si valoarea lor sã fie maximã.
Problema poate avea douã variante :
- varianta fractionarã, dacã se pot lua pãrti din fiecare obiect;
- varianta 0/1, dacã nu se pot lua decât obiecte întregi.
In varianta 0/1 vectorul solutie are n componente si fiecare x[k] poate fi 1 sau 0 dupã cum obiectul k a fost sau nu selectat.
Un algoritm greedy ordoneazã obiectele dupã valoarea lor unitarã (dupã raportul v[i]/g[i]) si verificã fiecare obiect din aceastã listã de candidati dacã mai are loc sau în rucsac. Pentru problema fractionarã metoda greedy conduce sigur la solutia optimã, dar pentru varianta 0/1 nu este garantatã solutia optimã.
Lista candidatilor este lista obiectelor, ordonatã dupã valoarea lor specificã.
Exemplu numeric: n=3, Gt=15
i 1 2 3
g[i] 10 6 8
v[i] 20 10 12
v[i]/g[i] 2.0 1.66 1.5
Solutia greedy spune cã trebuie selectat obiectul 1, valoarea selectiei fiind 20 . Vectorul solutie: x[1]=1, x[2]=0, x[3]=0
Solutia optimã este cea care ia obiectele 2 si 3, cu valoarea totalã 22 si greutatea totalã 14 :
x[1]=0, x[2]=1, x[3]=1
// Algoritm greedy ptr problema rucsacului
typedef struct Obiect;
// var globale
int x[M] ; // obiecte selectate (0 / 1)
Obiect a[M]; // greutati obiecte
int n; float gt,gp,vp ;
// daca obiectul k acceptabil
int posibil(int k)
// ciclul greedy
void greedy ()
}
// compara obiecte (ptr qsort)
int Obcomp (const void * p, const void * r)
void main ()
printf (" Greutatea admiså: "); scanf ("%f", >);
qsort (a,n,sizeof(Obiect), Obcomp);
gp=0; vp=0; // greutate si valoare partialå selectie
greedy ();
printf (" Solutia optimå are valoarea: %f \n",vp);
for ( i=0; i<n;i++)
if (x[i])
printf ( "%d %f %f \n", a[i].k, a[i].g, a[i].v);
}
Algoritm Greedy pentru colorarea nodurilor unui graf
Problema colorãrii nodurilor unui graf cu numãr minim de culori constã în atribuirea unei culori (unui numãr) pentru fiecare vârf, astfel încât sã nu existe douã vârfuri adiacente care sã aibã aceeasi culoare. Douã noduri sunt adiacente dacã sunt legate printr-o muchie.
Algoritmul greedy de colorare încearcã sã coloreze cât mai multe noduri din graf cu o aceeasi culoare “c”. In acest scop se cautã, la fiecare pas, acele noduri încã necolorate care nu sunt vecine cu nodurile ce au primit deja culoarea “c”. Procedura de colorare este aplicatã succesiv pentru fiecare culoare posibilã pânã când se coloreazã toate nodurile grafului.
Vectorul solutie contine culoarea fiecãrui vârf si are atâtea componente câte vârfuri existã în graf. Componentele vectorului solutie se obtin într-o ordine dependentã de datele problemei.
De exemplu, graful cu 5 vârfuri si muchiile
1-2, 2-3, 2-4, 3-5, 4-5
va fi colorat de algoritmul greedy astfel :
vârfurile 1,3,4 primesc culoarea 1 (pasul 1)
vârfurile 2,5 primesc culoarea 2 (pasul 2)
Vectorul solutie va fi:
x[1]=1, x[2]=2, x[3]=1, x[4]=1, x[5]=2
Lista de candidati este lista vârfurilor care nu au primit încã o culoare si ea se modificã la fiecare pas (prin eliminarea unor vârfuri).
Conditia de acceptare a unui vârf candidat pentru a fi colorat este ca sã nu existe muchii între el si alte vârfuri de aceeasi culoare.
De observat cã în graful cu 5 vârfuri, dacã se numeroteazã altfel vârfurile (se inverseazã 2 cu 5), atunci metoda greedy nu mai conduce la solutia optimã ( cu numai 2 culori). In acest caz, graba de a colora cât mai multe vârfuri cu o aceeasi culoare, în ordinea numerotãrii lor, nu este o bunã idee.
Pentru graful cu muchiile
1-5, 5-3, 5-4, 3-2, 4-3
solutia greedy foloseste 3 culori si este
x[1]=1, x[2]=1, x[3]=2, x[4]=2, x[5]=3
# define M 30 // nr. maxim noduri graf
// variabile globale
int n,nc ; // n=nr de noduri, nc= nr noduri colorate
int m ; // nr de culori
int a[M][M]; // matrice de adiacente graf
int x[M]; // culori noduri
// algoritmul greedy de colorare
void colorare (int c)
}
// repeta ptr fiecare culoare
void main ()
Algoritm Greedy pentru acoperire cu multimi
Problema acoperirii cu multimi este o problemã de optimizare clasicã în selectia unor resurse si se formuleazã astfel: Se dã o multime scop S si o familie de n multimi candidat C astfel cã orice element din S apartine cel putin unei multimi din C; se cere sã se determine numãrul minim de multimi din C care acoperã complet pe S (reuniunea acestor multimi include multimea S).
Exemplu de date si rezultate :
S = , n=4
C[1]= , C[2] =, C[3] = , C[4] =
Solutia optimã este :
sau, mai exact x[1]=2, x[2]=4 .
Colectia de multimi C poate fi un vector de multimi, iar solutia va fi un vector de indici în C.
Algoritmul "greedy" selecteazã, la fiecare pas, acea multime C[k] care acoperã cele mai multe elemente neacoperite încã din S (intersectia lui C[k] cu S contine numãrul maxim de elemente). Dupã alegerea unei multimi C[k] se modificã multimea scop S, eliminând din S elementele acoperite de multimea C[k]. Ciclul "greedy" se opreste atunci când multimea S devine vidã.
Lista candidatilor este lista multimilor C, ordonatã dupã cardinalul intersectiei dintre C[k] si S.
Exemplu de date pentru care algoritmul greedy nu determinã solutia optimã :
S = , n=4;
C[1]= , C[2]= , C[3] = , C[4] =
Solutia greedy este , dar solutia optimã este
Urmeazã câteva secvente importante din programul care rezolvã aceastã problemã.
#define M 20 // nr. maxim de multimi candidat
Set cand[M], scop, aux;
int n ; // n= nr. de multimi candidat
void greedy ()
}
printS (cand[imax]);
removeAll (scop,cand[imax]); // elimina elemente acoperite de candidat
} while ( ! emptyS(scop));
Secventa anterioarã nu a verificat dacã problema admite solutie, dar aceastã verificare se poate face imediat dupã citirea datelor: se reunesc toate multimile candidati si se verificã dacã multimea scop este continutã în reuniunea candidatilor.
|
