Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje (CROSBI ID 425726)
Ocjenski rad | sveučilišni preddiplomski završni rad
Podaci o odgovornosti
Jerebić, Pavao
Jakobović, Domagoj
hrvatski
Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje
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.
Pronalaženje puta ; A* ; evolucijsko računarstvo ; inteligencija rojeva ; optimizacija mravljim kolonijama ; mravlji sustav ; optimizacije prometa
nije evidentirano
engleski
Path finding optimization in a dynamic environment
nije evidentirano
Path finding ; A* algorithm ; Evolutionary computing ; Swarm intelligence ; Ant colony optimizations ; Ant system ; Traffic optimizations
nije evidentirano
Podaci o izdanju
32
01.07.2018.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb