prikaz prve stranice dokumenta Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta
  Preuzmi
PDF 1.5 MB
završni rad
Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta
Zagreb: Sveučilište u Zagrebu, Filozofski fakultet, 2024. urn:nbn:hr:131:658624
Todorović, Sebastijan
Sveučilište u Zagrebu
Filozofski fakultet
Odsjek za informacijske i komunikacijske znanosti

Institucijski repozitorij: ODRAZ

Citirajte ovaj rad

Todorović, S. (2024). Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta (Završni rad). Zagreb: Sveučilište u Zagrebu, Filozofski fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, Sebastijan. "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta." Završni rad, Sveučilište u Zagrebu, Filozofski fakultet, 2024. https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, Sebastijan. "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta." Završni rad, Sveučilište u Zagrebu, Filozofski fakultet, 2024. https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, S. (2024). 'Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta', Završni rad, Sveučilište u Zagrebu, Filozofski fakultet, citirano: 24.11.2024., https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović S. Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta [Završni rad]. Zagreb: Sveučilište u Zagrebu, Filozofski fakultet; 2024 [pristupljeno 24.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:131:658624

S. Todorović, "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta", Završni rad, Sveučilište u Zagrebu, Filozofski fakultet, Zagreb, 2024. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:131:658624

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:131:658624
Podaci o radu
NaslovVizualizacija i usporedba algoritama za pronalazak najkraćeg puta
Naslov (engleski)Visualization and comparison of algorithms for finding the shortest path
AutorSebastijan Todorović
MentorVedran Juričić (mentor)
Član povjerenstvaIvan Dunđer (predsjednik povjerenstva)
Član povjerenstvaKristijan Klasan (član povjerenstva)
Član povjerenstvaVedran Juričić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Filozofski fakultet
(Odsjek za informacijske i komunikacijske znanosti)
Zagreb
Datum i država obrane2024-09-16, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		DRUŠTVENE ZNANOSTI
Informacijske i komunikacijske znanosti
Sažetak
U radu se uspoređuju najpopularniji algoritmi za pronalaženje najkraćeg puta u dvodimenzionalnoj kvadratnoj mreži. U uvodnom dijelu se definiraju osnovni pojmovi iz teorije grafova te se daje važnost i mogućnosti primjene navedenih algoritama. Opisan je rad najpopularnijih algoritama koji uključuju Dijkstrin algoritam, A*, D* Lite i HPA*. Osim usporedbe načina rada i kompleksnosti, u radu se opisuju prednosti, mane i moguća unaprjeđenja, odnosno optimizacije algoritama. Vizualno se prikazuju koraci rada algoritama te se primjerima dolazi do rješenja izračuna puta u adekvatnim grafovima. Uz vizualno, prikazuje se i empirički mjereno vrijeme pronalaska put za svaki od algoritama koji su implementirani u C++ jeziku sa identičnim tipovima podataka kako bi rezultati bili što točniji. Objašnjavaju se točni problemi koji dovode to mjerenih rezultata te se daju primjeri rješenja koji bi mogli poboljšati rezultate. U sklopu rada izrađena je i opisana aplikacija koja vizualizira rad algoritama, odnosno koja za zadanu veličinu grafa, te početak i kraj putanje prikazuje pojedine korake rada algoritma i pretraženih puteva.
Sažetak (engleski)
The paper compares the most popular pathfinding algorithms in a two-dimensional square grid. In the introductory part, basic terms from graph theory are defined and the importance and application possibilities of the mentioned algorithms are given. The operation of the most popular algorithms such as Dijkstra's, A*, D* Lite and HPA* is described. In addition to the comparison of working methods and complexity, the paper describes the advantages, disadvantages, and possible improvements, that is, optimizations of the algorithms. Every step of the algorithm is visually shown, and the run time is empirically measured for each of the algorithms, each implemented in C++ programming language, using the same data types so that the results can be as accurate as possible. Problems that can and do increase the run time are mentioned and described, and the possible solutions are given so that the results can be improved. As part of the work, a program was created that visualizes the algorithms, which for a given graph size, and the beginning and end of the path, shows each step of the algorithm's operation and the searched paths.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:131:658624
Studijski programNaziv: Informacijske znanosti
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informacijskih znanosti (univ. bacc. inf.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2024-09-16 12:38:59