Biblioteca

Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime

Valoare:

4 puncte*

Marime:

128.08Kb

Pagini:

11

Nota:
8 Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime, 8 out of 10 based on 1 rating
Contine fisiere:

doc


Domenii:

Management


Profesor Indrumator / Prezentat Profesorului:

Hampu Alexandru

* de la numai 1.77 Lei, cumparand puncte sau poti obtine puncte daca postezi documente (vezi detalii)
Orice document downloadat sau uploadat este adaugat in Biblioteca Mea

Fisiere arhiva: (1)

  • Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime.doc
Vezi informatii descarcari anterioare

Extras din document:

Numeroase aplicaţii ale grafurilor sunt legate de determinarea drumului de valoare minimă sau maximă dintre două vârfuri şi ale grafului G= (X, Γ) = (X,U).
Problema drumului optim nu se reduce numai la găsirea numărului minim sau maxim de arce ci pentru aprofundarea suficientă a fenomenului reprezentat în grafuri este necesar să se ia în considerare pe lângă distanţa dintre două puncte şi alte elemente: dificultate de parcurgere (cheltuială de energie), mijloace financiare, etc. De aceea fiecare arc îi ataşăm o valoare
Definiţie
Valoarea pe care o ataşăm arcului se numeşte valoarea arcului (bucla are valoarea 1);
Fie drumul , atunci valoarea drumului se defineşte cu ajutorul relaţiei:
„Drumul optim” corespunde „valorii optime” (maxime sau minime) dintr-un anumit punct de vedere: al distanţei, al costurilor, al timpului de muncă reprezentat prin arcul
Unul dintre cele mai cunoscute metode de aflare a drumului de valoare optimă într-un graf fără circuite este algoritmul lui Bellman-Kalaba pe care-l vom prezenta în continuare.
Fie G= (X, Γ) un graf, vom introduce o funcţie ce asociază fiecărui arc din o valoare reală.
Notăm: şi graful valuat. În cazurile reale valuarea poate reprezenta:
- distanţa dintre două puncte (localizate)
- timpi sau costuri într-o reţea de transport, etc
Vrem să determinăm drumul de la un vârf oarecare la vârful , pentru care valoarea lui să fie minimă.
Pentru aceasta introducem „matricea extinsă a valorilor arcelor”
, dată de
şi notăm cu valoarea minimă a drumului de la vârful la vârful în graful dat, considerat în mulţimea drumurilor de cel mult k arce, cu valoarea minimă a drumurilor de la la , considerată în mulţimea tuturor drumurilor (indiferent de numărul de arce componente).
Algoritmul de construire a vectorilor se bazează pe următoarele propoziţii:
Propoziţia 1
Pentru orice avem
Demonstraţie:
Este evident că un drum de cel mult k+1 arce cu destinaţia se poate obţine dintr-un drum de cel mult k arce cu destinaţia , prin adăugarea unui arc la începutul său. Deci:
Propoziţia 2
Dacă există pentru care , pentru orice , atunci :
Demonstraţie:
a) demonstrăm prin inducţie după s: pentru s=k+1 proprietatea este adevărată conform enunţului.
Presupunând proprietatea adevărată pentru orice valoare avem:
b) rezultă în mod evident, pentru că prin adăugarea de arce noi nu obţinem drumuri de valoare mai mică.
Algoritmul de determinare a drumului minim
Schema algoritmică a acestui procedeu este următoarea:
Etapa I
Se consideră graful valuat , se construieşte matricea (tabela) extinsă a valorilor arcelor
Etapa II
Se adaugă matricii V, liniile suplimentare astfel:
a) linia coincide cu transpusa coloanei n a matricii V,
b) presupunând completată linia se completează linia conform propoziţiei 1.
c) Se continuă aplicarea fazei b) până la obţinerea a două linii şi identice.
Etapa III
Se determină regresiv drumul minim de la la astfel:
- se adună linia „i” din V cu linia urmărindu-se rezultatul minim ce se poate obţine.
Să presupunem că :
atunci primul arc din drumul minim de la la este arcul
- se adaugă linia „j” din V cu reţinând valoarea minimă, aflată de exemplu pe coloana „k”, atunci al doilea arc va fi , ş.a.m.d. Ultimul succesor determinat va fi
Algoritmul de determinare a drumului maxim
Schema algoritmică a acestui procedeu este următoarea:
Etapa I
Se consideră graful valuat , se construieşte matricea (tabelul) extinsă a valorilor arcelor astfel:


    Documente similare:
    Preview document similar
    Probleme Rezolvate la Diagnosticul si Evaluarea Intreprinderii
    Fituica contine 5 pagini in format doc cu o marime totala de 32.71 KB.
    Preview document similar
    Fundamentarea, Elaborarea, Implementarea si Evaluarea Strategiei...
    Proiectul contine 76 pagini in format doc cu o marime totala de 98.6 KB.
    Preview document similar
    Inteligenta Artificiala
    Proiectul contine 20 pagini in format doc cu o marime totala de 42.36 KB.
    Preview document similar
    Aplicatii ale Algoritmilor Genetici in Management - Problema...
    Referatul contine 9 pagini in format doc cu o marime totala de 125.67 KB.
    Preview document similar
    Max Weber
    Referatul contine 6 pagini in format doc cu o marime totala de 20.79 KB.
    Preview document similar
    Drum Critic
    Proiectul contine 27 pagini in format doc cu o marime totala de 455.91 KB.