alcp_12_

Algoritmi si Limbaje pentru Calcul Paralel 2008 Laborator nr. 12

Laborator Nr. 12

Drumuri optime n grafuri

1. Problema algebrica a drumurilor Problema algebrica a drumurilor unifica strategiile utilizate n rezolvarea a trei

clase mari de probleme, fiecare dezvoltata independent, cu algoritmi proprii:determinarea nchiderii tranzitive a unei relatii, determinarea drumurilor minime ntr-un graf, rezolvarea sistemelor de ecuatii liniare (metoda Gauss-Jordan).

Algoritmul lui Kucera

Algoritmul lui Kucera, dezvoltat pentru o masina CREW-PRAM, pentru

problema drumurilor minime poate fi considerat de baza.

Algoritmul utilizeaza ca date initiale matricea Dnn a ponderilor muchiilor unui

graf G = (V,E), (V = {1,...,n}, E VV). i,j {1,...,n} : D[i,j] = dij, daca (i,j) E

, daca (i,j) Eunde dij este distanta dintre nodurile i si j (dii = 0).

Rezultatul executiei algoritmului lui Kucera este o matrice Cnn:

C[i,j] = 0, daca i = j min[((i,i1,,ik,j)) || drum in G] { D[i,i1]+D[i1,i2]++D[ik,j]}, daca i j

Pseudocod pentru algoritmul lui Kucerafor all i,j:1 i,j n par do C[i,j] = D[i,j]; repeat log n times

for all i,j,k: 1 i,j,k n par do w[i,k,j] = C[i,k]+C[k,j]; for all i,j: 1 i,j n par do C[i,j] = min{C[i,j],mink{w[i,k,j]; k = 1,...,n}}; end


Complexitatea

Operatia min{C[i,j],mink{w[i,k,j]; k = 1,...,n}} poate fi implemntata prinprocedura sum, ,, fiind n acest caz operatorul de minimizare.

Daca se utilizeaza modelul CREW-PRAM, complexitatea timp a acesteioperatii este O(log n) iar numarul de procesoare utilizate este n/logn.

Rezulta pentru algoritm un timp de executie T(n)=O(log2n) si un necesar deprocesoare de O(n3/logn).

Pe o masina CRCW-PRAM, operatia de minimizare anterior mentionata se

poate efectua n timp constant cu n2 procesoare.

Consecinta este reducerea timpului de executie la O(logn), rezultnd nsa ocrestere a numarului procesoarelor la O(n4).

2. Definirea problemei algebrice a drumurilornlocuind n algoritmul lui Kucera: D cu A (matricea de adiacenta), + cu si

logic, min cu sau logic, se obtine un algoritm pentru problema nchideriitranzitive. Mentionam ca pentru un graf G, problema nchiderii tranzitive consta ndeterminarea unei matrice Cnn:

C[i,j] = 1, daca exista n G un drum de la i la j 0, altfel

Generaliznd, problema algebrica a drumurilor poate fi definita astfel:

Dat fiind un graf ponderat G = (V,E,w), unde w:E H, iar (H,,) formeazaun inel cu unitate, sa se determine matricea Cnn astfel nct

C[i,j] = w(p) [p drum de la i la j] Obs. Daca p = i0i1...ik-1ik atunci w(p) =

1

0

=

=

k

l w[il,il+1].


Implementri sistoliceFoarte numeroase sunt abordarile sistolice ale problemei algebrice a

drumurilor. Remarcabila este implementarea algoritmului lui Kleen pe o retea detip plasa data de Y. Robert si D. Trystram, 1986

Parametrii algoritmului sunt T = 5n-2 si A O(n2).


Reea sistolic pentru drumuri cu aceeai sursReteaua lui Y. Robert si D. Trystram poate modificata si adaptata problemei

drumurilor de cost minim sau maxim de la un nod n la toate celelalte n-1 noduri ale

unui digraf aciclic G = (V,A), V = {1,2,...,n}, E VV. Vom prezenta n continuare o arhitectura sistolica pentru problema drumurilor de

cost maxim de la un nod n la toate celelalte n-1 noduri ale unui digraf aciclic G =(V,A) Am ales varianta drumurilor maxime n perspectiva utilizarii acestora lasortarea topologica. Initial, Cnn este matricea Costnn a costurilor arcelor digrafuluiaciclic G. Cij este costul arcului (i,j).


Algoritmul Warshal-Floyd Algoritmul implementat de reteaua anterioara este derivat din algoritmul Warshal-

Floyd astfel: proc drumuri_maxime(C,n); begin

for k = 1 to n-1 do for j = 1 to n do

for i = k+1 to n do C[i,j] = max{C[i,j],C[i,k]+C[k,j]}

end; Procedura drumuri_maxime transforma elementele matricei C dupa formula:

Ck[i,j] = max{Ck-1[i,j],Ck-1[i,k]+Ck-1[k,j]}unde Ck-1 respectiv Ck definesc starea matricei C inainte si dupa iteratia k. Elementele Cn-1[i,j] vor contine costurile drumurilor maxime de la i la j. n final

doar elementele liniei n a matricei C vor ajunge n starea n-1 deci vor contine valoricorespunzatoare drumurilor maxime.

Exemplu de aplicare a algoritmului de drumuri maxime ntr-un digraf aciclic

alcp_12_

Documents