Metoda Greedy

Metoda Greedy (engleză: greedy = lacom) este o metodă generală de elaborare a algoritmilor, care poate fi aplicată unei varietăți mari de probleme de optimizare discretă. În cele mai multe cazuri, aplicarea metodei Greedy nu conduce la obținerea optimului global (adică a celei mai bune soluții dintre toate cele posibile) ci a unei soluții suboptimale. Totuși, metoda este de multe ori preferată, datorită simplității ei.
 
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. 
 
import java.util.*;

public abstract class Greedy {

  Collection c; // colectia candidatilor
  boolean gasitSolutia;

  public Greedy(Collection a) {
    c=new ArrayList();
    Iterator iter=a.iterator();
    while(iter.hasNext()) c.add(iter.next());
    gasitSolutia=false;
  }

  public Collection greedy() {
    Collection s=new ArrayList();
    while (!gasitSolutia && !c.isEmpty()) {
      Object x=selectie();
      if(poateFiAdaugat(s,x)) s.add(x);
      c.remove(x);
    }
    return s;
  }

  public abstract Object selectie();

  public abstract boolean poateFiAdaugat(Collection s, Object x); 
}

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:
     public abstract Object selecție() - selectează din colecția candidaților c pe cel mai bun candidat;
     public abstract boolean poateFiAdaugat(Collection s, Object x) - verifică dacă obiectul selectat x poate fi adăugat la colecția s și întoarcwe true în caz afirmativ, sau false în caz contrar. În ambele cazuri, obiectul x este eliminat din colectia c.

Cele două metode auxiliare trebuie definite pentru fiecare problemă rezolvată prin metoda Greedy.

Exemple de algoritmi obtinuți prin metoda Greedy

1. Sortarea prin selecție

Algoritmul de sortare prin metoda selecției, prezentat deja anterior, este un alt exemplu de aplicare a metodei Greedy. Amintim că, în acest algoritm, la fiecare parcurgere a ciclului de sortare se selectează cel mai mic element dintre cele încă ne sortate și se adaugă în coada listei elementelor deja sortate.
 
Î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ă. 
 
import java.util.*;

public class SortSelectie extends Greedy {

  public SortSelectie(List listaData) {
    super(listaData);
  }

  public Object selectie() {
    return Collections.min(c);
  }

  public boolean poateFiAdaugat(Collection s, Object x) {
    return true;
  }

  public static void main(String args[]) {
    if(args.length<2) {
      System.out.println("Dati ca parametri in linia de comanda cel putin doua cuvinte");
      System.exit(0);
    }
    ArrayList lst=new ArrayList();
    for(int i=0; i<args.length; i++) lst.add(args[i]);
    SortSelectie sortare=new SortSelectie(lst);
    Collection lst1=sortare.greedy();
    System.out.println(lst1);
  }
}

Î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ă.

2. Problema rucsacului (varianta continuă)

Într-un depozit există mai multe produse P1, P2, ..., Pn. Pentru fiecare produs Pi se cunosc greutatea disponibilă Gi și prețul pe unitatea de greutate pi. Considerăm că este necesar să se pună într-un rucsac mai multe produse, astfel încât să nu se depășească greutatea maximă admisă a rucsacului Gmax, iar costul total al produselor puse în rucsac să fie maxim. Se permite ca din fiecare produs să se pună în rucsac o cantitate oarecare (număr real), care să nu depășească greutatea disponibilă în depozit.
Observație: aceasta este "varianta continuă" a problemei rucsacului, pentru care se poate obține prin metoda Greedy soluția optimă. Există și o varianta discretă a acestei probleme, în care produsele nu pot fi divizate, deci din fiecare produs trebuie pus un număr întreg de bucăți. În acest al doilea caz, metoda Greedy nu mai garantează soluția optimă, ci una suboptimală. Pentru obținerea soluției optime în versiunea discretă a problemei, sunt necesare alte metode de rezolvare.

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. 
 
/* Se rezolva problema rucsacului prin metoda Greedy
*/

import java.util.*;

public class Rucsac extends Greedy {
  double greutateMax, greutateContinut;

  Rucsac(Collection necesar, double greutateMaxima) {
    super(new ArrayList(necesar));
    greutateMax=greutateMaxima;
  }

  public Object selectie() {
    return Collections.max(c);
  }

  /* Un nou obiect poate fi pus in rucsac numai daca prin aceasta 
     nu se depaseste greutatea maxima a rucsacului
  */
  public boolean poateFiAdaugat(Collection s, Object x) {
    ProdusNecesar prn=(ProdusNecesar)x;
    if((greutateContinut+prn.greutateDisponibila)<=greutateMax) {
      /* se pune in rucsac intreaga cantitate disponibila din produsul curent */
      prn.cantitate=prn.greutateDisponibila;
      greutateContinut+=prn.cantitate;
    }
    else {
      /* se pune in rucsac din produsul curent numai diferenta dintre
         greutatea maxima admisa si greutatea produselor puse anterior 
         si se incheie punerea de produse in rucsac
      */
      prn.cantitate=greutateMax-greutateContinut;
      greutateContinut+=greutateMax;
      gasitSolutia=true;
    }
    return true;
  }

  /* Clasa imbricata a produselor necesare  */
  public static class ProdusNecesar implements Comparable {
    double pretUnitar;
    double greutateDisponibila;
    double cantitate;

    /* Produsele necesare se compara dupa pretul pe unitatea de greutate */
    public int compareTo(Object ob) {
      double diferentaPret=pretUnitar-((ProdusNecesar)ob).pretUnitar;
      if(diferentaPret<0) return -1;
      if(diferentaPret>0) return 1;
      return 0;
    }

    public String toString() {
      return "(pr="+pretUnitar+" grd="+greutateDisponibila+" cant="+cantitate+")";
    }
  }
}

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.
 
In fisierul TestRucsac.java se da un exemplu de program simplu de testare a clasei Rucsac Pentru executarea lui, în linia de comandă se dau ca parametri greutatea maximă a rucsacului, urmată de prioritatea și greutatea fiecărui obiect dorit. De exemplu, dacă se dă comanda
   java TestRucsac 12.0 1.2 2.6 0.8 0.37 3.5 2.66 4.21 8.25 2.3 4.12
înseamnă că greutatea maximă a rucsacului este 12.0, iar obiectele necesare sunt (pe perechi pretUnitar   greutateDisponibila) următoarele: (1.2 2.6) (0.8 0.37) (3.5 2.66) (4.21 8.25) (2.3 4.12). Ca rezultat al executării aplicației se obține următorul conținut al rucsacului: (4.21 8.25) (3.5 2.66) (2.3 1.09), greutatea totală a obiectelor selectate fiind 12.0, iar costul acestora fiind 46.5495 (Nu încercați să ghiciți în ce valută s-au exprimat prețurile). Se observă că s-au pus în rucsac numai trei produse. Dintre acestea, la primele două s-a pus întreaga cantitate disponibilă, iar la ultimul numai cantitatea care a mai încăput în rucsac după punerea primelor două.

3. Arborele de acoperire de cost minim

Se dă un graf neorientat, în care fiecărei muchii i se asociază un cost al parcurgerii acesteia. Se numește arbore de acoperire de cost minim acel arbore de acoperire, pentru care suma costurilor laturilor este minimă. Construirea arborelui de acoperire de cost minim se poate face prin metoda Greedy.
 

3.1. Obținerea arborelui de acoperire de cost minim prin algoritmul lui Kruskal

Algoritmul lui Kruskal selectează prin metoda Greedy muchiile grafului, în ordinea strict crescătoare a costului lor. Sunt, desigur,  incluse în arborele de acoperire numai acele muchii, a căror adăugare la arbore nu produce formarea unor circuite.

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. 
 
/* Construieste arborele de acoperire de cost minim al unui graf prin metoda Greedy.
   Graful este dat ca o lista de muchii, pentru fiecare muchie fiind indicat
   si costul parcurgerii  ei.
*/ 

import java.util.*;

class ArbAcopCM extends Greedy {
  ArrayList graf=new ArrayList();
  int numarArbori, numarMuchii, numarNoduriGraf;
  Set multimeNoduri; 

  public ArbAcopCM(List muchiiGraf) {
    super(muchiiGraf);
    numarArbori=numarMuchii=0;
    /* Se construieste multimea nodurilor grafului, pentru a putea determina
       numarul de noduri 
    */
    Muchie m;
    Iterator iter=muchiiGraf.iterator();
    multimeNoduri=new HashSet();
    while(iter.hasNext()) {
      m=(Muchie)iter.next();
      multimeNoduri.add(m.nod1);
      multimeNoduri.add(m.nod2);
    }
    numarNoduriGraf=multimeNoduri.size();
    multimeNoduri=null; // multimea nodurilor nu mai este necesara
  }

  public Object selectie() {
    return Collections.min(c);
  }

  public boolean poateFiAdaugat(Collection s, Object x) {
    Muchie m=(Muchie)x;
    int arb1=0, arb2=0;
    Iterator iter=s.iterator();
    // se cauta la ce arbori apartin m.nod1 si m.nod2
    Muchie mc;
    while(iter.hasNext()) {
      mc=(Muchie)iter.next();
      if(m.nod1.equals(mc.nod1) || m.nod1.equals(mc.nod2)) arb1=mc.nrArbore;
      if(m.nod2.equals(mc.nod1) || m.nod2.equals(mc.nod2)) arb2=mc.nrArbore;
    }

    /* Daca ambele noduri ale muchiei apartin aceluiasi arbore, nu se poate
       adauga, deoarece formeaza un circuit
    */
    if(arb1==arb2 && arb1!=0) return false;
    /* Muchia selectata se poate adauga la arbore, dar trebuie stabilit 
       in ce mod
    */

    if(arb1==0 && arb2==0) { // se creeaza un nou arbore
      numarArbori++;
      m.nrArbore=numarArbori;
    }
    else if(arb1==0) { // se ataseaza cu nodul nod2 la arb2
      m.nrArbore=arb2;
    }
    else if(arb2==0) { // se ataseaza cu nodul nod1 la arb1
      m.nrArbore=arb1;
    }
    else {
      /* Fiecare nod al muchiei x apartine altui arbore. Se unesc cei doi arbori,
         dandu-le cel mai mic din cele doua numere
      */
      int nrNou= arb1<arb2?arb1:arb2;
      m.nrArbore=nrNou;
      iter=s.iterator();
      while(iter.hasNext()) { // se face renumerotarea arborilor
        mc=(Muchie)iter.next();
        if((mc.nrArbore==arb1 || mc.nrArbore==arb2)&&mc.nrArbore!=nrNou)
           mc.nrArbore=nrNou;
      }
    }
    /* In toate aceste cazuri s-a mai adaugat o muchie */
    numarMuchii++;
    if(numarMuchii>=(numarNoduriGraf-1)) gasitSolutia=true;
    return true;
  }

  /* Clasa imbricata a muchiilor grafului */
  static class Muchie implements Comparable {
    String nod1, nod2;
    double cost;
    int nrArbore;

    public Muchie(String nod1, String nod2, double cost) {
      this.nod1=nod1;
      this.nod2=nod2;
      this.cost=cost;
      nrArbore=0;
    }

    public String toString() {
      return "("+nod1+"-"+nod2+": cost="+cost+")";
    }

    public int compareTo(Object ob) {
      double dif=cost-((Muchie)ob).cost;
      if (dif<0) return -1;
      if (dif>0) return 1;
      return 0;
    }
  }
}

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ă:
    java ArbAcopCM A B 7.3 A D 1.2 A E 2.3 A F 5.1 B C 2.7 B D 2.9 C D 3.1 C H 4.6 D E 0.8 D H 4.2 E F 1.9 E G 2.1 E H 3.9 F G 4.7 G H 1.4
Muchiile pot fi introduse, desigur, în orice ordine.

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.
 

3.2. Obținerea arborelui de acoperire de cost minim prin algoritmul lui Prim

Spre deosebire de algoritmul lui Kruskal, care construieste o "pădure" (care se poate contopi pe parcurs într-un singur arbore), algoritmul lui Prim pornește de la un nod dat al grafului și construiește un singur arbore, având acest nod ca rădăcină.

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.
  Se inițializează arborele de acoperire T, care conține inițial numai nodul np.
  cât timp((numărul de noduri din T este mai mic decât cel din G) și (există în G cel puțin o muchie m care are un nod în T)) {
     se extrage din G muchia de cost minim m care are un nod în T;
     dacă (ambele noduri ale muchiei m sunt în T)
        atunci muchia m se elimină din G
        altfel muchia m se adaugă la T
    }

Î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.
 
import java.util.*;

public class ArbAcopPrim {

  Collection graf;
  Set multimeNoduri=new HashSet();
  int numarNoduri;

  public ArbAcopPrim(Collection muchiiGraf) {
    graf=muchiiGraf;
  }

  public Collection arbore(String nodPornire) {
    /* Se construieste o copie a grafului dat (ca o multime de noduri si o
       colectie de muchii)
    */
    Collection candidati=new ArrayList();
    Iterator iter=graf.iterator();
    Muchie m;
    while(iter.hasNext()) {
      m=(Muchie)iter.next();
      candidati.add(m);
      multimeNoduri.add(m.nod1);
      multimeNoduri.add(m.nod2);
    }
    numarNoduri=multimeNoduri.size();
    multimeNoduri=null; // nu mai este necesara
    /* Se initializeaza arborele de acoperire (ca o colectie de muchii) si multimea
       nodurilor arborelui
    */
    Collection arbAcop=new ArrayList();
    Set noduriArbore=new HashSet();
    noduriArbore.add(nodPornire);
    /* Se genereaza arborele de acoperire de cost minim prin algoritmul Prim
    */
    boolean existaCandidati=true, contineNod1, contineNod2;
    while(noduriArbore.size()<numarNoduri&&existaCandidati) {
      /* Se cauta muchia de cost minim care are un nod in arbore. Totodata, 
         se elimina muchiile care au ambele noduri in arbore
      */
      iter=candidati.iterator(); // se itereaza muchiile candidate
      Muchie candidatSelectat=null;
      while (iter.hasNext()) {
        m=(Muchie)iter.next();
        contineNod1=noduriArbore.contains(m.nod1);
        contineNod2=noduriArbore.contains(m.nod2);
        if(contineNod1&&contineNod2) iter.remove();// se elimina muchiia curenta
        else if(contineNod1 || contineNod2) {
          if(candidatSelectat==null || candidatSelectat.compareTo(m)>0) 
            candidatSelectat=m;
        }
      }

      if(candidatSelectat==null) existaCandidati=false; // nu mai exista candidati
      else { // muchia de cost minim se pune in arbore
        arbAcop.add(candidatSelectat);
        if(noduriArbore.contains(candidatSelectat.nod1))
          noduriArbore.add(candidatSelectat.nod2);
        else noduriArbore.add(candidatSelectat.nod1);
      } 
    } 
    return arbAcop;
  }

  static class Muchie implements Comparable {
    String nod1, nod2;
    double cost;

    public Muchie(String nod1, String nod2, double cost) {
      this.nod1=nod1;
      this.nod2=nod2;
      this.cost=cost;
    }

    public String toString() {
      return "("+nod1+"-"+nod2+": cost="+cost+")";
    }

    public int compareTo(Object ob) {
      double dif=cost-((Muchie)ob).cost;
      if (dif<0) return -1;
      if (dif>0) return 1;
      return 0;
    }
  }

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.

4. Algoritmul lui Dijkstra pentru aflarea celor mai scurte căi de la un nod dat la toate celelalte noduri ale grafului

Algoritmul lui Dijkstra permite să obținem cele mai scurte căi de la un nod initial dat, către toate celelalte noduri ale unui graf. Se creează astfel un arbore de acoperire, care are ca rădăcină nodul inițial dat (numit și sursă), iar fiecare ramură reprezintă cea mai scurtă cale de la sursă la toate nodurile pe care le conține. Acest arbore, în general, diferă de arborele de cost minim.

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.
 
import java.util.*;

public class Dijkstra {
  private static LinkedList graf, arbore, coada;

  public static Collection dijkstra(Collection muchiiGraf, String nodSursa) {
    /* initializari */
    graf=new LinkedList(muchiiGraf);
    arbore=new LinkedList();
    coada=new LinkedList();
    coada.add(new NodArbore(null, nodSursa, 0));

    /* Incepe bucla Greedy */
    NodArbore nodExtras;
    while(!coada.isEmpty()) {
      nodExtras=(NodArbore)coada.removeFirst();
      arbore.addLast(nodExtras);
      relaxeaza(nodExtras);
    } // sfarsit bucla Greedy

    return arbore;
  }

  private static void relaxeaza(NodArbore nodExtras) {
    /* Se extrag din graf muchiile care au la unul din capete nodul final din nodExtras.
       Acest nod devine tata, iar celalalt nod al muchiei grafului devine fiu
    */
    Muchie muchieCurenta;
    String tata, fiu;
    tata=nodExtras.nodCurent;
    ListIterator iter=graf.listIterator();
    while(iter.hasNext()) {
      muchieCurenta=(Muchie)iter.next();
      fiu=null;
      if(muchieCurenta.nod1.equals(tata)) fiu=muchieCurenta.nod2;
      else if(muchieCurenta.nod2.equals(tata)) fiu=muchieCurenta.nod1;
      if(fiu!=null) { // muchia curenta este adiacenta la "tata"
        iter.remove(); // se  elimina muchia curenta din graf
        if(!esteInArbore(fiu)) puneInCoada(new NodArbore(tata, fiu, 
                     nodExtras.distantaSursa+muchieCurenta.lungime));
      } // sfarsit if pentru muchii adiacente la tata
    } // sfarsit extragere muchii din graf
  }

