~ info project ~

Mai 6, 2010

Matricea drumurilor.

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 2:35 pm
Tags: , , ,

Este o matrice d cu n linii şi n coloane, în care fiecare element d[i,j] este :

–         1, dacă există drum de la nodul i la nodul j în graf;

–         0, în caz contrar.

Algoritmul Roy-Warshall de determinare a matricei drumurilor

Matricea drumurilor se obţine aplicând matricei de adiacenţă transformări succesive. Vom spune că există drum de la nodul i la nodul j, dacă găsim un nod k (diferit de i, j) cu proprietatea că există drum de la i la k şi drum de la j la k. Astfel:

  • un element a[i, j] care este 0, devine 1, dacă există un nod k astfel încât a[i, k]=1 şi a[k, j]=1. Pentru a găsi arcele nodului k, trebuie parcurse pe rând în varianta k toate nodurile 1, 2, …, n.

for k:=1 to n do

for i:=to n do       {i≠k}

for j:=1 to n do   {j≠k}

if (a[i, j]=0) and (i<>k) and (j<>k) then

a[i, j]:=a[i,k]*a[k, j];

Atribuirea a[i, j]:=a[i,k]*a[k, j] este o scriere elegantă a regulii de mai sus:

în cazul în care unul din elementele a[i,k], a[k, j] este 0, a[i, j] va rămâne 0;

dacă a[i, k]=1 şi a [k, j]=1, atunci a[i, j] devine 1.

Un CD valoros

Într-un grup sunt n elevi, băieţi şi fete, pe care-i numerotăm 1, 2, … , n. Fiecare elev cunoaşte o parte dintre ceilalţi elevi. Relaţia de cunoştinţă nu este neapărat reciprocă (dacă x îl cunoaşte pe y, asta nu înseamnă că şi y trebuie să îl  cunoască pe x). Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toţi membri grupului vor să-l aibă fie şi pentru scurt timp, pentru a şi-l copia pe calculatorul propriu. CD—ul circulă printre membrii grupului în felul următor: fiecare elev după ce l-a primit de la altcineva îl dă mai departe, dar numai unui elev pe care îl cunoaşte, pentru că nu doreşte să ajungă în mâna unor persoane în care nu poate avea încredere. Determinaţi o modalitate  (dacă există) prin care CD-ul să circule exact o singură dată pe la fiecare elev, transmiterea lui făcându-se numai către o cunoştinţă, iar în final CD-ul să ajungă din nou la proprietarul său.

Interpretarea datelor

Relaţiile de cunoştinţă din cadrul grupului pot fi reţinute într-o matrice a cu n linii şi n coloane, în fiecare element a[i, j] este: 1 dacă elevul i îl cunoaşte pe elevul j, respectiv 0 în caz contrar. Cu datele problemei putem construi un graf în care nodurile sunt elevii 1, 2, 3,…, n, iar arcele sunt relaţiile de cunoştinţă din grup. Astfel, va exista arc de la nodul x la nodul y dacă elevul x în cunoaşte pe elevul y. Întrucât în enunţ se precizează că relaţiile de cunoştinţă nu sunt neapărat reciproce („x cunoaşte pe y” nu implică „y cunoaşte pe x”), rezultă că avem de-a face cu un graf orientat. Matricea a definită mai înainte este tocmai matricea de adiacenţă a grafului.

„Traseul” pe care îl parcurge CD-ul pleacă dintr-un nod (proprietarul său), trecând prin fiecare nod (pe la fiecare elev) o singură dată. Transmiterea se face numai către o cunoştinţă. Astfel, de la elevul x va ajunge la elevul y numai dacă există arc (cunoştinţă) de la x la y. În final, traseul se încheie în nodul de unde a plecat (CD-ul se întoarce la proprietarul iniţial). Un traseu care respectă condiţiile de mai sus nu este altceva decât un circuit elementar care trece prin toate nodurile grafului: drum deoarece poate trece de la un nod la altul numai printr-un arc, elementar deoarece nu trece de două ori prin acelaşi nod, şi în sfârşit circuit pentru că revine în nodul de plecare.

Rezolvare

Folosim metoda backtracking. Fiecare astfel de circuit elementar care trece prin toate nodurile grafului, va fi o soluţie memorată în vectorul stivă st. Aşadar elementele vectorului st sunt noduri ale grafului.

O soluţie (st[1], st[2], …, st[p] ) este finală dacă

– conţine n nivele, adică p=n (au fost „puşi pe stivă” toţi cei n elevi, adică toate cele n noduri)

st[n]=x (pentru a fi ciclu trebui să revină în nodul de plecare, adică „elevul de pe ultimul nivel”, st[n], trebuie să fie proprietarul memorat iniţial în x).

Procedura {citire_matrice;} citeşte matricea de adiacenţă (relaţiile de cunoştinţă). În două cicluri for, cu i, j=1, 2, …, n, se citesc toate elementele a[i, j]. Această procedură a fost prezentată ca aplicaţie în lecţia „Reprezentarea grafurilor orientate

Procedura {iniţializări;} realizează iniţializarea stivei şi a proprietarului CD-ului.

–         într-un ciclu for, se iniţializează cu 0 întreg vectorul-stivă;

–         se citeşte numărul de ordine al proprietarului CD-ului în variabila x (nodul de plecare).

Procedura {tipar(p:integer):} afişează o configuraţie (st[1], st[2], …, st[p]) a vectorului-stivă.

Funcţia {valid(p:integer):boolean;} verifică pentru fiecare nivel p dacă st[p]I a generat o soluţie (st[1], st[2], …, st[p]) validă.

Testarea se face prin intermediul unei variabile booleene ok, iniţializează cu TRUE. În primul rând, din nodul st[p-1] se poate ajunge în

nodul st[p] numai printr-un arc (orice drum/circuit trece prin arce). Aşadar nodul st[p] este valid numai dacă există arc de la st[p-1] la st[p], adică a[st[p-1], st[p]]=1 (această condiţie provine din faptul că fiecare elev va transmite CD-ul numai prin cunoştinţă, ia relaţia de cunoştinţă este marcată în graf printr-un arc). În caz contrar ok devine FALSE.

ok:=TRUE;

if  a [ st[p],  st[p-1]]=0 then

ok:=FALSE;

Dacă ok a rămas TRUE, urmează testarea celei de-a doua condiţii. Am spus că soluţia este finală dacă p=n, iar pe ultimul nivel trebuie să se găsească  nodul x. Dar pe ultimul nivel anterior lui n nu putem avea nodul x (CD-ul revine la proprietar, dar numai după ce a trecut pe la ceilalţi elevi, pe la fiecare o singură dată).

if ok then

if (p<n) and (st[p]=x)

then

ok:=FALSE

Dacă ok a rămas în continuare TRUE, mai avem şi o a treia condiţie. Nodul st[p] să nu se mai găsească pe stivă (urmare a faptului că CD-ul trebuie să treacă pe la fiecare elev o singură dată). Parcurgem într-un ciclu nivelele i=1, 2, …, p-1 anterioare lui p. Dacă găsim un st[i] egal cu st[p], înseamnă că st[p] se mai găsesc pe un nivel anterior, deci ok devine şi în cazul acesta FALSE.

if ok then

for i:=1 to p-1 do

if  st[p]= st[i] then

ok:=FALSE

Procedura recursivă {bktr(p:integer);} “tratează” un nivel oarecare p al stivei.

  • Ø prin variabila val vor trece pe rând, într-un ciclu, toate valorile care teoretic ar putea fi puse pe nivelul p. Pentru fiecare dintre aceste valori:
    • dacă respectiva valoare a generat o soluţie validă (dacă funcţia valid(p) a returnat TRUE), atunci:

–         dacă soluţia respectivă e şi finală o tipărim (apelând procedura tipar (p)); în caz contrar trecem la nivelul următor (pentru a completa soluţia cu un nou nivel), prin auto-apelul bktr(p+1).

În programul principal, apelăm procedurile iniţializări şi citire_matrice, apoi declanşăm lanţul recursiv prin apelul bktr(1) (plecăm de la nivelul 1 al stivei).

Program XI_10;

var n,x:integer;

st:array[1..20] of integer;

a:array[1..20,1..20] of integer;

procedure citire_matrice;

{citeste matricea de adiacenta a de la tastatura}

var I,j:integer;

begin

write (‘numarul de noduri:  ’);  readln(n);

for i:=1 to n do

for j:=1 to n do

begin

write (‘[‘, i, ’,’, j, ‘]=’); readln(a[i, j]);

end;

end;

procedure initializari;

{initializeaza stiva si citeste datele problemei}

var i:integer;

begin

write (‘Cine este proprietarul: ’); readln(x);

for i:=1 to 25 do st[i]:=0;

end;

procedure tipar (p:integer);

{tipareste o solutie memorata in vectorul st}

var k:integer;

begin;

write (x, ’ ’);

for k:=1 to p do write (st[k]:4, ‘ ’);

writeln;

end;

function valid (p:integer): boolean;

{testeaza daca valoarea pusa pe nivelul p a generat o solutie valida, returnand TRUE sau FALSE}

var nr, i:integer; ok:boolean;

begin

{CD-il poate circula numai intre elevii care se cunosc, deci elevul st[p-1] trebuie sa il cunoasca pe st[p] pentru a-i putea da CD-ul mai departe}

ok:=TRUE;

if a[st[p-1], st[p]]=0 then ok:=FALSE;

if ok then

{proprietarul x nu se poate gasi pe un nivel anterior ultimului}

if (p<n) and (st[p]=x) then ok:=FALSE;

if ok then

{elevul st[p] nu trebuie sa se mai gaseasca pe nivelele anterioare}

for i:=1 to p-1 do

if st[p]= st[i] then ok:=FALSE;

valid:=ok;

end;

procedure bktr (p:integer);

{implementeaza algoritmul de backtracking recursiv}

var val:integer;

begin

{in variabila val trec pe rand toate valorile care ar putea fi incercate pe nivelul p al stivei}

for val:=1 to n do

begin

st[p]:=val;  {pune o noua valoare pe nivelul p}

if valid(p) then {daca solutia obtinuta e valida}

{o solutie e finala daca CD-ul a trecut pe la n elevi (p=n) si ultimul e proprietarul (st[p]=x)}

if (p=n) and (st[n]=x) then tipar (p) {daca e si finala, tipareste solutia}

else bktr (p+1); {trece la nivelul urmator in stiva, pentru a completa solutia}

end;

end;

begin;

initializai; citire_matrice; bktr(1); {plecam de la nivelul 1 pe stiva}

end.

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Blog la WordPress.com.

%d blogeri au apreciat asta: