NIST (National Institute of Standards and Technology) da
pentru algoritmul (tehnica algoritmică) Greedy : Un algoritm care, atunci când caută un răspuns, ia întotdeauna soluția imediată, locală. În unele probleme, algoritmii Greedy găsesc soluția globală, optimă, dar în alte probleme pot găsi soluții suboptimale [v. http://www.nist.gov/dads/HTML/greedyalgo.html]. Ca exemple de algoritmi de tip Greedy în care se obține soluția optimă (optimul global) se dau algoritmii lui Kruskal și al lui Prim de construire a arborelui de acoperire de cost minim și algoritmul Dijkstra de determinare a căii de cost minim într-un graf. |
Algoritmii de tip Greedy pot fi aplicați atunci când se dă o mulțime A și se cere să se obțină o submulțime S a acesteia, care satisface anumite restricții și optimizează (maximizează sau, respectiv, minimizează) funcția obiectiv. Se pornește de la o mulțime-soluție S vidă și, la fiecare iterație, se aplică o metodă (procedură sau funcție) de selecție, care alege din elementele încă neutilizate din A pe cel mai bun candidat care satisface restricțiile inpuse, adăugându-se acest candidat la submulțimea S. Algoritmul se oprește atunci când s-a atins obiectivul, sau când se constată că nu se mai gâsește în A un nou element care poate fi adăugat la S.
Sub forma sa cea mai generală, un algoritm Greedy se prezintă astfel:
funcția greedy(C) {
construiește mulțimea S vidă;
cât timp (S nu este soluțieși C nu
este vidă){
selectează din C cel mai bun candidat x;
dacă (x poate fi adăugat la S)
atunci se adaugă elementul x la
submulțimea S și se elimină din C;
}
întoarce S;
}
Funcția greedy primește ca argument mulțimea candidaților C, care conține toate elementele mulțimii data A. C poate fi o copie sau o clona a lui A. Daca A poate fi distrusa prin eliminarea de elemente, atunci C poate fi chiar A.
Remarcăm că funcția greedy invocă o funcție, care selectează cel mai bun element x din submulțimea C a candidaților, și o a doua funcție, care verifică dacă elementul candidat selectat xpoate fi adăugat la submulțimea S. Aceste funcții depind de problema rezolvată. Se consideră că, în procesul iterativ de construire a mulțimii S, fiecare submulțime obținută este tot o soluție posibilă, care poate fi ameliorată la pasul următor prin adăugarea unui nou element. Se alege în acest scop elementul care oferă cea mai mare creștere a funcției obiectiv f(S) în cazul când se caută valoarea maximă a acestei funcții (de aici și denumirea de greedy = lacom), sau cea mai mică creștere, când se caută valoarea minimă.
Complexitatea algoritmului Greedy este O(n2).
În fisierul Greedy.java este dată
clasa abstractă Greedy, care foloseste pentru aplicarea metodei Greedy
conform algoritmului dat mai sus.
Constructorul Greedy(Collection a) primește ca
argument colecția de obiecte dată a și creează colecția
auxiliară c, în care pune toate obiectele din a. Metoda Collection
greedy()aplică algoritmul Greedy și întoarce colecția s a
obiectelor selectate. La fiecare parcurgere a ciclului, această metodă
folosește două metode auxiliare abstracte: Cele două metode auxiliare trebuie definite pentru fiecare problemă rezolvată prin metoda Greedy. |
În fișierul SortSelectie.java
este dată o aplicație în care se sortează prin metoda Greedy o listă de
cuvinte date ca parametri în linia de comandă.
În acest caz, metoda selecție alege obiectul minim din lista candidaților, iar metoda poateFiAdaugat întoarce întotdeauna true, deoarece toate obiectele din lista dată se adauga la lista sortată. |
Rezolvare: Fie xi cantitatea de
produs Pi pusă în rucsac. Avem, desigur, interesul să
umplem rucsacul la greutatea maximă. În consecință, greutatea
produselor din rucsac este G=x1+x2+...xn si
trebuie să fie în final egală cu Gmax, iar costul
conținutului rucsacului este C=x1*p1+x2*p2+...+xn*pn.
Necunoscute sunt greutățile x1, x2, ..., xn
și costul C. Greutățile luate din fiecare produs se determină prin
metoda Greedy astfel:
- la fiecare parcurgere a ciclului Greedy se selectează produsul Pi
cu cel mai mare preț unitar, care nu a fost deja selectat anterior;
- dacă, prin punerea în rucsac a întregii cantități de produs, de
greutate disponibilă Gi, nu se depășește greutatea
admisă a rucsacului Gmax, atunci în rucsac se pune
toată cantitatea disponibilă (deci xi=Gi);
altfel, se pune în rucsac numai diferența dintre Gmax
si greutatea totală a produselor deja puse anterior.
Calculul se oprește când s-a atins greutatea maximă a rucsacului.
În fișierul Rucsac.java este data
clasa Rucsac, care extinde clasa Greedy.
Pentru produsele necesare (care ar trebui puse în rucsac) se
utilizează clasa imbricată ProdusNecesar, care conține trei câmpuri:
pretUnitar, greutateDisponibila si cantitate (cantitatea de produs
pusa in rucsac). Pentru a putea fi comparate aceste obiecte, clasa
Obiect necesar implementează interfața Comparable. Metoda int
compareTo(Object ob) compară obiectul propriu cu obiectul ob după
pretul unitar. In consecință, metoda Object selecție()
selectează la fiecare invocare produsull de pret unitar maxim. Metoda boolean
poateFiAdaugat(Collection s, Object x) intoarce true numai dacă
greutatea produsului x, adaugată la suma greutăților din colecția
obiectelor deja selectate s, nu depășește greutatea maximă admisă. În
cazul în care s-a atins greutatea maximă admisă a rucsacului, se pune
variabila booleană gasitSoluția din clasa Greedy la valoarea
true, pentru a se încheia selectarea de noi produse.
|
Fie, de exemplu, graful din figura 1, în care nodurile sunt etichetate cu litere, iar pentru fiecare muchie este specificat costul parcurgerii acesteia.
- Figura 1 -
Selectarea muchiilor care intră în componența arborelui de acoperire
de cost minim se face în ordinea crescătoare a costurilor, după cum
urmează:
- se selectează muchia D-E de cost 0.8, formând astfel primul
arborele nr. 1;
- se selectează muchia A-D de cost 1.2, care are nodul D comun cu
muchia precedentă, astfel că este atașată arborelui nr 1, deja format;
- se selectează muchia G-H de cost 1.4, ale cărei noduri nu fac
parte din arborele 1, astfel că se constituie arborele nr. 2;
- se selectează muchia E-F de cost 1.9, la care nodul E face parte
din arborele 1, iar nodul F este liber; în consecință, muchia E-F se
atașează la arborele 1;
- se selectează muchia E-G de cost 2.1, care are nodul E în
arborele 1, iar nodul G în arborele 2; în consecință, muchia reunește
cei doi arbori în unul singur, fie acesta arborele 1;
- se selectează muchia A-E de cost 2.3, dar nu poate fi
adăugată, deoarece ambele noduri există deja în arborele 1,
astfel că s-ar forma un circuit;
- se selectează muchia B-C de cost 2.7, ale cărei noduri nu sunt
încă cuprinse în arbori; în consecință se formează un arbore nou, fie
acesta arborele 3;
- se selectează muchia B-D de cost 2.9, care are nodul B în
arborele 3 si nodul D în arborele 1, deci această muchie unește cei doi
arbori în unul singur, fie el arborele 1; cu aceasta construirea
arborelui de acoperire de cost minim s-a încheiat, deoarece numarul de
muchii pe care le conține este n-1, unde n este numărul de noduri din
graf.
Încercările de a selecta celelalte muchii (C-D, E-H, D-H, C-H, F-G,
A-F, A-B) eșuează, deoarece toate au ambele noduri în arborele 1, deci
adăugarea lor ar forma circuite.
Arborele de acoperire de cost minim astfel construit este
reprezentat în figura 2.
- Figura 2 -
Din exemplul de mai sus constatăm că, în procesul de
construire a arborelui de acoperire de cost minim prin această metodă,
se creează mai mulți arbori care, treptat, dacă graful este conex, se
unesc într-un singur arbore de acoperire. Pentru fiecare nouă muchie
selectată (de cost minim) există următoarele posibilități: a) nici unul din nodurile de la capetele muchiei nu există în arborii deja creați anterior; în acest caz, se creează un arbore nou, care conține numai această muchie; b) unul din nodurile muchiei există deja într-un arbore creat anterior, iar al doilea nod este liber; în acest caz, muchia se atașează la arborele căruia îi aparține unul din noduri; c) ambele noduri ale muchiei aparțin aceluiași arbeore, dintre cei existenți; în acest caz, adăugarea muchiei ar creea un circuit, deci muchia se elimină; d) cele două noduri ale muchiei se regăsesc în doi arbori diferiți; în acest caz, prin adăugarea noii muchii, cei doi arbori se contopesc în unul singur. Acest nou arbore primește numărul de ordine cel mai mic dintre cei doi, făcându-se în mod corespunzător modificarea câmpului nrArbore la toate muchiile care le aparțin. Dacă graful este conex, arborele de acoperire conține toate cele n noduri ale grafului și n-1 muchii. În consecință, dacă numărul de muchii din arbore a ajuns la valoarea n-1, căutarea se încheie. În fișierul ArbAcopCM.java este
dat un exemplu de clasă în care se construiește prin metoda Greedy
arborele de acoperire de cost minim al unui graf. Clasa ArbAcopCM
extinde clasa Greedy.
Graful dat este reprezentat ca o colecție de muchii. Fiecare muchie este un obiect din clasa imbricată Muchie, care conține drept câmpuri etichetele celor două noduri pe care le unește (sub formă de obiecte din clasa String) și un număr real, care este costul muchiei. S-a introdus, de asemenea, câmpul ajutător nrArbore, care este numărul de ordine al arborelui din care face parte muchia respectivă (inițial toate muchiile au acest câmp la valoarea 0). Muchiile se compară după costul lor. Metoda Object selectie() alege la fiecare invocare, dintre muchiile candidate, muchia de cost minim. Metoda boolean poateFiAdaugat(Collection s, Object x) stabilește în ce situație se găsește muchia selectată și decide dacă se elimină, se creează cu ea un arbore nou, se atașează la unul din arborii existenți sau unește între ei doi arbori existenți. Modul de lucru este specificat în această metodă prin comentarii. In fisierul TestArbAcopCM.java
este dat un exemplu simplu de program de testare a clasei ArbAcopCM.
Metoda main() primește ca argumente în linia de comandă
muchiile grafului sub forma unei succesiuni de trilpete: nod1 nod2
cost unde nod1 și nod2 sunt șiruri de caractere
(etichetele nodurilor) iar cost este un număr real. Astfel,
pentru construirea arborelui de acoperire de cost minim al grafului din
figura 1, se dă următoarea comandă: |
Remarcăm că, dacă graful nu este conex, aplicând algoritmul lui
Kruskal se obțin mai mulți arbori, câte unul pentru fiecare componentă
conexă a grafului.
La fiecare parcurgere a ciclului Greedy din acest algoritm, la arborele deja existent se adaugă un singur nod. În acest scop, dintre muchiile candidate care au unul din noduri în arborele deja creat, iar celalalt nod liber, se alege muchia de cost minim. Dacă graful este conex, algoritmii lui Kruskal și lui Prim dau același rezultat: arborele de cost minim care acoperă toate nodurile grafului. Dacă însă graful nu este conex, algoritmul lui Kruskal generează pădurea care contine câte un arbore de acoperire de cost minim pentru fiecare componentă conexă a grafului, în timp ce algoritmul lui Prim generează numai arborele de acoperire de cost minim al componentei conexe în care se gasește nodul de pornire.
De exemplu, pentru a construi arborele de acoperire de cost minim al
grafului conex din figura 1, pornind de la nodul E, se adaugă
muchiile în ordinea următoare: E-D, D-A, E-F, E-G, G-H, D-B, B-C. Dacă
se pornește din vârful B, ordinea va fi următoarea: B-C, B-D, D,E, D-A,
E-F, E-G, G-H.
Algoritmul Prim poate fi formulat în pseudocod astfel:
Se inițializează graful G și nodul de pornire np. În fișierul ArbAcopPrim.java
este dat un exemplu de clasă care conține o metodă de generare a
arborelui de acoperire de cost minim prin algoritmul lui Prim.
Un program de testare este dat in fișierul TestArbAcopPrim.java. Ca date in linia de comanda se dau nodul de pornire urmat, pentru fiecare muchie, de nodul inițial, nodul final și cost. |
Pentru aplicarea acestui algoritm, se folosesc două structuri de
date auxiliare:
- Arborele S, care conține căile cele mai scurte către noduri;
inițial, acest arbore conține numai nodul sursă, dar el se completează
cu un nou nod la fiecare parcurgere a ciclului Greedy;
- coada de priorități Q, care conține nodurile care nu sunt în S,
dar către care conduc legături de la nodurile din S; la extragerea din
coadă, prioritatea maximă aparține nodului pentru care distanța de la
sursă este cea mai mică.
Inițial, se creează structurile vide S și Q, după care se pune nodul
sursă în Q. fiecărui nod din Q i se atașează ca informație distanța de
la nodul sursă până la nodul dat. Se intră apoi într-un ciclu Greedy. La
fiecare parcurgere a ciclului se extrage din Q nodul de prioritate
maximă (deci cel pentru care distanța de la nodul sursa este minimă) și
se pune în S. Pentru a se putea reconstitui arborele, în structurile S
și Q fiecare element va conține și o referință la tatăl acestuia, deci
va fi reprezentat prin următorul triplet:
(<tata> < nod_curent> <distanță_la_sursă>)
Să considerăm ca exemplu graful din figura 1 și să adoptăm ca
sursă nodul A.
- Inițial, S va fi vid, iar Q va conține numai elementul (null,
A, 0).
- La prima parcurgere a ciclului Greedy, se extrage din Q unicul nod
existent și se pune în S, iar în Q se pun elementele (A, D, 1.2), (A,
E, 2.3), (A, F, 5.1) și (A, B, 7.3).
- La următoarea parcurgere a ciclului Greedy, din Q se extrage nodul
D (pentru care distanța la sursa A este minimă), după care se pun în Q
nodurile legate prin muchii de acesta, cu distanțele de la nodurile
respective la A calculate ca distanța de la D la A plus distanța de la
nodul respectiv la D. Există posibilitatea ca unele din aceste noduri
să există deja în Q, cum sunt B și E, pentru care există deja o distanță
la A calculată anterior, si alta calculată acum pentru calea care trece
prin D. Dintre acestea doua se va alege cea mai mică. Observăm, deci, că
în Q nu trebuie să existe de mai multe ori același nod și nici nu se pun
noduri care există deja în S. Ca urmare, S conține acum elementele
(null, A, 0) și (A, D, 1.2), iar Q conține elementele (D, E, 2.0), (D,
B, 4.1), (D, C, 4.3), (A, F, 5.1) și (D, H, 5.4), în ordinea
crescătoare a priorităților.
- La fiecare dic parcurgerile următoare ale ciclului Greedy se
procedează similar: se extrage din Q nodul cu cea mai mică distanță la
A, iar nodurile adiacente acestuia se pun în Q, calculându-se pentru
fiecare distanța la A actualizată. Iată cum evoluează mulțimile de
noduri din S și Q:
S={ }, Q={(null, A, 0, 0)}
S={(null, A, 0.0)}, Q={(A, D, 1.2), (A, E, 2.3), (A, F, 5.1),
(A, B, 7.3)}
S={(null, A, 0.0), (A, D, 1.2)}, Q={ (D, E, 2.0), (D, B, 4.1),
(D, C, 4.3), (A, F, 5.1), (D, H, 5.4)}
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0)}, Q={ (E, F, 3.9),
(D, B, 4.1), (E, G, 4.1), (D, C, 4.3), (D, H, 5.4) }
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9)}, Q={
(D, B, 4.1), (E, G, 4.1), (D, C, 4.3), (D, H, 5.4) }
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B,
4.1)}, Q={(E, G, 4.1), (D, C, 4.3), (D, H, 5.4) }
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B,
4.1), (E, G, 4.1)}, Q={ (D, C, 4.3), (D, H, 5.4) }
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B,
4.1), (E, G, 4.1), (D, C, 4.3)}, Q={(D, H, 5.4) }
S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B,
4.1), (E, G, 4.1), (D, C, 4.3), (D, H, 5.4)}, Q={ }
Algoritmul se oprește când mulțimea Q devine vidă. Dacă graful este
conex, numărul de parcurgeri ale ciclului Greedy este egal cu n-1,
unde n este numărul de noduri din graf. Arborele de acoperire
astfel obținut cuprinde, deci, toate nodurile grafului. dacă graful nu
este conex, arborele dat de algoritmul Dijkstra acoperă numai
componenta conexă din care face parte nodul sursă.
Arborele astfel obținut este cel din figura 3 și diferă de cel de cost minim din figura 2. În figură s-au reprezentat prin numere negre lungimile muchiilor și prin numere roșii, puse lângă noduri, distanțele de la sursă la nodurile respective. S-a menținut amplasarea nodurilor din figura 3.1, pentru a se putea compara mai ușor.
- Figura 3 -
În fișierul Dijkstra.java este
dat un exemplu de clasă care conține metoda statică public static Collection dijkstra(Collection muchiiGraf, String nodSursa) care primește ca argumente colecția muchiilor grafului și eticheta nodului sursa și întoarce (sub forma unei colecții de arce) arborele de acoperire obținut din graful respectiv aplicând algoritmul lui Dijkstra.
În acest program, graful este considerat neorientat și este reprezentat ca o listă de muchii. Fiecare muchie a grafului este un obiect din clasa imbricată Muchie, ale cărei câmpuri sun etichetele celor două noduri și lungimea muchiei. Este evident că lungimea trebuie să fie un număr real pozitiv. Arborele rezultat este implementat, de asemenea, printr-o listă de arce. Fiecare arc este un obiect din clasa imbricată ArcArbore, ale cărei câmpuri sunt cele două noduri (origine și vârf), lungimea arcului și distanța de la vârful arcului la nodul sursă. Coada conține, de asemenea, obiecte ale clasei ArcArbore. Algoritmul Dijkstra este conținut în metoda dijkstra,
putând fi exprimat în pseudocod astfel:
În implementarea prezentată aici a algoritmului Dijkstra, în Q și în S se pun arce, care conțin fiecare un nod, tatăl acestuia și distanța de la nod la sursă. Relaxarea nodului curent se face prin invocarea metodei Relaxarea se face după un algoritm, care poate fi formulat
astfel:
Distanța de la fiu la sursa se calculează ca distanța de la tată la sursă, plus lungimea muchiei m. Verificarea dacă un nod fiu se găsește în arbore se face prim
metoda Punerea în coada Q a unui nod se face prin metoda Întrucât Q este o coadă de priorități, în care primul element
este cel pentru care distantaLaSursa este minimă, la punerea
în coadă a unui nou element trebuie să se respecte următoarele
condiții:
|