prikaz prve stranice dokumenta Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta
  Download
PDF 1.5 MB
undergraduate thesis
Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta
Zagreb: University of Zagreb, Faculty of Humanities and Social Sciences, 2024. urn:nbn:hr:131:658624
Todorović, Sebastijan
University of Zagreb
Faculty of Humanities and Social Sciences
Department of information and Communication sciences

Institutional repository: ODRAZ

Cite this document

Todorović, S. (2024). Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Humanities and Social Sciences. Retrieved from https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, Sebastijan. "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta." Undergraduate thesis, University of Zagreb, Faculty of Humanities and Social Sciences, 2024. https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, Sebastijan. "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta." Undergraduate thesis, University of Zagreb, Faculty of Humanities and Social Sciences, 2024. https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović, S. (2024). 'Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta', Undergraduate thesis, University of Zagreb, Faculty of Humanities and Social Sciences, accessed 23 November 2024, https://urn.nsk.hr/urn:nbn:hr:131:658624

Todorović S. Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Humanities and Social Sciences; 2024 [cited 2024 November 23] Available at: https://urn.nsk.hr/urn:nbn:hr:131:658624

S. Todorović, "Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta", Undergraduate thesis, University of Zagreb, Faculty of Humanities and Social Sciences, Zagreb, 2024. Available at: https://urn.nsk.hr/urn:nbn:hr:131:658624

Metadata
TitleVizualizacija i usporedba algoritama za pronalazak najkraćeg puta
Title (english)Visualization and comparison of algorithms for finding the shortest path
AuthorSebastijan Todorović
MentorVedran Juričić (mentor)
Committee memberIvan Dunđer (predsjednik povjerenstva)
Committee memberKristijan Klasan (član povjerenstva)
Committee memberVedran Juričić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Humanities and Social Sciences
(Department of information and Communication sciences)
Zagreb
Defense date and country2024-09-16, Croatia
Scientific / art field,
discipline and subdiscipline		SOCIAL SCIENCES
Information and Communication Sciences
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:131:658624
Study programmeTitle: Information Sciences
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informacijskih znanosti (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informacijskih znanosti)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2024-09-16 12:38:59