Extras din curs

Pe parcursul acestui capitol se vor prezenta soluţii matematice şi computaţionale, care au drept scop optimizarea reţelelor de comunicaţii la nivelul structurii topologice, bazate pe teoria grafurilor. Cu această ocazie vor fi elaborate programe de simulare realizate în limbajul de programare DELPHI 5.0, ce vor furniza soluţiile de optimizare ca o frontieră între teorie şi practică. Acest limbaj este foarte răspândit în cadrul programării calculatoarelor, în special în procesul de învăţământ. Între tehnicile de programare şi teoria grafurilor există o strânsă legătură, obţinându-se astfel rezultate deosebit de importante prin intermediul mecanismelor specifice de programare (tehnici deja prezentate în capitolul anterior). De exemplu, pentru aflarea ciclurilor hamiltoiniene se foloseşte metoda backtraking, pentru aflare ciclurilor culeriene folosim tehnica Greedy, pentru aflarea drumurilor optime se poate folosi metoda programării dinamice.

Fiecare metodă de optimizare este prezentată folosind setul următoarelor etape:

- prezentarea problemei de optimizare = conţine principalele aspecte care intervin în rezolvarea algoritmului respectiv şi pregăteşte noţiunile necesare parcurgerii pas cu pas a algoritmului;

- prezentarea algoritmului = în această secţiune sunt parcurşi paşii din care este format algoritmul (trataţi din punct de vedere teoretic);

- prezentarea unui exemplu de funcţionare a algoritmului, ţinând cont de fiecare pas în parte (trataţi din punct de vedre numeric);

- observaţii cu privire la problemele specifice fiecărui algoritm;

- implementarea algoritmului = sunt prezentate principalele probleme care intervin în implementarea computaţională a algoritmului şi variabilele folosite în acest scop;

Analiza şi optimizarea reţelelor de comunicaţii la nivel topologic, atât în faza de proiectare cât şi în cea de exploatare a ei, se poate face după următoarele criterii:

- distanţă:

- flux informaţional;

- probabilitate de realizare a legăturii;

- întârziere;

- fiabilitate, etc.

În cele ce urmează vor fi prezentate soluţii care realizează optimizări la nivelul structurii topologice după criterii de distanţă şi flux informaţional.

5.1. Algoritmi simplii pentru grafuri

(arbori minimali)

Un arbore de interes special este arborele minimal. Determinarea acestui tip de arbore are un rol important în cadrul optimizării reţelelor de comunicaţii la nivel de topologie, atât în faza de proiectare, cât şi în cadrul celei de exploatare. Arborele minimal, ales din multitudinea de arbori corespunzători grafului, respectă următoarele condiţii:

- permite realizarea legăturii între oricare două noduri ale reţelei;

- valoarea atributului, corespunzătoare reuniunii de arce, care formează arborele este optimă, adică pentru atributul de distanţă (cost) valoarea acestuia este minimă, iar pentru cel de flux informaţional este maximă.

Pentru a construi acest arbore se poate folosi o procedură iterativă, începând cu cel mai scurt arc şi extinzând în mod gradual la celelalte arce din reţea. Există două moduri distincte de realizare a acestei iteraţii, acestea fiind prezentate în continuare.

5.1.1. Algoritmul lui J.B. KRUSKAL şi

cel al lui R.C. PRIM

Prima metodă, numită şi algoritmul lui J.B. Kruskal, permite construirea arborelui parţial de cost minim muchie cu muchie astfel: toate arcele sunt aranjate după lungime şi sunt adăugate la setul de arce dacă nu formează un ciclu cu acele arce care deja există în set; această metodă a fost elaborată de J.B. Kruskal şi poate conduce la câţiva subarbori care cresc simultan. Graful obţinut are n vârfuri, este conex, nu are cicluri şi deci este arbore. Evident, trebuie să demonstrăm că arborele construit este de cost minim.

Pentru a doua metodă, numită şi algoritmul lui R.C. Prim, metoda Greedy permite construirea arborelui parţial de cost minim astfel: arborele creşte constant, de la un arc iniţial, iar la fiecare pas al algoritmului arcul care este adăugat este cel mai scurt arc rămas, ce are un vârf în arbore. Deci, pentru a selecta un arc, acele arce care nu fac parte din arborele parţial sunt scanate şi împărţite în două seturi: cele care au un nod (şi numai unul) în arbore şi cele care nu au deloc, sau au două.

Diferenţa dintre cei doi algoritmi constă în faptul că algoritmul lui Kruskal poate crea câţiva arbori mici până când arborele este complet, pe când algoritmul lui Prim dezvoltă un arbore parţial pentru a deveni arborele dorit.