izpis_h1_title_alt

Iskanje najcenejše poti v grafih preko polkolobarjev
Horvat, Veronika (Avtor), Oblak, Polona (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (367,92 KB)

Izvleček
V diplomskem delu je predstavljen problem iskanja najcenejših poti v usmerjenem grafu s pomočjo Bellmanovega algoritma. Algoritem je različica Bellmanovih enačb z novostjo, da delo poteka nad matrikami in operacijami tropskega polkolobarja. Za utežen usmerjen graf cene povezav zapišemo v matriko A. Matrika ima kvazi inverz A^* nad tropskim polkolobarjem, s pomočjo katerega izračunamo minimalno rešitev sistema enačb, izraženega iz Bellmanovih enačb. Rešitev algoritma je vektor cen najcenejših poti do vseh vozlišč v grafu.

Jezik:Slovenski jezik
Ključne besede:Tropska algebra, kvazi inverz, Bellmanov algoritem, usmerjen graf
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2014
Število ogledov:718
Število prenosov:317
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Semirings and the shortest path problem
Izvleček:
The thesis presents the problem of finding the shortest path in a directed graph with the Bellman's algorithm. This algorithm a version of Bellman equation with the novelty that the we work with matrices and operations over tropical semiring. Given a weighted directed graph, its arc prices are written in a matrix A. The matrix has a quasi-inverse A^* over tropical semiring, which is used to compute the minimal solution of the system of equations expressed from the Bellman equation. The solution of the algorithm is a vector of prices that represents the prices of the shortest paths to all nodes in the graph.

Ključne besede:Tropical algebra, quasi inverse, Bellman's algorithm, directed graph

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj