A. Considerații teoretice

O clasă largă de probleme presupune aflarea unei soluții optime. Într-o abordare directă se pot genera toate soluțiile posibile și pe parcursul procesului de generare să fie reținută soluția optimă întâlnită până în acel moment. Dacă însă spațiul soluțiilor este foarte mare, acest mod de căutare a optimului nu este viabil, timpul de execuție fiind exagerat de lung. În astfel de cazuri alegerea unei strategii potrivite are o importanță deosebită, atât în ce privește durata de rezolvare a problemei, cât și în ce privește calitatea rezultatului care se obține.

Strategia Greedy realizează construirea unei soluții prin parcurgerea, în etape, a unor soluții parțiale. La fiecare pas se alege o soluție parțială, pe baza căreia se va face căutarea în pasul următor. Dacă la fiecare pas se alege o soluție optimă pentru pasul respectiv, există șanse mari de obținere a unei soluții optime în final.

Un exemplu cu caracter general al aflării soluției optime este următorul: Se cere să se găsească o submulțime, selectată dintr-o mulțime dată, astfel încât elementele submulțimii să îndeplinească unul sau mai multe criterii optimale. Rezolvarea directă se poate face generând toate submulțimile mulțimii date și verificând pentru fiecare dacă soluția reprezintă un optim. Metoda care folosește un algoritm Greedy va selecta într-o singură trecere elementele submulțimii, alegând mereu acel element care optimizează submulțimea curentă.

Se poate întâmpla ca soluția găsită (mai ales dacă există mai multe criterii contradictorii de optim) să nu fie soluția optimă, dar, în mod sigur, ea va fi apropiată de aceasta. Există totuși situații și mai nefavorabile, când strategia Greedy nu ne conduce la nici o soluție, deși aceasta există.

În continuare se va prezenta un algoritm specific pentru probleme modelate matematic prin grafuri.


B. Exemple

Se consideră un graf format din noduri denumite A,B,C, etc. și arce de dimensiune dată. Problema este găsirea unui subgraf aciclic în care orice pereche de noduri X, Y are un drum care se cunoaște și suma tuturor arcelor este minimă. Acest graf se numeste "arbore parțial de cost minim" (minimum spanning tree).

Reprezentarea grafului se poate face în felul următor: o matrice bidimensională pătratică simetrică care va avea ca indici pe linii și coloane nodurile grafului. Elementele matricei vor fi dimensiunile arcelor. Dacă nu există arc între două noduri se va nota cu MaxInt (infinit).

Exemplu:

va deveni:

Matricea distanțelor
A B C D E
A 0 2 5 MaxInt Maxint
B 2 0 MaxInt 4 Maxint
C 5 MaxInt 0 3 4
D MaxInt 4 3 0 5
E MaxInt MaxInt 4 5 0

Diagonala principală este formată din zerouri, considerând că drumurile interne din noduri sunt nule. Se observă că fiecare arc apare de două ori. Semnificația acestui fapt este că arcele nu sunt orientate, fiecare reprezentând drumul de la X la Y, dar și de la Y la X.

Algoritmul propus este următorul (algoritmul Prim) :

* Rădăcina arborelui generat este nodul care etichetează
  prima linie a matricei de costuri
* Se marchează prima linie a matricei
* Se șterge prima coloană a matricei
while * mai sunt elemente neșterse do
begin
  * Se determină coordonatele (linia I și coloana J) ale
    elementului minim dintre toate elementele neșterse
    de pe liniile marcate
  * Se adaugă, la arborele generat, nodul J
  * Se leagă nodul J de nodul I
  * Se marchează linia J din matrice
  * Se șterge coloana J din matrice
end;

O ilustrare a acestui algoritm se poate urmări în următorul applet :

Programul de navigare nu suportă appleturi Java.


C. Teme

  1. Se consideră n (n ≤ 20) orașe. Acestea sunt legate prin drumuri de lungime cunoscută. Să se găsească rețeaua de drumuri de lungime minimă, astfel încât toate orașele să fie legate direct sau indirect între ele.
    Datele de intrare se dau într-un fișier text orase.dat, care are următoarea structură :

    <n>       {numar de orașe}
    <oraș 1>   {numele orașelor}
    <oraș 2>
    ...
    <oraș n>
    <oraș i>-<oraș j>=dij   {lungimea drumurilor}
    ...
    <oraș k>-<oraș l>=dkl
    

    Să se afișeze toate drumurile care compun rețeaua minimă de drumuri și suma totală a lungimii drumurilor sub forma:

    <oraș p>-<oraș q>=dpq 
    ...
    <oraș r>-<oraș s>=drs
    Total=<suma totală>
    
  2. Sugestii :

  3. Se dau n șiruri S1, S2, S3, ..., Sn de lungimi l1, l2, l3, ..., ln. În cadrul fiecărui șir elementele sunt ordonate crescător. Să se construiască un șir S cu l1+l2+l3+...+ln elemente, ordonate de asemenea crescător, conținând elementele cumulate ale celor n șiruri inițiale. Se cere ca programul realizat să fie optim din punct de vedere al timpului necesar pentru construirea șirului S.

    Indicații :

    • se va folosi o procedură pentru interclasarea a două șiruri ordonate, transmise ca parametrii;

    • pentru optimizare se vor interclasa, întotdeauna, cele mai scurte două șiruri;

    • pentru testare, programul va fi prevăzut și cu posibilitatea de a genera aleator șirurile inițiale și de a le ordona, înainte de începerea prelucrării propriuzise.

  4. * Se citesc informații despre n baieți și n fete. Acestea conțin:

    • nume;

    • culoare preferată (roșu, portocaliu, galben, verde, albastru, indigo, violet);

    • muzica preferată (operă, simfonică, pop, rock, country);

    • temperament (flegmatic, melancolic, sanguin, coleric).

    Să se scrie un program care stabilește perechile pentru un concurs de dans, astfel încat baiatul și fata care compun o pereche să aibă aceleași preferințe la muzică și culori și temperamente diferite. Dacă nu se poate, atunci să fie respectate numai două criterii sau cel puțin unul.