  private static boolean esteInArbore(String fiu) {
    ListIterator iter=arbore.listIterator();
    boolean gasit=false;
    while(!gasit && iter.hasNext())
      if(((NodArbore)iter.next()).nodCurent.equals(fiu)) gasit=true;
    return gasit;
  }

  private static void puneInCoada(NodArbore nodAdaugat) {
    /* Se cauta in coada nodAdaugat */
    ListIterator iter=coada.listIterator();
    NodArbore arcCoada=null;
    boolean gasit=false, trebuieAdaugat=true;
    while(!gasit && iter.hasNext()) {
      arcCoada=(NodArbore)iter.next();
      if(arcCoada.nodCurent.equals(nodAdaugat.nodCurent)) {
        gasit=true;
        if(nodAdaugat.distantaSursa<arcCoada.distantaSursa)
          iter.remove(); // se scoate nodul vechi si se adauga cel nou
        else trebuieAdaugat=false;
      } // sfarsit if
    } // Sfarsit while cautare in coada
    /* daca este necesar, se adauga nodul nou in coada, pe pozitia corespunzatoare
       distantei sale la sursa
    */
    if(trebuieAdaugat) {
      if(coada.isEmpty()) coada.add(nodAdaugat);
      else {
        /* Se cauta in coada pozitia pe care elementul trebuie inserat */
        int indice=-1;
        iter=coada.listIterator();
        gasit=false;
        while(!gasit && iter.hasNext()) {
          indice++;
          arcCoada=(NodArbore)iter.next();
          if(arcCoada.distantaSursa>nodAdaugat.distantaSursa) gasit=true;
        }  // Sfarsit while cautare pozitie pentru inserare
        /* Se face inserarea noului element */
        if(!gasit) coada.addLast(nodAdaugat);
        else coada.add(indice, nodAdaugat);
      } // Sfarsit else
    } // sfarsit if(trebuieAdaugat)
  } 

  static class Muchie {
    String nod1, nod2;
    double lungime;

    public Muchie(String nod1, String nod2, double lungime) {
      this.nod1=nod1;
      this.nod2=nod2;
      this.lungime=lungime;
    }

    public String toString() {
      return "("+nod1+"-"+nod2+": "+lungime+")";
    }
  }

  static class NodArbore {
    String tata, nodCurent;
    double distantaSursa;

    NodArbore(String tata, String nodCurent, double distantaSursa) {
      this.tata=tata;
      this.nodCurent=nodCurent;
      this.distantaSursa=distantaSursa;
    }

    public String toString() {
      return "("+tata+" - "+nodCurent+": "+distantaSursa+")";
    }
  }
}

Î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:
 
  Se introduc graful G și nodul sursa s;
   Se creează arborele S și coada de priorități Q, inițial vide;
   Se pune în Q nodul sursă s;
   cât timp Q nu este vidă {
      se extrage din Q nodul n și se pune în S;
      se relaxează nodul n, punând în Q nodurile adiacente acestuia, care nu sunt deja în S;
   }

 Î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
  private static void relaxeaza(NodArbore nodExtras)

Relaxarea se face după un algoritm, care poate fi formulat astfel:
 
 pentru fiecare muchie m a grafului {
   dacă unul din nodurile muchiei m, fie acesta n1 , este nodExtras
      atunci { // muchia este adiacentă la nodExtras {
        se elimină din graf muchia m
         nodul n1se consideră nod tată
         celălalt nod al muchiei m se consideră nod fiu
         dacă nodul fiunu este în arborele S
           atunci se pune în coada Q obiectul (tata, fiu, distantaLaSursa)
      } // sfârșit atunci
 } 

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 
    private static boolean esteInArbore(String fiu)

Punerea în coada Q a unui nod se face prin metoda
    private static void puneInCoada(NodArbore nodAdaugat)

Î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:
    - același nod fiu nu poate să apară în coadă de două ori;
    - coada trebuie să fie tot timpul ordonată crescător după distantaLaSursa
Pentru a se respecta prima condiție, în prima etapă se parcurge coada Q și se caută un element care conține ca fiu nodul nou adăugat. Dacă un astfel de element există, se compară distantaLaSursa a acestuia, cu cea a nodului nou, iar dintre ele se alege cel pentru care distantaLaSursa este mai mică. Dacă ea este mai mică la elementul existent în Q, acest element este păstrat în Q și nu se mai adaugă nodul nou. Dacă însă distantaLaSursa a elementului nou este mai mică decât a omologului său existent în Q, sau dacă acesta nu are un omolog în Q, se face înserarea noului nod pe poziția corespunzîtoare distanței sale la sursă.

 



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați