Algoritmul lui Bellman-Kalaba în Rezolvarea Problemei Drumurilor Minime-Maxime

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: