Naslov
Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje
(Path finding optimization in a dynamic environment)

Autori
Jerebić, Pavao

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
01.07

Godina
2018

Stranica
32

Mentor
Jakobović, Domagoj

Ključne riječi
Pronalaženje puta ; A* ; evolucijsko računarstvo ; inteligencija rojeva ; optimizacija mravljim kolonijama ; mravlji sustav ; optimizacije prometa
(Path finding ; A* algorithm ; Evolutionary computing ; Swarm intelligence ; Ant colony optimizations ; Ant system ; Traffic optimizations)

Sažetak
Tema ovog rada je “Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje“. Problem je predstavljen u svijetu prometnih mreža i vozila koja se koja se njima gibaju. Prometna mreža je predstavljena grafom, a gužve su predstavljene kapacitetom kao težinama na bridovima. Pristup koji je odabran se sastoji od dviju komponenti. Prva komponenta je A* algoritam kojim se traži najkraći put u smislu prostorne udaljenosti između početne i krajnje točke. Drugi dio rješenja čini mravlji algoritam kojim to rješenje optimiziramo. Staza koja se dobije A* algoritmom služi za postavljanje početnog feromonskog traga gdje je trag jači što je taj čvor bliže cilju. Time je postignut efekt zatvarača koji se koristi i u stvarnim prometnim mrežama. Dobiveni rezultati su bili očekivani. Rješenja dobivena mravljim algoritmima su bila bolja od onih dobivenih samo A* algoritmom. Na manjim grafovima je dolazilo do utjecaja pristranosti najkraćem rješenju, ali je kod većih grafova bilo potrebno da bi se brzo pronašao neki put. Daljnjim iteracijama mravljeg algoritma, uspio se smanjiti taj utjecaj do zanemarive razine. Takvi rezultati su se na kraju pokazali dobrima i vidjelo se znatno poboljšanje od pohlepnog rješenja koje uzima u obzir samo najkraću udaljenost.

Izvorni jezik
Hrvatski

POVEZANOST RADA