Algoritmi de optim local ('Greedy') - Prezentarea metodei Greedy

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", &gt);

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.