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

Extras din referat Cum descarc?

Numeroase aplicatii ale grafurilor sunt legate de determinarea drumului de valoare minima sau maxima dintre doua varfuri si ale grafului G= (X, ?) = (X,U).
Problema drumului optim nu se reduce numai la gasirea numarului minim sau maxim de arce ci pentru aprofundarea suficienta a fenomenului reprezentat in grafuri este necesar sa se ia in considerare pe langa distanta dintre doua puncte si alte elemente: dificultate de parcurgere (cheltuiala de energie), mijloace financiare, etc. De aceea fiecare arc ii atasam o valoare 
Definitie
Valoarea pe care o atasam arcului se numeste valoarea arcului (bucla are valoarea 1);
Fie drumul , atunci valoarea drumului se defineste cu ajutorul relatiei:
,,Drumul optim" corespunde ,,valorii optime" (maxime sau minime) dintr-un anumit punct de vedere: al distantei, al costurilor, al timpului de munca reprezentat prin arcul 
Unul dintre cele mai cunoscute metode de aflare a drumului de valoare optima intr-un graf fara circuite este algoritmul lui Bellman-Kalaba pe care-l vom prezenta in continuare.
Fie G= (X, ?) un graf, vom introduce o functie ce asociaza fiecarui arc din o valoare reala.
Notam: si graful valuat. In cazurile reale valuarea poate reprezenta:
- distanta dintre doua puncte (localizate)
- timpi sau costuri intr-o retea de transport, etc
Vrem sa determinam drumul de la un varf oarecare la varful , pentru care valoarea lui sa fie minima.
Pentru aceasta introducem ,,matricea extinsa a valorilor arcelor" 
, data de
si notam cu valoarea minima a drumului de la varful la varful in graful dat, considerat in multimea drumurilor de cel mult k arce, cu valoarea minima a drumurilor de la la , considerata in multimea tuturor drumurilor (indiferent de numarul de arce componente).
Algoritmul de construire a vectorilor se bazeaza pe urmatoarele propozitii:
Propozitia 1
Pentru orice avem
Demonstratie:
Este evident ca un drum de cel mult k+1 arce cu destinatia se poate obtine dintr-un drum de cel mult k arce cu destinatia , prin adaugarea unui arc la inceputul sau. Deci:
Propozitia 2
Daca exista pentru care , pentru orice , atunci :
Demonstratie:
a) demonstram prin inductie dupa s: pentru s=k+1 proprietatea este adevarata conform enuntului.
Presupunand proprietatea adevarata pentru orice valoare avem:
b) rezulta in mod evident, pentru ca prin adaugarea de arce noi nu obtinem drumuri de valoare mai mica.
Algoritmul de determinare a drumului minim
Schema algoritmica a acestui procedeu este urmatoarea:
Etapa I
Se considera graful valuat , se construieste matricea (tabela) extinsa a valorilor arcelor 
Etapa II
Se adauga matricii V, liniile suplimentare astfel:
a) linia coincide cu transpusa coloanei n a matricii V, 
b) presupunand completata linia se completeaza linia conform propozitiei 1.
c) Se continua aplicarea fazei b) pana la obtinerea a doua linii si identice.
Etapa III
Se determina regresiv drumul minim de la la astfel:
- se aduna linia ,,i" din V cu linia urmarindu-se rezultatul minim ce se poate obtine.
Sa presupunem ca :
atunci primul arc din drumul minim de la la este arcul 
- se adauga linia ,,j" din V cu retinand valoarea minima, aflata de exemplu pe coloana ,,k", atunci al doilea arc va fi , s.a.m.d. Ultimul succesor determinat va fi 
Algoritmul de determinare a drumului maxim
Schema algoritmica a acestui procedeu este urmatoarea:
Etapa I
Se considera graful valuat , se construieste matricea (tabelul) extinsa a valorilor arcelor astfel:


Fisiere in arhiva (1):

  • Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime.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:

* Prin apăsarea pe butonul “Descarcă acum” declar că am citit, înțeles și agreat termenii și condițiile.
* Prețul este fără TVA.


Hopa sus!