Biblioteca

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

Valoare:

4 puncte *

Marime:

128,08 Kb

Pagini:

11

Nota:
8Algoritmul 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.64 Lei, cumparand puncte sau poti obtine puncte daca postezi documente (vezi detalii)
Orice document downloadat sau uploadat este adaugat in Biblioteca Mea
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.