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

Referat / Management
Informatii Referat:
Numar pagini: 11 pagini
Marime arhiva: 128.08 KB
Contine fisiere: doc
Numar fisiere: 1 fisier
Nota pe site: Nota  8 Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime , 8 out of 10based on 1 rating
Profesor indrumator / Prezentat Profesorului:
Hampu Alexandru
Ce sunt punctele? Ce sunt punctele?
  • Punctele reprezinta moneda de schimb a site-lui.
  • Ai nevoie de ele ca sa downloadezi documente si le poti primi incarcand documente pe site.
  • Daca nu vrei sau nu poti face asta, punctele se pot cumpara foarte usor prin SMS, Card sau PayPal.
  • Click pentru mai multe detalii.

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:


Fisiere in arhiva: (1)

  • Algoritmul lui Bellman-Kalaba in Rezolvarea Problemei Drumurilor Minime-Maxime.doc

Previzualizare pagini (11):


    Documente similare:

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