Drumuri Minime In Retele de Transport

LUCRARE DE LICENȚĂ

Drumuri minime în rețele de transport

Introducere

Scopul acestei lucrări este aprofundarea algoritmilor de drumuri minime în grafuri și utilizarea acestora în probleme proactice, legate de transportul urban.

Motivația alegerii acestei teme este necesitatea oamenilor de a găsi rute cât mai rapide cu mijloacele de transport în comun. Acest lucru m-a determinat să îmi aleg ca subiect pentru licență drumuri minime în rețele de transport. Drumurile minime în Teoria grafurilor reprezintă un subiect de actualitate în aplicațile practice din zilele noastre.

Lucrarea este structurată în patru capitole. Primul capitol aduce în discuție noțiunile de bază folosite în Teoria grafurilor. Următorul capitol prezintă mai mulți algoritmi fundamentali în determinarea drumurilor minime dintr-un graf, printre care amintim de algoritmul Dijkstra, algoritmul Bellman-Ford sau algoritmul Floyd-Warshall. Cel de al treilea capitol conține metode euristice de căutare care pot determina drumurile minime dintr-un graf. Cel mai reprezentativ algoritm euristic este algoritmul A*. În ultimul capitol este prezentată aplicația suport a acestei lucări de licență. Aceasta este denumită Minimum Path Subway și are drept scop determinarea drumului minim dintr-o rețea de transport subtreană.

Cuprins

1.Noțiuni de bază…………………………………………………………………………………………………………………………………….4

2.Drumuri minime rezultate cu ajutorul algoritmilor convenționali ……………….9

2.1. Drumuri minime de sursa unică…………………………………………………10

2.1.1 Muchii de cost negativ………………………………………………………10

2.1.2 Reprezentarea drumurilor minime………………………………………12

2.1.3 Drum optim…………………………………………………………………….14

2.1.4 Relaxare…………………………………………………………………………16

2.1.4.1 Proprietățile relazării……………………………………………..18

2.1.5 Algoritmul Dijkstra………………………………………………………….23

2.1.6 Algoritmul Bellman-Ford………………………………………………….29

2.2. Drumuri minime între toate perechile de vârfuri…………………………..35

2.2.1 Algoritmul Floyd-Warshall………………………………………………..37

3. Drumuri minime rezultate cu ajutorul algoritmilor euristici de explorare…..43

3.1 Algoritmul A*…………………………………………………………………………..43

4. Aplicație……………………………………………………………………………………………54

4.1. Descrierea aplicației………………………………………………………………..54

4.2 Structura aplicației…………………………………………………………………..55

4.3 Tehnologii folosite în crearea aplicației………………………………………58

4.4 Detalii aplicație……………………………………………………………………….60

Bibliografie……………………………………………………………………………………………64

1. Noțiuni de bază

În acest capitol definim principalele noțiuni folosite în aplicație pentru a fi mai ușor de înțeles subiectele discutate. Fiecare definiție este însoțită de un exemplu concret.

Graf

Există doua tipuri de grafuri,neorientate și orientate.

Un graf neorientat G reprezintă o pereche ordonată de mulțimi (V,E), unde V este o mulțime finită nevidă ale cărei elemente sunt vârfurile grafului(nodurile), iar M este o mulțime formată din perechi neordonate de elemente ce aparțin lui V. Dacă elementele unei perechi din E diferă, aceasta formează muchie, altfel formează buclă.

Exemple: -muchie. Fie (x,y) E; x V; y V

x y

-buclă. Fie (x,x) E; x V;

x

Vârfurile x și y se numesc extremitățile muchiei și sunt adiacente în graf. Se mai poate spune că nodurile x,y sunt incidente cu muchia (x,y) E.

Un graf orientat G este o pereche ordonată de mulțimi (V, E) în care V este o mulțime finită nevidă, ale cărei elemente sunt vârfurile grafului(nodurile), iar mulțimea E este formată din perechi ordonate de elemente ale mulțimii V. Dacă elementele unei perechi diferă, aceasta se numește arc, altfel daca acestea coincid se numește buclă.

Exemple: – arc: Fie (x,y) E; x V; y V;

x y

– buclă: Fie (x,x) E; x V;

x

Nodurile x și y sunt adiacente în graf și sunt incidente cu arcul care îl formează.

Gradul unui vârf

Într-un graf neorientat gradul vârfului x se notează cu d(x) și este suma tuturor muchiilor incidente cu x.

Exemplu: x

d(x)=5

Figura 1.1

Într-un graf orientat, vârful x are două grade, de intrare și de ieșire.

Gradul de intrare se notează d ¯(x) și este numărul arcelor care ajung la x, iar gradul de ieșire se notează d+(x) și este numărul de arce care pleacă din x.

Exemplu: x d+(x)=4

d-(x)=1

Figura 1.2

Fie graful G=(V, E). Graful G’=(V’, E’) este subgraf al lui G dacă V’ este inclus în V, iar E’ conține toate muchiile din E formate cu vârfurile din V’.

Fie G=(V, E) un graf neorientat cu n vârfuri.Acesta se numște graf complet dacă oricare două vârfuri, x,y V sunt adiacente, (x,y) E.

Exemplu: x y

t z

Figura 1.3

Un lanț într-un graf neorientat G=(V, E) este o secvență de noduri cu proprietatea că oricare două noduri consecutive din aceasta sunt adiacente.

Exemplu: 2 5

4 6 Nodurile 1 și 6 sunt

1 3 extremitățile lanțului.

Figura 1.4

Lungimea unui lanț este numărul de muchii din care este alcătuit.

Ciclul într-un graf neorientat G=(V, E) este o secvență de vârfuri care formează un lanț, iar vârful inițial coincide cu cel final.

Exemplu: 1

2

3

4

5 Noul inițial=nodul final=1

Figura 1.5

Fie graful neorientat G=(V, E). Acesta se numește conex dacă oricare ar fi x V, y V, există un lanț care are capetele x și y.

Dacă nu se îndeplinește condiția de mai sus, graful se împarte în componente conexe (subgrafuri conexe maximale, cu mulțimea vârfurilor distincte două câte două).

Exemple: 1 7 1 7

6

2 4 6 2 5

3 3 4 9 8

5

GRAF CONEX DOUĂ COMPONENTE CONEXE

Figura 1.6

Într-un graf orientat G=(V,E) un drum este o secvență de noduri cu proprietatea că oricare două noduri consecutive formează un arc.

Exemplu: 2 5 Nodurile 1 și 5 sunt

1 3 extremitățile drumului.

4

Figura 1.7

Lungimea unui drum reprezintă numărul de arce din care este format.

Într-un un graf orientat G=(V, E) circuitul reprezintă o secvență de vârfuri care formază un drum, iar nodul inițial coincide cu nodul final.

Exemplu: 1 2

5 3 Nodul inițial=nodul final=1

6

4

Figura 1.8

Distanța într-un graf neorientat G=(V, E) între două vârfuri x,y V reprezintă lungimea celui mai scurt lanț dintre cele două vârfuri. Se notează cu d(x,y).

Exemplu: x y z

u

w t d(x,u)=3.

Figura 1.9

Într-un graf orientat G=(V, E), distanța între două vârfuri x,y V reprezintă lungimea celui mai scurt drum dintre acestea. Se noteaza d(x,y).

2 3

1

4 5 6 7 d(1,7)=3

Figura 1.10

Un graf orientat G=(V, E) se numește ponderat dacă fiecărei muchii a sa i se atribuie o pondere, care poate fi un cost, o greutate, o durată, etc.

De exemplu în graful din figura de mai jos ponderea muchiei <s,a> este 4 sau a muchiei <a,b> este 1, etc.

s 4 a

9 1 b

c 6

Figura 1.11

2. Drumuri minime “Algoritmi fundamentali”

În introducere voi da un exemplu practic, din viața reală pentru a înțelege noțiunile ulterior enunțate.

O persoană vrea să plece într-o călătorie în România și vrea să știe toate drumurile minime între orașul unde se află și cel în care sunt situate obiective turistice ce trebuiesc vizitate.

Se pot calcula toate drumurile posibile, însă acest lucru ar fi incomod și ineficient. Turistul trebuie să știe ce drum trebuie să urmeze pentru a putea vizita cât mai mult sau a economisi timp. De exemplu persoana vrea să plece de la București pentru a vizita Castelul Peleș și Castelul Bran din Brașov. Unele din trasee pot fi București- Pitești- Brasov, 240 km, București –Ploiești- Brașov 194 km, sau București –Târgoviste- Brașov 188km. Turistul trebuie să cunoască nu doar câți kilometri trebuie să parcurgă, ci și care este drumul optim.

În acest capitol vom descrie noțiuni și algoritmi care permit determinarea de drumuri minime în mod eficient.

Fie un graf orientat de costuri G=(V,E), funcția de cost:E , fiecărei muchii asociindu-se un cost reprezentat de un număr real. Costul unui drum p= v1, v2, ……..,vk este determinat de suma costurilor muchiilor care îl formează:

(p)=(vi-1,vi)

Costul unui drum minim(costul optim) de la nodul u pana la nodul v se definește prin:

(u,v)=, unde up v indică drumul p dintre u și v.

Un drum minim de la u la v reprezintă orice drum p cu proprietatea (p) = (u,v).

Există două categorii de probleme legate de drumuri minime în grafuri:

– Problema drumului minim de sursă unică, adică de la un nod sursă la restul nodurilor

– Problema drumului minim, între toate perechile de noduri.

2.1. Drumuri minime de sursă unică

În acest subcapitol vom prezenta algoritmi de rezolvare a problemei drumurilor minime de sursă unică: fiind dat un graf G=(V, E) dorim să găsim pentru un vârf sursă cunoscut s V, un drum minim până la fiecare vârf v V. Pe baza algoritmul de rezolvare a acestei probleme, putem rezolva și alte probleme reductibile la aceasta, printre care :

– Problema drumurilor minime de destinație unică: Problema constă în determinarea pentru fiecare vârf v V, a unui drum minim către vârful t cu destinație prestabilită. Totul se rezumă la inversarea muchiilor în graf rezultând o problemă de determinare a drumului minim de sursă unică.

– Problema drumurilor minime de sursă și destinație unică: În această problema determinăm un drum minim unic de la u si v, cunoscându-se u si v. Rezolvând problema drumurilor minime de sursă unică pentru vârful u, la un moment dat nodul destinație devine v și se află rezultatul. Acest mod de rezolvare al problemei este cel mai rapid.

– Problema drumurilor minime pentru surse si destinații multiple: În acest caz trebuie să determinăm pentru fiecare pereche de vârfuri u și v un drum minim. Problemele se pot rezolva cu ajutorul aplicarii algoritmului de aflare a drumului minim cu sursă unică, însă acestă abordare este mai puțin eficientă. În urmatorul subcapitol se va analiza mai detaliat modul de determinare

și construcție acestui tip de drumuri cu ajutorul altor metode sau algoritmi mai eficienți. (Algoritmul Floyd-Warshall)

2.1.1 Muchii de cost negativ

Considerăm un graf G=(V, E), un nod sursă s de la care vrem să calculăm drumurile minime către orice alt nod v al grafului.

În componența drumului se pot regăsi și muchii de cost negativ, doar dacă acestea nu se află într-un ciclu cu cost negativ.Dacă întâlnim această situație, atunci costul drumului minim va fi – ((s,v)= -).

În următorul exemplu voi prezenta efectul muchiilor de cost negativ asupra determinării drumului minim de la un nod sursă la restul nodurilor:

s -1 a 2 b

5 1

e c

-7 2 -6

f 3

d

Figura 2.1

Figura 2.1 reprezintă un graf orientat, iar drumurile minime sunt următoarele:

-drumul minim de la s la a este unic, are costul (s,a)= (s,a)= -1(chiar dacă costul este negativ, distanța se poate calcula pentru că, nu există ciclu de cost negativ care să fie accesibil din s).

-drumul minim de la s la b este unic, (s,b)= (s,a) + (a,b)= -1+2=1.

-drumul minim de la s la c, are în componența sa un ciclu de cost negativ. Rezultă că drumul minim are valoarea . Ciclul de cost negativ este format din muchiile <c,d> si <d,c>. –

-drumul minim de la s la d va avea costul -, fiind aceeași situație ca cea a drumului minim de la nodul s la nodul c. Pe parcursul determinării acestuia, drumul accesează un ciclu de cost negativ care va face ca costul drumului să tindă către -.

-drumul minim de la s la e este unic, are costul 5.

-drumul minim de la s la f are costul -2.

Determinarea drumului minim de sursă unică se face cu ajutorul unei serii de algoritmi, precum:

– Algoritmul Dijkstra calculează drumul minim, dar în ipoteză că toate costurile muchiilor trebuie să fie pozitive.

-Algoritmul Bellman-Ford, funcționează și pentru grafuri cu muchii care au costuri negative. Acesta determină prezența ciclurilor de costuri negative și semnalează acest lucru și furnizează răspunsuri corecte în scopul determinării drumului minim de la un nod sursă.

2.1.2.Reprezentarea drumurilor minime

În problemele de drum minim, avem drept scop nu numai să calculăm distanțele de cost optim, dar și să determinăm vârfurile care alcătuiesc drumul minim.

Fie un graf G=(V, E). Vom reține pentru fiecare vârf v V, cu ajutorul vectorului , predecesorul său.Valoarea [v] este egală cu penultimul nod al drumului minim de la nodul sursă la nodul v. Muchia având capetele v și [v] este ultima din drumul minim astfel construit. Nodului sursă și nodurilor care nu au drum către sursă li se vor atribui în vectorul predecesor valoarea zero. Algoritmii care urmează să fie prezentați și care determină drumul minim, vor folosi o procedură care va afișa lanțul de predecesori din aproape în aproape, astfel putându-se determina și nodurile care comun drumul. Așadar, pentru orice vârf v, al cărui predecesor (v) este diferit de zero, vom folosi următoarea procedură AFIȘEAZĂ_DRUM(G,s,v) :

AFIȘEAZĂ_DRUM(G,s,v)

{

Daca v=s atunci

afișează s

altfel dacă [v] =NULL atunci

afișează “nu există drum de la s la v”

altfel

Afișează_drum(G,s,[v])

Afișează v

}

În algoritmii pe care îi vom prezenta, pentru a demonstra că valorile finale din sunt corecte vom studia subgraful predecesorilor G = (V , E) indus de valorile lui

Mulțimea V este formată din vârfurile din G cu proprietatea că au predecesor diferit de NULL și de vârful s:

V ={ vV : v] ≠ NULL} {s}

Mulțimea E este formată din muchiile induse de valorile lui pentru vârfurile din V :

E = {([v],v)E : v V \ {s}}

Vom demonstra că valorile din determinate de algoritmii de calcul al drumului minim din acest capitol indica valori corecte. În acest caz, G trebuie să fie un arbore al drumurilor minime definit cum urmează:

Definiție:

Fie G=(V, E) un graf orientat ponderat cu funcția de cost : E→ și nodul sursă s. În acest graf considerăm că nu avem cicluri de cost negativ ce pot fi accesate de un drum minim din nodul sursă s deoarece trebuie să știm cu siguranță că toate drumurile minime au costuri numere reale. În aceste ipoteze, un arbore al drumurilor minime de rădăcină s este un subgraf orientat

G’=(V’, E’), unde V’ V, E’ E astfel încât urmatoarele condiții sunt satifăcute:

– V’ este mulțimea vârfurilor accesibile de un drum din s în graful G

– G’ este un arbore orientat cu rădăcină

– pentru orice v V’, drumul unic de la s la v în G’ este un drum minim de la s la v în G

Drumurile minime nu sunt unice, putând exista mai multe drumuri minime între două noduri cu același cost, dar vectorul predecesorilor diferit, așadar rezultă ca nu exista un unic arbore de drumuri minime. În urmatorul exemplu se arată acest lucru:

s 3 a 5 b

4 1 1

d 5 c

Figura 2.2

Acesta este un graf orientat cu costul drumurilor minime de la s la următoarele noduri: (s,a)= 3, (s,b) = 8, (s,c) = 9, (s,d)=4.

s 3 a 5 b s 3 a 5 b

4 1 1 4 1 1

d 5 c d 5 c

Muchiile colorate cu albastru formează un Muchiile colorate cu maro formează

arbore de drumuri minime avand drept un alt arbore de drumuri minime

rădăcină nodul s . tot cu rădăcina s.

Figura 2.3

2.1.3. Proprietăți ale drumurilor minime

Algoritmii fundamentali de drum minim din acest capitol se bazează pe proprietatea că orice subdrum dintre două vârfuri al unui drum minim este drum minim între cele două vârfuri. Această simplă observație va interveni în corectitudinea algoritmilor Dijkstra și Bellman-Ford care determină drumul minim de la un nod sursă la toate celelalte noduri, dar și a algoritmului Floyd-Warshall care calculează toate drumurile minime între oricare două noduri ale grafului.

În continuare este demonstrată proprietatea de optimalitate a drumurilor minime []:

Lema 2.1:(Subdrumurile unui drum minim sunt drumuri optimale)

Fie un graf orientat G=(V, E) cu funcția de cost :E, fie p=(v1,v2,…vk) un drum minim de la vârful v1 la vârful vk și pentru i și j astfel încât 1ijk fie pij = <vi,vi+1,…..,vj> subdrumul lui p de la varful vi la vârful vj. Atunci, pij este un drum minim de la vi la vj.

Demonstrație:

Dacă descompunem drumul p în v1p1i vipij vjpjk vk , atunci (p)= (p1i) + (pij) + (pjk). Presupunem că avem un drum p’ij de la vi la vj de cost (p’ij) <(pij).

Atunci v1p1i vip’ij vjpjk vk este un drum de la vi la vk al cărui cost (p1i) + (p’ij) + (pjk) < (p). Acest lucru contrazice presupunerea că p este un drum minim de la v1 la vk.

Corolar 2.1:

Fie G=(V, E) un graf orientat ponderat și funcția de cost :E . Presupuneam că drumul minim p de la vârful sursă s la vârful v poate fi descompus în sp’ u → v, pentru un anume vârf u și un drum p’. Așadar, costul unui drum minim de la s la v este (s, v) = (s,u) + (u,v).

Demonstrație:

Conform lemei de mai sus, subdrumul p’ este un drum minim de la vârful sursă s la vârful u. Rezultă următoarele:

(s, v) = (p) = (p’) + (u,v) = (s,u) + (u,v).

Lema următoare subliniază o proprietate a drumurilor de cost minim.

Lemă 2.2:

Fie G = (V, E) un graf orientat ponderat și cu funcția de cost :E și fie un vârf sursă s. Atunci, pentru toate muchiile (u,v) E avem (s, v) (s,u) + (u,v).

Demonstrație:

Un drum de cost minim p de la vârful sursă s la vârful v este mai mic sau egal cu orice alt drum de la s la v. Astfel, costul drumului p este mai mic sau egal cu costul oricărui drum de sursă s la vârful u care conține muchia (u,v).

2.1.4. Relaxare

Algoritmii de drumuri minime de sursă unică au la bază aceeași idee, cunoscută sub numele de tehnica relaxării. În acest subcapitol vom prezenta această tehnică, ce care are un rol important în determinarea corectă a drumurilor minime într-un graf.

Orice vârf v V va avea asociată o valoare d[v] care reprezintă suma totală a costului drumului minim de la nodul sursă s până la acesta. Pe parcursul algoritmului, d[v] reprezintă o estimare a drumului minim, mai exact va fi costul unui drum deja determinat de la sursă la vârful v.

Inițial, fiecare vârf v din V va avea valoarea d[v] infinit, iar predecesorul nodului v va avea valoarea zero fiindcă nu s-a executat niciun pas din algoritmii de determinare a drumurilor minime. Estimarea drumului minim de la sursă la ea însăși are valoarea zero.

Următoarea procedură se ocupă de cele enunțate mai sus, numindu-se sugestiv INIȚIALIZARE_SURSĂ:

INIȚIALIZARE_SURSĂ(G,s)

{

pentru fiecare v V[G] execută

dacă v≠ s atunci

d[v]←

NULL

altfel

d[v] ← 0

NULL

d[s]←0

}

Tehnica relaxării constă în verificarea muchiei (u,v) dacă poate îmbunătăți costul drumului minim calculat până atunci de la nodul sursă s la v. Prin îmbunătățirea costului înțelegem modificarea inițială a estimării drumului minim până la nodul v, cu o valoare mai mică determinată de un alt drum de cost mai mic.

Dacă este posibil acest lucru, atunci se reactualizează valoarea drumului minim d[v] prin descreșterea sa, dar în același timp în câmpul ce conține predecesorul vârfului v se înlocuiește vechea valoare cu u.

Următoarea procedură realizează un pas de relaxare pe muchia (u,v) care reprezintă o relaxare a restricției d[v]d[u] + (u,v) , adică distanța estimată de la s până la nodul v este mai mică decât distanța estimtă de la sursă până la nodul u plus costul muchei (u,v).

RELAXEAZA(u,v,)

{ dacă d[v]>d[u] + (u,v) atunci

d[v] ← d[u] + (u,v)

← u }

Exemplu:

1) u v 2) u v

d[u]=1 d[v]=8 d[u]=1 d[v]=3

RELAXEAZA(u,v,) RELAXEAZA(u,v,)

u v u v

d[u]=1 d[v]=4 d[u]=1 d[v]=3

(u,v)= 3 (u,v)= 3

Figura 2.4

În primul exemplu, înainte de relaxare, valoarea lui d[v] este mai mare decat d[u]+(u,v), iar după ce se aplică relaxarea această valoare se modifică atribuindu-se costul d[v]= d[u]+(u,v).

În al doilea exemplu înainte de relaxare d[v] este mai mică sau egală cu d[u]+(u,v), așadar valoarea lui d[v] ramane neschimbată după ce s-a aplicat relaxarea.

În algoritmii considerați, relaxarea este unica modalitate prin care estimările drumurilor minime și a predecesorilor sunt modificați. Aceștia diferă între ei atât prin numărul de relaxări efectuate, dar și prin ordinea în care muchiile sunt relaxate.

În algoritmul Dijkstra fiecare muchie este relaxată o singură dată, pe când în algoritmul Bellman-Ford fiecare muchie este relaxată de mai multe ori.

2.1.4.1. Proprietățile relaxării

Proprietățile operației de relaxare sunt enunțate sunt forma unor leme []. Toate aceste leme sunt aplicabile oricărei secvențe de pași de relaxare asupra unui graf orientat cu costuri, inițializat cu ajutorul procedurii INIȚIALIZARE_SURSĂ definite mai sus.

Corectitudinea algoritmilor de drumuri minime de sursă unică va rezulta din aceste leme.

Lemă 2.3:

Fie G=(V, E) un graf orientat ponderat și funcția de cost :E si fie (u,v) E. Atunci, după relaxarea muchiei (u,v) cu ajutorul procedurii RELAXEAZĂ(u,v,) rezultă d[v] d[u] + (u,v).

Demonstrație:

Dacă înaintea relaxării muchiei (u,v) condiția d[v] > d[u] + (u,v) este îndeplinită, atunci prin relaxare d[u] devine d[u] + (u,v). Dacă înaintea aplicării relaxării d[v] d[u] + (u,v), nici d[v] și nici d[u] nu se modifică, după aplicarea relaxării avem d[v] d[u] + (u,v).

Lemă 2.4:

Fie G=(V, E) un graf orientat cu costuri și funcția de cost :E. Fie s V un vârf sursă și presupunem că graful este inițialzat cu ajutorul procedurii INIȚIALIZARE_SURSĂ(G,s). Atunci pentru orice vV avem d[v] (s,v) și relația se păstrează pentru orice secvență de pași de relaxare efectuați asupra muchiilor lui G. În plus, odată ce d[v] își atinge marginea inferioară (s,v), valoarea lui nu se mai modifică.

Demonstrație:

Relația d[v] (s,v) este cu certitudine îndeplinită după inițializare deoarece d[s]=0 (s,s). Dar dacă d[v]= atunci d[v] (s,v),-{s}.

Observație: (s,s) este – dacă vârful sursă s este într-un ciclu de cost negativ, sau poate fi zero în caz contrar.

Vom demonstra prin reducere la absurd că relația se menține pentru orice secvență de pași de relaxare. Fie v primul vârf pentru care un pas de relaxare a muchiei (u,v) determină d[v] (s,v). Atunci după relaxarea muchiei (u,v) obținem:

d[u] + (u,v) = d[v] < (s,v) (s,u) + (u,v). (din lema 2.3)

Această inegalitate implică d[u]< (s,u).Deoarece, însă, relaxarea muchiei (u,v) nu modifică d[u], această inegalitate ar trebui să fie adevărată înainte de relaxarea muchiei, ceea ce contrazice alegerea lui v ca fiind primul vârf pentru care d[v] (s,v) se păstrează pentru orice v aparținând lui V.

Pentru a vedea că valoarea lui d[v] nu se mai modifică o dată ce d[v] = (s,v), să observăm că dacă și-a atins marginea inferioară, deoarece d[v] (s,v), rezultă că d[v] nu mai poate descrește sau crește, fiindcă pași de relaxare nu determină incrementarea valorilor lui d.

Corolar 2.2:

Presupunem că în graful orientat ponderat G=(V, E) și funcția de cost :E, nu ar exista drum de la vârful sursă s V la un vârf dat v V. Atunci după pasul de inițializare a grafului (INIȚIALIZARE_SURSĂ(G,s)), am avea d[v] (s,v) și această egalitate s-ar păstra pentru orice secvență de pași de relaxare pentru graful G.

Demonstrație:

Din lema 2.4) observăm că =(s,v) d[v], atunci d[v] = =(s,v)

Următoarea lemă este esențială în demonstrarea corectitudinii algoritmilor de drum minim, furnizând condiții suficiente pentru ca estimarea drumului, obținut prin relaxare să conveargă la costul unui drum minim.

Lema 2.5:

Fie G=(V, E) un graf orientat ponderat și funcția de cost :E. Fie s V un vârf sursă și s u → v un drum minim în G cu u,v V. Graful G este inițializat cu ajutorul procedurii INIȚIALIZARE_SURSĂ(G,s) și apoi se efectuează o secvență de pași de relaxare cu ajutorul funcției specifice RELAXEAZĂ ( u,v,) asupra grafului G. Dacă înaintea unei relaxări d[u]= (s,u), atunci d[v] primeste valoarea (s,v) după apelarea funcției RELAXARE.

Demonstrație:

Din lema 2.4 observăm ca dacă d[u]= (s,u) înaintea unei relaxări a muchiei (u,v), atunci egalitatea se pastrează în continuare. După relaxarea muchei (u,v) avem:

d[v] d[u] + (u,v) (acest lucru este enunțat si demonstrat în lema 2.3.

=(s,u) + (u,v)

= (s,v) (acest lucru este enunțat si demonstrat în corolarul 2.1)

Din lema 2.4 rezultă că (s,v) este minorant pentru d[v], deci d[v]=(s,v) și această egalitate se va păstra la toate momentele ulterioare.

În următoarea parte vom demonstra că dacă o secvență de relaxări determină un drum minim, atunci subgraful predecesorilor G indus de valorile lui este un arbore al drumurilor minime pentru G.

Următoarea lemă stabilește că subgraful predecesorilor este un arbore având drept rădăcină vârful sursă cunoscut.

Lema 2.6:

Fie G=(V, E) un graf orientat cu costuri și funcția de cost :E și s V un vârf sursă. Presupunem că G nu are cicluri de cost negativ care să nu poată fi atinse din vârful s. Atunci, după ce graful a trecut de pasul inițializării ( INIȚIALIZARE_SURSĂ (G,s)), graful predecesorilor G este un arbore cu rădăcină s pentru orice secvență de pași de relaxare aplicată muchiilor din G.

Demonstrație:

În momentul inițial în G avem doar vârful sursă. Rezultă ca afirmația de mai sus este adevărată.

La următorul pas considerăm că G este graful predecesorilor, rezultat în urma execuției unei relaxări. Demonstrăm prin reducere la absurd că graful Geste aciclic. Presupunem că la un anumit pas în relaxare apare un ciclu în graful G, notat cu c = <v0,v1,…..vk>, v0 = vk. Rezultă că [vi] = vi-1, pentu i=1,2,3,…k și fară restângerea generalitații presupunem că ciclul format este în G prin relaxarea muchiei (vk-1,vk).

Afirmăm că toate vârfurile ciclului c pot fi atinse din vârful sursă s. Acest lucru este posibil pentru că fiecare vârf al ciclului c în momentul în care i-a fost atribuită o valoare diferită de zero în vectorul , are de asemenea asociată și o estimare a drumului minim. Prin lema 2.4, fiecare vârf al ciclului c are costul unui drum minim finit, din care rezultă că vârful este accesibil din s.

Exemplu care ilustrează unicitatea drumului în G de la nodul sursă la orice vârf.

Nodul sursă s. Cosiderăm v vârful la care vrem să ajungem.

b v

s a d

c

Figura 2.5:Drumulde la nodul sursă s la nodul v. Dacă ar există două drumuri de la s la v p1=(s→a→b→d→f→v) și p2=(s→a→c→e→f→v), unde cb și c≠d și e≠b și e≠d atunci [f]=d si [f]=e ceea ce ar duce la o contradicție.

Următorul pas în demonstrație este să analizăm estimările drumurilor minime ale vârfurilor din c existente înaintea efectuării apelul funcției RELAXEAZĂ(vk-1,vk,) si apoi să arătăm că ciclul c are un cost negativ, fapt ce ar contrazice presupunerea că G nu conține cicluri de cost negativ care să poată fi atinse de vârful sursă. Înainte de efectuarea apelului, avem

[vi] = vi-1 pentru i=1,2,3…k-1. Așadar pentru i=1,2,3,…k-1, ultima reactualizare a valorii d[vi] a fost: d[vi]←d[vi-1] + (vi,vi-1). Dacă din acest moment valoarea lui d[vi-1] a fost modificată, atunci noua valoare va fi mai mică( regula a relaxării) . Apoi exact înaintea exectuării apelului funcției RELAXEAZĂ(vk-1,vk,)avem inegalitatea:

d[vi]d[vi-1] + (vi-1,vi), i=1,2,3…k-1. (2.6.1)

Deoarece [vi] a fost modificat prin apel, înainte de apel aveam inegalitatea strictă:

d[vk] > d[vk-1] + + (vk-1,vk). (2.6.2)

Din inegalitatea 2.6.2 și din însumarea celor k-1 inegalități 2.6.1 se obține suma estimărilor drumului minim de-a lungul ciclului c:

[vi]>[vi-1] + (vi-1,vi)) = [vi-1] + (vi-1,vi)

Dar,

[vi] = [vi-1], deoarece fiecare vârf din ciclul c apare exact o dată în fiecare din cele două sume. De aici rezultă inegalitatea:

0>(vi-1,vi).

Din aceasă inegalitate rezultă că lungimea ciclului c este negativă, ceea ce este o contradicție.

Rezultă că graful G este un graf orientat aciclic.

Pentru a arăta ca el este un arbore cu rădăcina s, este suficient să arătăm că pentru orice vârf v V există un drum unic de la s la v în G.

Trebuie să arătăm mai întâi ca pentru orice vârf din V există un drum de la s către acel vârf. Mulțimea V ese formată din vârfurile care au valori diferite de NULL și de vârful s. Ideea este de a demonstra prin inducție că există un drum de la s către toate vârfurile din V.

Pentru a completa demonstrația lemei, trebie arătat faptul că orice vârf v V există cel mult un drum de la s la v în graful G . Să presupunem contrariul. Cu alte cuvinte, să presupunem că există două drumuri simple de la s la un anume vârf v: p1 , care poate fi descompus în s a b → d v și p2 care poate fi descompus în s a c → d v, unde d≠e. În acest caz, rezultă [d]= b și [d]=c ceea ce conduce la contradicția x=y. În cosecință, există un singur drum în G de la s la v, deci G este un arbore al drumurilor minime de rădăcină s.

Acum putem demonstra că, dupa efectuarea unei secvențe de pași de relaxare, tuturor vârfurilor le-au fost asociate adevăratele costuri corespunzătoare drumurilor minime, rezultă că subgraful predecesorilor G este un arbore al drumurilor minime.

2.1.5. Algoritmul lui Dijkstra

Acest algoritm a fost descoperit de catre Edsger Dijkstra în anul 1956.

Voi da un exemplu practic pentru a înțelege mai bine utilizarea acestui algoritm.

O persoană vrea să știe care este distanța minimă de la locuința sa până la o destinație anume utilizând mijloacele de transport în comun din oraș. Distanța minima poate fi reprezentă de numărul minim de stații parcuse sau de distanța efectivă parcursă. O soluție a problemei acestea este aplicarea algoritmului Dijkstra aspura hărții transportului public, care poate fi interpretat ca un graf, fiecare vârf fiind o stație.

Algoritmul Dijkstra rezolvă problema drumurilor minime de sursă unică într-un graf orientat cu costuri asociate fiecărei muchii, G=(V,E). Fiecare muchie are cost pozitiv( (u,v)0, pentru orice (u,v) E).

Algoritmul încearcă la fiecare pas să găsească drumuri noi din vârfuri cât mai apropiate de sursă, relaxând muchiile divergente din acesta . Pentru aceasta algoritmul lucrează pe o mulțime S de vârfuri, ale căror costuri de la sursă către ele au fost deja determinate. Mai precis, algoritmul lucrează pentru toate vârfurile v S care au d[v]=(s,v) . Algoritmul iterează selectarea unui vârf u V-S, cu proprietatea că estimarea drumului minim este minim, apoi introduce acest vârf u în S și relaxează muchiile divergente din u. În implementarea algoritmului din următorul paragraf, este necesară o coadă de prioritați Q, în care vom avea toate vârfurile din V-S indexate prin valorile d corespunzătoare. Graful G este reprezentat prin liste de adiacență.

Funcția care definește acest algoritm:

DIJKSTRA(G, ,s)

{

1 INIȚIALIZEAZĂ_SURSĂ(G,s)

2 S←

3 Q←V[G]

4 cât timp Q≠ execută

5 u←EXTRAGE_MINIM(Q)

6 S←S{u}

7 pentru fiecare vârf vAdj[u] execută

8 RELAXEAZĂ(u,v, )

}

În continuare vom explica pașii cei mai importanți ai algoritmului Dijksra:

– linia 1: apelăm funția de inițializare a valorilor d și

– linia 2: mulțimea S inițial va fi vidă

– linia 3: coada de priorități este inițializată, cu toate vârfurile din V

-liniile 4-6: cu ajutorul structurii repetitive cât timp, se va extrage un vârf u din Q=V-S și va fi introdus în mulțimea S.

-liniile 7-8: luăm fiecare muchie (u,v) divergentă cu u și reactualizăm estimarea d[v] și predecesorul [v] în cazul în care drumul minim către v poate fi micșorat. (aceastea sunt caracteristicile proceduri RELAXEAZĂ).

Exemplu:

Figura 2.6

În figura de mai sus am ilustrat pe pași modul cum lucrează agloritmul Dijkstra. Vârful sursă este s. Primul desen reprezintă configurația inițială, imediat inainte de prima iterație. În următorii pași își pune amprenta structura repetitivă cât timp din algoritm, iar muchiile colorate diferit față de pasul anterior sunt muchiile relaxate de algoritm( liniile 4-8).

Algoritmul Dijkstra în implementarea sa alege întotdeauna vârful cu eticheta de distanță cea mai mică și îl prelucrează. Intuitiv această strategie nu asigură obținerea soluției optime, de aceea este necesar să demonstrăm corectitudinea algoritmului. Pentru aceasta vom enunța o teoremă și un corolar [].

Teoremă 2.1: Corectitudinea algoritmului Dijkstra

Dacă algoritmul Dijkstra este aplicat unui graf orientat ponderat G=(V, E) cu funcția de cost negativă și vârf sursă s, atunci la terminare d[u] = (s,u) pentru toate vârfurile u V

Demonstrație:

Vom demonstra prin reducere la absurd că pentru fiecare vârf u V în momentul în care u este introdus în mulțimea S, d[u] = (s,u) și egalitatea se va menține la toate momentele de timp ce vor urma.

Fie u primul vârf pentru care d[u] ≠ (s,u) în momentul la care el este introdus în mulțimea S. Studiem configurația existentă la începutul iterației din bucla cât timp care determină introducerea vârfului u în S și prin examinarea unui drum minim de la s la u vom obține concluzia d[u] = (s,u). Deoarece s este primul vârf introdus în S și d[s] = (s,s)=0 rezultă ca u≠s. Deoarece u≠s, avem S≠ în momentul în care în S introducem u. În mod necesar, există un drum de la s la u, deoarece în caz contrar prin corolarul 3.3 am avea d[s] = (s,s)= ceea ce ar contrazice ipoteza d[u] ≠ (s,u). Deoarece există cel puțin un drum de la s la u, există și un drum minim p de la s la u. Drumul p conectează un vârf s din S și un vârf u din V-S. Fie y primul vârf de-a lungul lui p astfel încât y V-S și fie x V predecesorul lui y. Din figura urmatoare rezultă că drumul p poate fi descompus ca sp1 x→y p2 u.

Figura 2.7:Mulțimea S este nevidă, Introducem pe u în aceasta. Un drum minim de la vârful sursă s la vârful u este descompus în urmatorul mod s→p1 x→p2 u, unde y este primul vârf al drumului ce nu se află în mulțimea S, iar xS îl precede pe y. Vârfurile x≠y, dar putem avea urmatoarele situații s=x sau y=u..

Afirmăm că d[y]=(s,y) în momentul la care u este introdus în u. Pentru a demonstra această afirmație, observăm că x S. Deoarece u este primul vârf pentru care d[u] ≠ (s,u) în momentul la care el este introdus în S, rezultă că d[x] = (s,x) în momentul în care x este introdus în S. Muchia (x,y) a fost relaxată, deci afirmația rezultă pe baza lemei 2.5.

Dar, deoarece y precede u pe un drum minim de la s la u și toate costurile muchiilor sunt nenegative (în particular și care compun drumul p2 ) avem (s,y) (s,u) și deci:

d[y] =(s,y) < (s,u) d[u] (lema 3.3)

Dar, deoarece vârfurile u și y se aflau deja în V-S în momentul în care u a fost selectat în linia 5, din algoritm rezultă d[u] d[y]. Așadar, inegalitatea de mai sus se transformă in egalitate:

d[y] =(s,y) = (s,u)= d[u]

În consecință, d[u]=(s,u) ceea ce contrazice alegerea făcută vârfului u.

În concluzie, în momentul în care fiecare vârf u V este inserat în mulțimea S , avem d[u]=(s,u) și conform lemei 2.3) această egalitate se pastrează la toate momentele de timp ce vor urma.

Corlar 2.3 (la teorema de corectitudine al algoritmului Dijkstra):

Dacă algoritmul Dijkstra este aplicat unui graf orientat G=(V,E) cu funcția de cost pozitivă :E și vârf sursă s, atunci la terminare subgraful predecesorilor G va fi un arbore al drumurilor minime de rădăcină s.

Complexitatea algoritmului Dijkstra

Calculăm timpul de rulare al algoritmului Dijkstra într-un graf cu |E| muchii și |V| noduri.

În primul rând analizăm algoritmul Dijkstra descris în acest subcapitol, care stochează vârfurile mulțimii Q într-o coadă de priorități, care este de fapt o listă. Operația EXTRAGE_MINIM(Q) este o simplă căutare liniară a vârfurilor mulțimii Q. Rezultă un timp de rulare O(V2+E).

În al doilea rând, pentru grafurile rare, care au un număr mai mic de muchii decât | V2| , algoritmul Dijkstra se poate implementa într-un mod mai eficient, prin stocarea grafului sub forma listelor de adiacență și folosirea heap binar sau heap Fibonaci pe post de coadă de priorități în implementarea funcției EXTRAGE_MINIM. Cu heap binar algoritmul necesită un timp de rulare de ordinul O((E + V) log V), iar heap Fibonaci îmbunătățește acest timp la O(E + V logV).

2.1.6. Algoritmul Bellman-Ford

Algoritmul Bellman-Ford rezolvă problema drumurilor minime de sursă unică în cazul în care costul muchiilor pot fi negative. Amintim că în corectitudinea algoritmului lui Dijkstra a fost esențial faptul că muchiile au cost nenegativ. Fie un graf orientat ponderat G= (V, E) cu vârful sursă s și funcția de cost :E. Algoritmul detectează existența unui ciclu de cost negativ accesibil din vârful sursă dat. Dacă algoritmul a găsit un astfel de ciclu, semnalează ca nu a gasit soluție, iar dacă un astfel de ciclu nu există algoritmul calculează drumurile minime și costurile asociate.

Acest algoritm utilizează ca și algoritmul Dijkstra tehnica relaxării, scăzând valoarea estimării d[v] a drumului minim de sursă s de fiecare vârf v V până când este obținut costul corect (s,v) al unui drum minim..

Algoritmul Bellman-Ford după efectuarea inițializării (INIȚIALIZEAZĂ_SURSĂ), efectuează |V| – 1 treceri prin muchiile grafului facând câte o relaxare a fiecărei muchii. La sfârșit verifică existența ciclului negativ sau nu.

În urmatoarea parte voi explica cei mai importanți pași ai algoritmului:

Bellman-Ford(G,,s)

{

1 INIȚIALIZEAZĂ_SURSĂ(G,s)

2 pentru i→1,|V[G]|-1 execută

3 pentru fiecare muchie (u,v) E[G] execută

4 RELAXEAZA(u,v,)

5 pentru fiecare muchie (u,v) ) E[G] execută

6 dacă d[v]>d[u]+(u,v) atunci

7 returnează FALS

8 returnează ADEVARAT

}

Explicăm în continuare liniile de cod din algoritm pentru a fi mai clar cum lucrează:

1: apelam funcția de inițializare a valorilor d și

2-4: realizăm o iterație a relaxării pentru fiecare muchie în parte o singură dată

5-8: ajungem aici dupa ce am efectuat |V|-1 pași, verificăm dacă exista un ciclu de cost a negativ si întoarcem fals, altfel întoarcem adevărat.

Exemplu:

Figura 2.7:Am ilustrat pe pași evoluția agloritmului. Nodul de start este s.

Algoritmul Bellman-Ford are complexitate O(VE). Inițializarea sursei necesită O(V) timp, fiecare dintre trecerile |V|-1 prin mulțimea muchiilor inițiale necesită timp O(E).

În continuare enunțăm si demonstrăm o lemă, cu ajutorul căreia arătăm că algoritmul Bellman-Ford detectează cicluri de cost negativ, returnând drumurile minime corecte de la sursă la orice vârf [].

Lema 2.7:

Fie G=(V, E) un graf orientat ponderat, funcția de cost :E, și s V un vârf sursă. Presupunem că G nu are în componență cicluri de cost negativ accesibile din nodul sursă s. Atunci, la terminarea algoritmului Bellman-Ford avem d[v]=(s,v) pentru toate vârfurile v, accesibile din s.

Demonstrație:

Fie v un vârf astfel încât între s și v avem drum. Fie p=(v0,v1,…vk) un drum minim între aceste două vârfuri,unde v0=s și vk=v.Drumul p nu conține un vârf de mai multe ori și rezultă k|V|-1.

Demonstrăm prin inducție că pentru a i-a trecere prin muchiile lui G, i=0,1,…k, avem d[vi]=(s,vi) și această egalitate se păstrează la toate momentele de timp ulterioare. Deoarece numărul de treceri(pași) este |V|-1, stabilirea acestei proprietăți este suficientă pentru demonstrație. După inițializare avem d[v0]=(s,v0)=0 și din lema 3.4, această egalitate se menține pe tot parcursul rulării algoritmului. Pentru a demonstrarea pasului inductiv, presupunem că după a cea de a (i-1)-a trecere d[vi-1]=(s,vi-1). Muchia (vi-1,vi) este relaxată la cea de a i-a trecere, deci din lema 3.6 rezultă că d[vi]=(s,vi) după cea de a i-a trecere și la toate momentele de timp ulterioare, ceea ce încheie demonstrația .

Corolar 2.4:

Fie G=(V, E) un graf orientat ponderat, funcția de cost :E și vârful sursă s.

Atunci pentru fiecare vârf v V, există un drum minim de la s la v dacă și numai dacă prin aplicarea algoritmului Bellman-Ford asupra grafului G, vârful v este fixat( d[v]<).

Teoremă 2.2 (corectitudinea algoritmului Bellman-Ford)

Considerăm că algoritmul Bellman-Ford este aplicat unui graf orientat G=(V, E) cu costuri, cu funcția de cost :E și cu vârful sursă s. Dacă graful G nu conține cicluri de cost negativ accesibile din s atunci valoarea de adevăr returnată de algoritm este ADEVĂRAT și avem d[v]=(s,v) pentru toate vârfurile v V, iar subgraful predecesorilor G este un arbore al drumurilor minime cu rădăcină s. Altfel, dacă G ar conține cel puțin un ciclu de cost negativ, accesibil din s algoritmul Bellman-Ford ar returna FALS.

Demonstrație:

Vom presupune că în graful G vârful sursă ajunge doar la cicluri de cost pozitiv. Demonstrăm mai întâi că la terminarea algoritmului d[v]=(s,v) pentru toate vârfurile v V. Acest lucru reiese din lema enunțată si demonstrată mai sus( lema 2.7) în cazul în care există drum de la s la v, iar în caz contrar afirmația rezulta din corolarul lemei 2.4. De aici concluzionăm că în ambele situații d[v]=(s,v). G este și arbore al drumurilor minime. Acum trebuie să arătăm că Bellman-Ford returnează adevărat la final. Pentru fiecare muchie (u,v) E avem în final:

d[v] = (s,v)

(s,u)+(u,v); (lema 2.2)

= d[u]+(u,v)

d[v]= d[u]+(u,v)

Deci testul de la linia 6 a algoritmului nu va fi verificat de nicio muchie (u,v), ceea ce ne conduce la faptul că algoritmul retunează ADEVARAT.

Reciproc, presupunem că graful G, conține un ciclu c=<v0,v1,v2….vk> de cost negativ, accesibil din vârful sursă s, unde v0=vk. Rezultă urmatoarea inegalitate:

(vi-1,vi) <0. (1)

Vom presupune prin absurd că algoritmul Bellman-Ford returnează ADEVĂRAT. Rezultă că d[vi]d[vi-1]+(vi-1, vi) pentru i=1,2,…k. Aici s-a facut pentru un pas; pentru toți pașii dintr-un ciclu rezultă inegalitatea:

d[vi] d[vi-1] + (vi-1,vi)

Dar fiecare vârf din ciclu apare exact o singură dată în fiecare dintre cele două sume:

d[vi] = d[vi-1]

Din corolarul 2.3 deducem că d[vi] este finită pentru i=1,2,3….k, așa că:

0(vi-1,vi) (2)

Din inegalitățile 1) și 2) rezultă o contradicție.

În concluzie, agloritmul Bellman-Ford returnează ADEVĂRAT dacă graful G nu conține cicluri de cost negativ accesibile din sursa s și FALS în caz contrar.

În continuare voi da un exemple de aplicații practice care folosesc algoritmul Bellman-Ford.

Aceaste aplicații sunt de rutare și folosesc o variantă distribuită a algoritmului Bellman-Ford în protocolalele de rutare distanță – vector. Unul din exemple este Protocolul de Rutare a Informației(RIP). Această variantă a algoritmului constă în urmatori pași:

– fiecare nod calculează distanța de la el la toate celelate noduri și aceste rezultate sunt stocate într-un tabel

– tabelul unui nod este trimis la restul nodurilor

– în momentul în care un nod primește un astfel de tabel de la vecinii săi, calculează cele mai scurte drumuri către toate celelalte noduri și actualizează propriul tabel astfel încât să pună la dispoziția celorlalte noduri tabelul modficat.

Acest algoritm modificat, Bellman-Ford are și dezavantaje, cum ar fi măsurarea incorectă a drumului sau calcularea drumurilor minime la infinit( fapt ce se datorează transmiterii greșite a tabelelor).

În concluzie, acest subcapitol prezintă algoritmi fundamentali de determinare a drumurilor minime de sursă unică. Acești algoritmi sunt eficienți și stau la baza multor aplicații care ajută la determinarea soluțiilor optime în diferite situații.

2.2. Drumuri minime între toate perechile de vârfuri

Să considerăm un exemplu pentru a evidenția importanța determinării drumurilor minime între oricare două puncte din graf:

O firmă distribuitoare de produse de panificație într-un județ dorește să știe drumurile minime între oricare două localități pentru a consuma cat mai puțin combustibil și pentru că nu în fiecare zi are același traseu, totul depinzând de cererile cumparătorilor.

Figura 2.8

Această comanie vrea sa știe toate drumurile minime posibile.

Calculăm pentru câteva orașe:

– de la Costești la Pitești este 24 km urmând traseul Costești, Albota,Pitești

– de la Albota la Rucăr este 94 km urmând traseul Albota,Pitești,Piscani,Mioveni, Valea Mare, Rucăr

– de la Domnești la Hârtiești este 48km , iar traseul este Domnești, Piscani, Mioveni, Hârtiești.

În acest subcapitol vom rezolva această problemă a drumurilor minime între toate perechile de vârfuri ale unui graf, utilizând unul din algoritmii fundamentali, și anume Algoritmul Floyd-Warshall.

2.2.1. Algoritmul Floyd-Warshal

În știința calculatoarelor, algoritmul Floyd-Warshall( cunoscut uneori și sub denumirea de algoritmul Roy-Floyd sau algoritmul WFI, încă din anul în care acest algoritm a fost descris de către Bernard Roy(1959)) reprezintă un algoritm de analiză a grafului orientat în vederea găsirii celor mai scurte drumuri. O singură rulare a sa va determina cel mai scurt drum între toate perechile de vârfuri. Putem avea muchii de cost negativ, dar nu și cicluri negative pentru a returna un drum minim.

Algoritmul Floyd-Warshall reprezintă un exemplu de programare dinamică. El compară toate drumurile posibile din graf dintre fiecare doua noduri pentru a ajunge la soluție.

Considerăm un graf orientat ponderat G=(V, E) și de o funcție de cost :E. Pentru fiecare pereche de vârfuri u,v V a grafului vom determina distanța minimă între ele.

Algoritmul Floyd-Warshal construiește un drum minim luând în considerare și vârfurile “intermediare” din acesta. Un vârf intermediar al unui drum elementar p=<v1,v2,…vl> este oricare vârf p diferit de capetele drumului, adică un vârf din mulțimea {v2,v3,v4….vl-1}.

Fie V={1,2,…n} mulțimea vârfurilor din G. Pentru un anumit kn, considerăm submulțimea {1,2,….k}. Pentru oricare pereche de vârfuri i,j V, considerăm toate drumurile de la i la j ale căror vârfuri fac parte din mulțimea {1,2,..k}.Fie p drumul intermediar de cost minim dintre aceste drumuri.

Algoritmul Folyd-Warshal caută o relație între drumul p și drumul minim provizoriu de la i la j care este format cu vârfurile în mulțimea {1,2,…k-1}. Această relație se modifică sau nu în funcție de k, dacă poate sa fie sau nu vârf intermediar al drumului p.

Rezultă că avem următoarele cazuri pentru a ajunge la soluția algoritmului:

– Dacă vârful k nu este vârf intermediar al drumului p, rezultă că toate vârfurile intermediare ale drumului p fac parte din mulțimea {1,2,…k-1}. În concluzie, un drum minim de la vârful i la vârful j cu toate vârfurile intermediare în mulțimea {1,2,…k-1} este același cu drumul minim de la i la j cu vârfurile intermediare în mulțimea {1,2,3…k}.

-Dacă vârful k este vârf intermediar al drumului p, acesta se descompune în două drumuri

ip1 kp2 j ( ca în figura de mai jos). Din lema 3.1 observăm că p1 este drum minim de la i la k cu toate vârfurile intermediare în mulțimea {1,2,…k}. Dar p este un drum elementar, deci vârful k nu este vârf intermediar al drumului p1, rezultă că p1 este un drum minim de la 1 la k cu toate vârfurile intermediare în mulțimea {1,2,…k-1}. În mod similar arătăm că p2 este un drum minim de la vârful k la vârful j cu toate vârfurile intermediare în mulțimea {1,2,… k-1}.

toate vârfurile intermediare toate vârfurile intermediare

din {1,2,…k-1} din {1,2,…..k-1}

k

p1 p2

i j

p: toate vârfurile intermediare din mulțimea {1,2,3…..k}

Figura 2.8:Drumul p este un drum minim de la vârful i la vârful j, iar k este vârf intermediar al lui drumului p. Așadar p1 , drumul de la i la k are toate nodurile intermediare în mulțimea {1,2….k-1}. Dar si p2 care este drumul de la k la j are toate nodurile intermediare în mulțimea {1,2,….k-1}

Spre deosebire de algoritmi de drum minim cu sursă unică, în care reprezentarea grafului se facea prin listă de adiacență, algoritmii care determina drumurile minime între toate nodurile grafului folosesc matricea costurilor. Aceasta se notează W, de dimensiune n*n, iar fiecare element reprezintă costul muchiei grafului G=(V,E) având n vârfuri. Mai pe scurt W=(ij) unde

0 , dacă i=j

ij = costul arcului (i,j) , dacă i≠j și (i,j)E

R , dacă i≠j și (i,j)E

Deducem o formulă recursivă a estimărilor drumurilor minime. Notăm cu d(k)ij drumul minim de la i la j cu toate vârfurile intermediare în mulțimea {1,2,…k}. În momentul în care k=0, drumul de la i la j nu are niciun vârf intermediar. Rezultă că acest drum conține cel mult un arc, deci d(0)ij = ij.

Definiția recursivă a lui d(k)ij este următoarea:

ij ,dacă k=0

d(k)ij =

min(d(k-1)ij , d(k-1)ik + d(k-1)kj) ,dacă k1.

Matricea D(n) = (d(n)ij) este rezultatul, d(n)ij = (i,j), pentru orice i,j V, pentru că toate vârfurile intermediare se află în mulțimea {1,2….n}.

Procedura următoare se bazează pe recuranța definită mai sus și determină valorile lui d(k)ij în ordinea valorilor crescătoare k. La intrare, avem matricea W cu dimensiunea n*n. Procedura returnează matricea D(n) a costurilor de drumuri minime dintr-un graf orientat

G = (V, E).

Definiția procedurii:

Floyd-Warshall(W)

1 D(0) ←W

2 pentru k ← 1,n execută

3 pentru i ← 1,n execută

4 pentru j ← 1,n execută

5 d(k)ij ← min(d(k-1)ij , d(k-1)ik + d(k-1)kj)

6 returnează D(n)

Complexitatea algoritmului Floyd-Warshall O(n3), pentru că are trei cicluri repetitive (liniile 2-4) .

Construirea drumului minim cu algoritmul Floyd-Warshall

Construirea drumului se face cu ajutorul matricei D a costurilor drumurilor minime, apoi cu matricea a predecesorilor.

Pentru a genera matricea , trebuie să construim un șir de matrici (0),(1),(2)….(n) , unde (n)=, iar ij(k) este definit ca fiind predecesorul vârfului j în drumul minim de la vârful i cu toți predecesorii în mulțimea {1,2,….k}.

Avem următoarea formulă recursivă pentru ij(k) :

– Dacă k=0, orice drum minim de la i la j nu are vârf intermediar și rezultă:

NIL ,dacă i=j sau ij=

ij(0)=

i ,dacă ij sau ij<.

– Dacă k1. Considerăm drumul i k j și observăm că predecesorul lui j pe drumul minim de la i la j este același cu predecesorul ales pe un drum minim de la k la j cu toate vârfurile intermediare în mulțimea {1,2….k-1}. Obținem urmatorul sistem pentru k1:

ij(k-1) ,dacă d(k-1)ij d(k-1)ik + d(k-1)kj

ij(k) =

kj(k-1) ,dacă d(k-1)ij > d(k-1)ik + d(k-1)kj.

Exemplu:

Figura 2.9:Șiruri e de matrice D și determinate de Alogoritmul Floyd-Warshal.

Algoritmul Floyd-Warshall în cazul ciclurilor negative

Pentru un rezultat numeric semnificativ al algoritmul Floyd-Warshall se presupune că nu există cicluri. Totuși, dacă acest lucru se întâmplă, Floyd-Warshall poate fi folosit pentru identificarea acestora. Dacă se rulează algoritmul încă o dată, unele drumuri pot scădea, însă nu se garantează că între toate vârfurile drumul corespunzător va fi afectat de aceeași manieră. Un număr de pe diagonală matricei drumului este negativ dacă și numai dacă vârful corespunzător acestui număr aparține unui ciclu negativ.

Algoritmul Floyd-Warshall se poate folosi și în rezolvarea altor algoritmi, cum ar fi:

– algoritmul Gauss-Jordan (Inversarea matricilor reale)

– algoritmul lui Kleene (ajută la găsirea unei expresii regulate, indicând limbajul regulat, acceptat de către un automat finit)

În concluzie algoritmul Floyd-Warshal determină toate drumurile minime între oricare două noduri ale grafului, dar timpul său de execuție este O(n3).

3. Drumuri minime rezultate cu ajutorul algoritmilor euristici de explorare

În acest capitol vorbim despre algoritmi de explorare care se bazează pe tehnica căutării. Aceasta este de două feluri, neinformată sau informată.

Căutarea neinformată descoperă drumului de la starea țintă la nodul ‚scop’ făra să știe nicio informație legată de numărul de pași pe care trebuie să îi urmeze sau despre costul drumului. Nodul ‚scop’ nu îl cunoaște, el este descoperit în timpul rulării.

Căutarea informată se mai numește și căutare euristică. Acest timp de căutare se bazează pe cunoașterea de informații cum ar fi nodul scop, numărul de pași care trebuie urmați, costul drumului, pe scurt cunoștiințe specifice problemei ce trebuie rezolvate. Toate acestea definesc noțiunea de spațiul al stărilor.

Euristica este o metodă de studiu și de cerectare care stă la baza descoperirii unor noi fapte, explorând toate soluțiile posibile.

Algoritmi euristici de explorare se bazează pe tehnica căutării euristice și întorc soluție pentru problemele mult prea complexe, cu foarte multe calcule, pentru care un algoritm fundamental este foarte lent. De exemplu algoritmul Dijkstra necesită foarte mult timp pentru a detemina drumul minim de la un nod sursă peste un graf foarte mare, comportându-se nesatisfăcător. Prin graf mare putem înțelege un graf infinit.

Algoritmii euristici de explorare întorc soluția optimă într-un timp satisfăcător. De exemplu pot fi folosiți în probleme de planificare, în proiectarea circuitelor VSLI, robotică, proiectarea agenților inteligenți.

Acest capitol se axează pe descrierea modului de funcționare a celui mai cunoscut și folosit algoritm euristic, A* și pe modelarea problemelor sub forma grafurilor de stări.

3.1. Algoritmul A*

Algoritmul A* este un algoritm euristic, de căutare care determină o soluție optimă cu ajutorul unei aproximari de la nodul curent la cel final, fiind o soluție a problemelor de drum minim. Algoritmul A* determină costul estimat în fiecare vârf al grafului prin suma a două valori, prima este cea a distanței reale dintre nodul de start și nodul pe care ne aflăm , iar cea de a doua este reprezentată de aproximarea distanței de la nodul în care ne aflăm până la nodul sursă (se poate imagina o muchie care leagă aceste noduri iar aproximarea reprezintă costul acesteia). Algoritmul are soluție în momentul în care costul estimat este cel mai mic, iar valorea aproximării distanței este zero .

Notațiile folosite în construirea, analizarea și demonstrarea algoritmului sunt urmatoarele:

– G=(V, E) reprezintă graful asociat, unde V sunt vârfurile, iar E sunt muchiile.

– n0 este nodul de start, asocit stării inițiale a problemei

– mulțimea Open este formată din nodurile explorate(frontiera între zona cunoscută și cea necunoscută)

– mulțimea Closed este formată din nodurile expandate( mulțimea nodurilor cunoscute)

– V reprezintă mulțimea nodurilor soluție. Un nod soluție este notat cu y

– g(n) reprezintă costul drumului de la n0 la n în momentul curent de timp în curs de execuție

– gp(n) reprezintă costul final al drumului de la n0 la n pe un traseu cunoscut p

– h(n) 0 este costul estimat al drumului optim(de cost minim) de la nodul n la orice nod din mulțimea soluțiilor, y. Cunoaștem că h(y)=0, y

– f(n) reprezintă costul estimat pe întregul drum de la nodul de start pana la un nod soluție favorabil, trecând printr-un nod n. Nodul n este descoperit de algoritm la momentul curent de timp în cursul execuției, formând cu n0 drum

– g*(n) reprezintă costul exact al drumului optim n0…n

– h*(n) este funcția euristică și reprezintă costul exact a porțiunii n…y, din drumul optim n0…n…y, unde y este cel mai favorabil nod din .( h*(n) = min(cost(n…y)| y))

– f*(n) = g*(n) + h*(n) reprezintă costul exact al unui drum optim n0…n….y, pentru cel mai favorabil y din .

– c = min { f*(y) | y} reprezintă costul exact al unui drum optim n0…..y.

– (n) reprezintă adresa către predecesorul lui n pe drumul n0…n descoperit de algoritm pana la momentul curent de timp în cursul execuției.

– c(n,n’) trebuie sa fie pozitiv strict și reprezintă costul muchiei (n,n’)

Observație 1: Un drum cu costul f*(n), riscă ca drumul n0…y să nu fie optim, însă cu siguranță este cel mai bun drum care trece prin vârful n pana la vârful soluție. Deci costul c este soluție optimă.

Observație 2: Pentru fiecare nod n din Open și Closed, n conține în mod explicit informația (n), g(n) și f(n). Pe h(n) nu o conține fiincă ea este calculată daca este nevoie.

În urmatoarea figură este prezentat modul cum lucrează A* cu informația:

Figura 3.1

Pseudocodul algoritmului A* :

A*(Stare_initiala,h,test_solutie)

{

n0 = construcție_nod(Stare_inițială)

f(n0) = h(n0)

g(n0) = 0

(n) = NIL

OPEN = {n0}

CLOSED =

cât timp OPNE ≠ execute

nod = selecție_nod (OPEN)

dacă ( test_soluție(nod)) atunci

returnează nod

OPEN = OPEN \ {nod}

CLOSED = CLOSED {nod}

succ = expandează(nod)

repetă până când ( succ_nod succ)

{

g_succ_nod= g(nod) + c(nod, succ_nod)

f_succ_nod= g_succ_nod + h(succ_nod)

dacă succ_nod CLOSED OPEN atunci

{

OPEN = OPEN {succ_nod} // am descoperit un nod nou

g(succ_nod) = g_succ_nod

f(succ_nod) = f_succ_nod

(succ_nod) = nod

}

altfel

dacă g_succ_nod< g(succ_nod) atunci

{

g(succ_nod) = g_succ_nod

f(succ_nod) = f_succ_nod

(succ_nod) = nod

dacă succ_nod CLOSED atunci

{

CLOSED = CLOSED \ {succ_nod} //nodul succ_nod este redeschis

OPEN = OPEN {succ_nod}

}

}

}

returnează 0

}

Funcția selecție_nod alege nodul care are costul minim dintre estimările drumului întreg.

Algoritmul modelează pointeri (n) în ordinea cea mai corectă pentru a găsi cel mai favorabil nod de final y. Nodul soluție găsit este determinat de funcția euristică h(n).

La pași urmatori presupunem că mulțimea nodurilor soluție este nevidă și orice nod din aceasta este accesibil din orice alt vârf al grafului.

Voi da un exemplu practic si voi prezenta modul cum lucrează algoritmul A*

Figura 3.2 [14]

Avem următoarea hartă și vrem să calculăm drumul minim de la Arad la București. Cunoaștem distanțele dintre orașe.

Pasul 1:

Nodul inițial este Arad care costul optim egal cu valoarea costului aproximat până la nodul destinație

Pasul 2:

Nodul inițial este expandat, iar fiecărui nod succesor ii se atribuie un cost egal cu suma dintre costul real al drumului de la acesta la nodul de la care s-a expandat, împreună cu estimarea costului de la nodul fiu la nodul sursă. Alegem nodul Sibiu pentru a fi expandat la pasul următor pentru că are costul cel mai mic.

Pasul 3:

Nodul Sibiu se expandează la rândul său, fiecărui nod succesor atribuindu-se costul propriu. Apoi alegem ca următorul nod expandat să fie Râmnicu Vâlcea, însă vom expanda și nodul Făgăraș fiincă are valorea funcției euristice foarte apropiată de cea a celuilalt nod și este posibil să se formeze drum și pe acel traseu.

Pasul 4:

Am expandat nodul Râmnicu Vâlcea, acum urmează Făgăraș

Pasul 5:

Am expanda nodul Făgăraș și am dat de nodul București prin expandare. Însă acesta are o valoare euristică mai mare decât costul nodului Pitești de pe cealaltă traiectorie de explorat f*(nod(Bucuresti)) = 450 > f*(nod(Pitesti)) = 417. Algoritmul nu se oprește, își continuă rularea fiindcă este posibil să existe un drum mai bun din nodul Pitești către nodul București.

Pasul 6:

După ce și nodul Pitești a fost expandat, unul dintre nodurile succesor este București, care are costul cel mai minim, ceea ce rezultă că am descoperit drumul minim de la nodul inițial Arad, către nodul sursă București, pe traseul Sibiu, Râmnicu Vâlcea, Pitești. Algoritmul se termină în acest moment.

Urmatoarea teoremă verifică în ce condiții algoritmul A* este complet:

Teoremă 3.1:

Algoritmul A* este complet, chiar dacă graful explorat nu este finit.

Demonstrație:

Știm că un algoritm este complet dacă descoperă o soluție atunci când problema acceptă soluție. Considerăm că în graful explorat de A*, avem un nod y, din mulțimea soluțiilor care este accesibil pe o cale parțial descoperită n0 … y de cost f(y). Dar observăm că algoritmul nu se termină niciodată. Deducem că A* urmează cel puțin un drum infinit, notat cu D. Costul drumului acesta crește monoton, fiindcă întâlnește numai muchii cu cost pozitiv( funcția f). Atunci există un momnet în care costul f(n’) al unui nod n’ din D depășește f(y), așadar în acel moment nodul n’ nu mai este selectat pentru expansiune, iar drumul D nu mai este folosibil.

Rezultă că A* se termină într-un moment, iar acel moment este când selectăm un nod soluție din mulțimea OPEN.

Lema 3.1:

Fie p=n0,n1….nm un drum oarecare în graful explorat de A*, care la un moment anume T, toate nodurile din p sunt în CLOSED. Rezultă că la orice moment de timp egal sau mai mare ca T, avem inegalitatea g(ni)gp(ni), unde i ia valori de la 0 la m .

Demonstrație:

Pentru a face demonstrația acestei leme avem nevoie de inducție matematică după indicele i cu proprietatea:

Prop(i) = def (j0…i | [nj CLOSED] la momentul T)

Rezultă că pentru același j avem g(nj)gp(nj) la orice moment T.

Inducție:

– Pentru i=0. Nodul n0 este primul nod expandat de A*. Din defințiile de mai sus ale lui g și gp rezultă că g(n0) = gp(n0) = 0. Adevărat.

-Pentru 0 i m. Considerăm că Prop(i) este adevărată și trebuie să demonstrăm că Prop(i+1) este adevărată.

Știm că ni este în CLOSED la momentul T, rezultă că există un moment T’ < T la care nodul ni este expandat ultima oară în intervalul de timp [0,T] și apoi rămâne în CLOSED în perioada de timp [T,T’].

La momentul T’ trebuie sa avem urmatoarea ineglitate g(ni) gp(ni) , dar ipoteza inductivă va fi contrazisă și mai avem nodul ni+1 care este descoperit din ni.

Din algoritmul A* avem urmatoarele două proprietăți:

1) ni+1 OPEN CLOSED, în momentul T’ când ni+1 este descoperit din ni

g(ni+1) = g(ni) + c(ni,ni+1)

g(ni+1) gp(ni) + c(ni,ni+1) = gp(ni+1)

2) ni+1 OPEN CLOSED, în momentul T’ când ni+1 este descoperit din ni

Fie g’(ni+1) valoarea g curentă a nodului ni+1.

Din algoritmul A* rezultă:

g(ni+1) = min { g(ni)+ c(ni,ni+1) , g’(ni+1)}

g(ni+1) g(ni) + c(ni,ni+1)

g(ni+1) gp(ni) + c(ni,ni+1) = gp(ni+1)

Din algoritmul A*, g(ni+1) nu se poate modifica în timpul rulării algoritmului. Rezulă g(ni+1) gp(ni+1) la orice moment de timp după T’ și nici șadar proprietatea P(i+1) este adevărată.

Corolarul 3.1:

Fie p=n0,….n’,n un drum în graful exploatat de A*, astfel încât la un moment T al explorării toate nodurile din porțiunea n…n’ a căii drumului p sunt în CLOSED, iar n în mulțimea OPEN. Rezultă g(n) gp(n), în orice moment de timp egal sau superior lui T.

Definiția 3.1:

Funcția euristică h este admisibilă dacă pentru orice nod n din spațiul stărilor h(n) h*(n). Reformulat deducem că o euristică admisibilă h este optimistă și h(y)=0 pentu orice y.

Lema 3.2:

Dacă A* folosește o euristică h admisibilă, atunci în orice moment înaintea terminării algoritmului, există un nod nOPEN astfe încât f(n) c.

Demonstrație:

Fie un nod n OPEN ce aparține unei căi optime p=n0…n’,n….y, unde y iar costul f*(n)=c astfel încât toate nodurile din porțiunea n0…n’ a drumului p se află în mulțime p. Observăm că nodul n se află sigur în drum fiindcă nodul y nu este în mulțimea CLOSED. Din Corolarul 1) g(n) gp(n) = g*(n). Dar g*(n) reprezintă costul minim a drumui n0…n, totul se reduce la g(n) = g*(n).

Costul lui f(n) este :

f(n) = g(n) + h(n) = g*(n)+h(n)

f(n) g*(n)+h*(n) = f*(n) = c.

Teorema 3.2:

Algoritmul A* este ghidat printr-o euristică admisibilă ce descoperă soluția optimă dacă există soluții.

Demonstrație:

Presupunem că A* are nod final pe n’, astfel încât f(n’) >c. Din lema 4.2 știm că înaintea terminării A* există cel puțin un nod n OPEN cu proprietatea f(n)c<f(n’). Atunci A* nu poate selecta pe n’ pentru expansiune.

Rezultă că A* nu se poate termina cu o soluție al cărei cost este mai mare decât c.

Complexitate algoritm A*

Algoritmul A* rezolvă majoritatea problemelor pe care alți algoritmi nu reușesc, însă consumă resurse importante de spațiu și timp. Este un algoritm euristic admisibil care asigură optimalitatea soluției. Alte două caracteristici ale algoritmului ce îl fac eficient sunt monotonia și dominanța.

În urmatoarea parte voi trata legatura dintre precizia euristică a algoritmului și puterea de rezolvare .

Din definiția algoritmului și a euristicii, euristica h este cu atât mai bună cu cât favorizează mai mult expandarea nodurilor pe căile optime n0…y, ceea ce determină o soluție liniară. Așadar, putem estima calitatea euristicii folosite cu ajutorul ordinului efectiv al grafului explorat.

Definiție 3.2:

Fie N numarul total de noduri expandate din A* până la determinarea unei soluții y, iar d numărul de muchii de pe drumul descoperit de algoritm, n0…y. Notăm cu b* ordinul efectiv al grafului explorat, numărul de muchii care ies din fiecare nod al unui arbore echilibrat cu N noduri și înălțime d+1.

b*d , deci b* N1/d

O euristică este mai eficientă cu cât valoarea b* este mai mică. B* este determinat pentru a micșora numărul de noduri expandate A*.

În cazul cel mai defavorbil, dacă spațiul de căutare începe să crească exponențial erori( |h(n) – h*(n)| ) euristice față de distanța reală, atunci soluția are o creștere sub-exponențială:

| h(n) – h*(n) | O(log h*(n))

Însă în majoritatea cazurilor crește liniar cu distanța până la soluție, ceea face algoritmul să devină mare consumator de timp și memorie ( memorăm mulțimea CLOSED a nodurilor ). În acest caz h(n)=h*(n) și toate nodurile sunt expandate pe un drum minim. În acest caz ideal, rezultatul poate fi generalizat pentru orice eurisitcă ce satisface | h(n) – h*(n) | , unde este o constantă mai mare ca zero.

4. Aplicație: Drumuri minime în rețele de transport

Minimum path subway

4.1 Descrierea aplicației

Minimul path subway este o aplicație web destinată publicului larg și are drept scop găsirea drumului minim între două stații de metrou dintr-o magistrală a unui oraș. Aplicația are în baza de date multe hărți de metrou pentu a putea fi folosită de toți oamenii din diferite părți ale lumii.

În momentul în care un utilizator va dori să afle drumul cel mai scut între stații, el accesează pagina principală(Default) pentru a-și alege țara și orașul dorit urmând să i se deschidă altă pagină, cea cu harta metroului corespunzătoare orașului ales unde va trebui să aleagă stația de plecare(apăsând click pe hartă în dreptul acesteia) și stația destinație (făcând același procedeu ca la stația de plecare). Pe hartă vor aparea două puncte de culori diferite verde, respectiv roșu care indică stațiile căutate.

Apoi apăsând pe butonul din josul paginii va apărea drumul minim căutat, indicându-se stațiile și magistralele pe care omul interesat trebuie să le străbată.

Însă, se vor afișa două drumuri și un număr de secunde în dreptul fiecăruia. Acest lucru este evidențiat în scop didactic, harta de metrou fiind considerat un graf și vrem să observăm cum lucrează doi algoritmi diferiți, unul de specific de căutare a drumului minim Dijkstra, iar altul A*, care este un algoritm euristic și este adaptat pentru a căuta un drum minim. Timpul necesar determinării drumului minim utilizând A* este mai mic decât cel determinat de Dijkstra. Aplicația este uzabilă fiind ușor de folosit pentru toți membrii site-ului.O altă caracteristică este disponibilitatea, putând fi accesată de orice utilizator în orice moment.

4.2 Structura aplicației

1) Pagina de Administrator(Mapping). Această pagină oferă posibilitatea persoanei cu drepturi specifice să facă modificări site-ului, adăugând, șterge sau editând țări, orașe, hărți de metrou, magistralele unei hărți, dar și stațiile.

Adăugarea unei hărți se rezumă la încărcarea unei imagini a unei rețea de metrou corespunzătoare orașului selectat în prealabil. În momentul în care vrem să adăugăm magistrale, imagine hărții este încărcată pentru a ușura acest lucru.Același mecanism se întâmpla și la adăugarea de stații și a conexiunilor dintre ele. Când selectăm o magistrală, adăugăm stațiile corespunzătoare în baza de date imediat după dăm click pe imagine. Va aparea un cerc în dreptul său si apoi sub imagine vom avea o casetă text unde îi putem scrie denumirea. Când selectăm mai multe stații dintr-o magistrală se creează casetele textbox corespunzătoare. Utilizatorul nu va face confuzie între ele deoarece atunci când dorește să scrie numele stației într-o casetă, cerculețul corespunzător stației se va colora diferit. Conexiunile dintre stații se fac asemănător cu procesul de adăugare a stațiilor, putând selecta două dintre ele apărând în casetele text ale acestora numele lor împreună cu distanța. În momentul în care avem pasaj, considerăm două stații diferite aflându-se pe două magistrale diferite, dar distanța o considerăm zero. În restul situațiilor distanța va fi considerată unu.

Aplicația se bazează pe ideea a găsirii drumul cel mai scurt cu numar minim de stații.

Figura 4.1: Introducerea staților în baza de date

Figura 4.2 : Introducerea conexiunilor între stații

2)Pagina de Start(Default) este creată pentru a informa utilizatorul asupra scopului aplicației. Aceasta este menită să ajute persoana care accesează site-ul în găsirea drumului minim într-o rețea de metrou.

Utilizatorul poate alege țara și orașul căutat, direct din această pagină, urmând să apese pe butonul din pagină pentru a-l direcționa la pagina următoare.

3)Pagina Hărții și Drumului(MAP) are drept scop găsirea drumului minim din rețea de metrou a orașului selectat în prealabil de utilizator. Acesta este îndrumat să aleagă din imagine cele două stații dorite( de plecare și de sosire) printr-un click cu mouse-ul pe hartă.

Dacă cele două puncte sunt alese corect, apasă butonul GET PATH, iar drumul minim este afișat. Acesta este format din stațiile și magistralele pe care se află fiecare stație.

Cum am precizat și în descrierea aplicației, afișarea a două drumuri nu trebuie să fie considerată o eroare a aplicației. Folosirea a doi algoritmi cu caracteristici diferite evidențiază diferența dintre timpul de execuție al fiecăruia.

Figura 4.3: nodul de start este colorat cu verde pe hartă, iar cel destinație cu roșu.

Figura 4.4: Drumul minim rezultat între cele două noduri. Sunt ajușate și pasajele pentru a putea observa utilizatorul pe ce majistrale trebuie să urmeze.

4.3 Tehnologii folosite în creearea aplicației

În acest subcapitol voi enumera și defini tehnologiile folosite în alcătuirea acestei aplicații web:

4.3.1 Tehnologii folosite pe partea de server

Server-ul Web folosit este IIS Express 8.0.( Internet Information Services)

Baza de date este SQL Express LocalDB. Baza de date a aplicației este formată din 5 tabele (Country, City, Throughfare, Station și StationConnection) legate între ele cu ajutorul cheilor străine (Froeign Key) după schema de mai jos:

Pentru partea de logică de pe server, în aplicație folosesc C# împreună cu .NET.Framework 4.5. C# este un limbaj de programare modern, orientat pe obiecte, care oferă posibilitatea construirii rapidă a aplicațiilor pe platforma Microsoft .Net, fiind creat special pentru aceasta. Bibliotecile utilizate de C# sunt cele definite de arhitectura .Net.

.Net permite dezvoltarea și execuția aplicațiilor pe platformă, dând posibilitatea programatorului să amestece diferite limbaje de programare, dar oferindu-le securitate și portabilitatea programelor. Legat de C#, arhitectura .Net definește două entități foarte importante. Prima este reprezentată de motorul de căutare (este sistemul care se ocupă de execuția programelor) , iar cea de a doua este biblioteca de clase .Net ( cu ajutorul acesteia programul are acces la mediul de rulare). Prin biblioteci (librării) înțelegem o mulțime de unități binare reutilizabile în runtime, care oferă un set de funcționalități standard, având un scop bine definit.

Pentru accesul și la lucrul cu baza de date se folosește Entity Framework versiunea 5. Prin framework înțelegem ceva mai mult decât o librărie în care aplicația face doar apeluri, preluând controlul aplicației.

Pentru generarea paginilor web, folosesti ASP.NET 4.5. Se creează un șablon ASP.Net Web Aplication care automat generează fișierele de bază necesare începeri unei noi pagini din aplicație.

4.3.2 Tehnologii folosite pe partea de client

Pentru designul aplicației folosesc HTML 5 și CSS 3, împreună cu jQuery care este un framework de javascript.

HTML(HyperText Markup Language) este un limbaj de programare utilizat pentru crearea paginilor web ce pot fi afișate într-un browser, oferind utilizatorului o interfață simplă și ușor de folosit.

CSS(Cascading Style Sheets) este în strânsă legatura cu limbajul HTML, reusind să formateze elementele acestuia. CSS este un limbaj care definște Layout-ul pentru documetele HTML, creeând un aspect al site-ului plăcut ochiului utilizatorului.

4.4 Detalii aplicație

Aplicația este împărțită în patru părți importante:

-prima, Bachelor.Business se ocupă de aplicarea algoritmilor și a modului cum trebuie să funcționeze aplicația. Are în componența sa patru clase, printre care două ale algoritmilor de bază a aplicației , Dijkstra și A*, iar celelalte două clase au încorporate mai multe metode care ajută la manipularea datelor în aplicație.

Cele două clase sunt :

public class DataManager și

public class FileManager

Exemplu de metode din aceste două clase:

public static List<City> GetCities(int countryId) metoda returnează lista orașelor unei țări.

public static Thoroughfare GetThoroughfare(int stationId) metoda returnează magistrala pe care se află stația din drumul minim returnat.

public static void AddStation(int thoroughfareId, string stationName, string areaCoordinates) cu ajutorul acestei metode adaug din pagina de administrator stații(puncte) în baza de date.

-a doua, Bachelor.DataAccess se ocupă cu oferirea accesului la baza de date și la intermedierea cererilor metodelor din Bachelor.Business

-cea de a treia, Bachelor.Database reprezintă baza de date a aplicației. Permite să se stochez script-urile care generează baza de date după care acestea putând fi trimise să se execute pe server.

-a patra este Bachelor.Web și face referință doar la partea de web, de interfață. În interiorul acesteia se gaăsesc cele trei pagini(Administrator, Home și Drum minim) împreuna cu elemntele ce realizează interfața.

Perspectiva fizică a aplicației este descrisă de mediul în care urmează să funcționeze aplicația(prin mediu înțelegând elemente de rețea , hardware și software de bază). Pentru a descrie această perspectivă voi folosi o digrama de dyployment UML:

În concluzie, aplicația Minimul path subway are utilizare fixă în practică, conturându-se asupra unei singure idei, aflarea drumului minim. Este utilă, putem afla distanța minimă între oricare două stații de metrou dintr-un anumit oraș, într-un timp scurt.

Făcând o comparație între site-urile care au scop comun cu aceasta, aplicația este mai simplă, interacționând cu utilizatorul într-un mod plăcut și reușiind să îi atragă atenția pentru a mai reveni. Celelate aplicații concurente sunt mai stufoase, durând destul timp pentru a găsi pagina, apoi pentru a găsi stațiile dorite.

De exemplu în acesată aplicție, stația de start și cea de final sunt alese de utilizator de pe o hartă complexă, printr-un simplu click, pe când într-un site trebuie căutate cele două stații într-o listă. Acest lucru este incomod pentru utilizator, nu îi oferă o privire de ansamblu a hărții pe care trebuie să o străbată, iar în cazul în care o rețea de metrou este foarte mare găsirea unei stații devine imposibilă.

Bibliografie:

[1]. Ravindra K. Ahuja,Thomas L. Magnanti,James B. Orlin, NETWORK FLOWS

[2]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to algorithms, Editura The MIT Press Cambridge, McGraw-Hill Book New York, 2000.

[3]. Cristian A. Giumale, Introducere in analiza algoritmilor, Editura Polirom, 2004.

[4]. F. Hristea, M.F. Bâlcan, Căutarea și reprezentarea cunoștințelor în inteligența artificială. Teorie și aplicații ,Editura Universitații din București, 2005.

[5]. M. Dârdală, I. Smeureanu, Tehnologii de Acces la Date, ASP.NET, Editura ASE, București, 2008.

[6]. Dragoș Radu Popescu, Combinatorică si teoria grafurilor, Editura Societatea de ștințe matematice din România, 2005.

[7]. H. Schildt, C# ,Editura Teora, 2008.

[8]. Ioan Tomescu, Probleme de combinatorică și teoria grafurilor, Editura Didactică și Pedagogică, 1981.

[9]. Dijkstra's algorithm, Wikipedia, 2014, (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

[10]. A* search algorithm, Wikipedia, 2014 (http://en.wikipedia.org/wiki/A*_search_algorithm).

[11]. Bellman–Ford algorithm, Wikipedia 2014, (http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)

[12]. Floyd–Warshall algorithm, Wikipedia 2014, (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)

[13]. Teoria grafurilor, Wikipedia, 2014 (http://ro.wikipedia.org/wiki/Teoria_grafurilor)

[14]. http://elf.cs.pub.ro/pa/wiki/laboratoare/laborator-11

Bibliografie:

[1]. Ravindra K. Ahuja,Thomas L. Magnanti,James B. Orlin, NETWORK FLOWS

[2]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to algorithms, Editura The MIT Press Cambridge, McGraw-Hill Book New York, 2000.

[3]. Cristian A. Giumale, Introducere in analiza algoritmilor, Editura Polirom, 2004.

[4]. F. Hristea, M.F. Bâlcan, Căutarea și reprezentarea cunoștințelor în inteligența artificială. Teorie și aplicații ,Editura Universitații din București, 2005.

[5]. M. Dârdală, I. Smeureanu, Tehnologii de Acces la Date, ASP.NET, Editura ASE, București, 2008.

[6]. Dragoș Radu Popescu, Combinatorică si teoria grafurilor, Editura Societatea de ștințe matematice din România, 2005.

[7]. H. Schildt, C# ,Editura Teora, 2008.

[8]. Ioan Tomescu, Probleme de combinatorică și teoria grafurilor, Editura Didactică și Pedagogică, 1981.

[9]. Dijkstra's algorithm, Wikipedia, 2014, (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

[10]. A* search algorithm, Wikipedia, 2014 (http://en.wikipedia.org/wiki/A*_search_algorithm).

[11]. Bellman–Ford algorithm, Wikipedia 2014, (http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)

[12]. Floyd–Warshall algorithm, Wikipedia 2014, (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)

[13]. Teoria grafurilor, Wikipedia, 2014 (http://ro.wikipedia.org/wiki/Teoria_grafurilor)

[14]. http://elf.cs.pub.ro/pa/wiki/laboratoare/laborator-11