Drumuri Optime intr-un Graf

Extras din referat Cum descarc?

In marea majoritate a problemelor care pot fi modelate prin grafuri nu ne intereseaza numai daca exista sau nu legaturi intre componentele reprezentate prin nodurile grafului ci si intensitatea acestora. Aceasta intensitate are semnificatia unei valori numerice (pozitive sau negative) asociate arcului corespunzator legaturii a carei intensitate o masoara. 
In aplicatiile economice aceasta valoare poate fi:
- lungimea drumului dintre doua localitati;
- costul parcurgerii rutei reprezentate prin arcul corespunzator;
- durata parcurgerii rutei respective;
- cantitatea transportata pe ruta respectiva;
- capacitatea maxima a rutei respective;
- castigul realizat prin trecerea de la o stare la alta a sistemului;
- consum de energie pentru efectuarea trecerii respective;
- punctaj realizat etc.
Una din problemele care poate aparea in aceste situatii este gasirea, pentru o anumita pereche de noduri (sau mai multe perechi), a drumului optim intre acestea.
Pentru formalizarea problemei vom introduce notiunea de valoare a unui drum, care este egala cu suma valorilor arcelor care il compun. Vom nota in continuare valoarea unui arc (xi,xj) cu v(x!i,xj) sau cu vij, drum minim l(dm) = min (d(x!1,xn)) , oricare d U si drum maxim l(dM) = maz (d(x!1,xn)) oricare d U In aceste conditii putem enunta problema drumului optim astfel:
"Dat un graf G = (X,U) si o functie care asociaza fiecarui arc o valoare reala, sa se gaseasca, pentru o pereche data de noduri, drumul (drumurile) de valoare optima (minima sau/si maxima) intre cele doua noduri si valoarea acestuia (acestora)"
Deoarece este vorba de gasirea minimului unei multimi de numere reale, prima intrebare care se pune este daca aceasta admite minim. Daca multimea nodurilor grafului este infinita atunci pot exista o infinitate de drumuri elementare distincte intre cele doua noduri si multimea valorilor acestora poate avea orice forma (inchisa sau nu, marginita sau nu) devenind foarte greu de caracterizat cazurile cand minimul dorit exista. Deoarece totusi majoritatea covarsitoare a problemelor economice se modeleaza prin grafuri cu numar finit de noduri, ne vom limita in continuare doar la acestea.
Un numar finit de noduri n atrage dupa sine existenta unui numar finit de arce (cel mult n2) si a unui numar finit de drumuri elementare ( cel mult nxn!x ). Deoarece oricarui drum d ii corespunde un drum elementar de (obtinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricarui drum ca suma intre valoarea drumului elementar corespunzator si valorile unor subcircuite ale sale, fiecare inmultita cu numarul de parcurgeri ale circuitului respectiv.
In concluzie, daca exista un circuit de valoare negativa inseamna ca exista drumuri de valoare oricat de mica (cele care contin acest circuit), obtinuta prin parcurgerea acestuia de oricate ori dorim si, deci, multimea valorilor drumurilor este nemarginita inferior, neexistand drum de valoare minima. Daca exista un circuit de valoare pozitiva atunci exista drumuri de valoare oricat de mare si multimea valorilor drumurilor este nemarginita superior, neexistand drum de valoare maxima.
Daca nu exista circuite de valoare negativa atunci valoarea oricarui drum este mai mare sau egala cu a drumului elementar corespunzator, deci drumul de valoare minima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor) va avea minorant si am lamurit problema compatibilitatii problemei. Analog, daca nu exista circuite de valoare pozitiva atunci valoarea oricarui drum este mai mica sau egala cu a drumului elementar corespunzator, deci drumul de valoare maxima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor), va avea majorant.
Obs. 1. Daca in graf nu exista decat arce de valoare pozitiva atunci exista drum de valoare minima.
Obs. 1. Daca in graf nu exista decat arce de valoare negativa atunci exista drum de valoare maxima.
Obs. 1. Daca in graf nu exista circuite atunci exista si drum de valoare minima si drum de valoare maxima.
Deoarece din cele de mai sus se sesizeaza importanta existentei circuitelor intr-un graf vom da in continuare un algoritm de depistare a existentei circuitelor intr-un graf: ( un drum in care nodul initial si cel final coincid este un circuit )
Pasul 1. Se construieste multimea A formata din nodurile pentru care toate arcele incidente sunt incidente spre interior ( noduri in care toate arcele "intra" sau, altfel spus, noduri din care nu "pleaca" nici un arc).
Pasul 2. Se gasesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealalta extremitate in A (noduri din care se poate "ajunge" doar in A). Daca nu exista nici un astfel de arc se trece la pasul 4.
Pasul 3. Se adauga arcele gasite la pasul 2 la multimea A apoi se reia algoritmul de la pasul 2, pentru noua multime A.
Pasul 4. Daca A contine multimea tuturor nodurilor atunci graful nu contine circuite. Daca au ramas noduri in afara lui A atunci graful contine circuite.
Algoritmi de gasire a drumului optim
Din cauza varietatii nelimitate a grafurilor posibile, nu exista un algoritm care sa rezolve orice problema in timp util, dar s-au elaborat o multime de algoritmi, fiecare fiind cel mai eficace in anumite cazuri. Acesti algoritmi pot fi grupati in cinci categorii:
1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);
2. Algoritmi prin ajustari succesive: (Ford);
3. Algoritmi prin inductie (Dantzig);
4. Algoritmi prin ordonare prealabila a varfurilor grafului;
5. Algoritmi prin extindere selectiva (Dijkstra).
A. Algoritmul lui Bellman - Kalaba (formulare teoretica si algoritm de rezolvare)
Algoritmul se aplica in grafuri finite care nu au circuite de valoare negativa (pentru o problema de minim) sau care nu au circuite de valoare pozitiva (intr-o problema de maxim) si gaseste drumurile de valoare minima (maxima) de la toate nodurile grafului la un nod oarecare, fixat. Daca dorim sa cunoastem drumurile de valoare minima (maxima) intre oricare doua noduri vom aplica algoritmul, pe rand, pentru fiecare nod al grafului.


Fisiere in arhiva (1):

  • Drumuri Optime intr-un Graf.doc

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!