Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta

undergraduate thesis

• Title (english): Visualization and comparison of algorithms for finding the shortest path
• Author: Sebastijan Todorović
• Mentor: Vedran Juričić (mentor)
• Committee member: Ivan Dunđer (predsjednik povjerenstva)
• Committee member: Kristijan Klasan (član povjerenstva)
• Committee member: Vedran Juričić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Humanities and Social Sciences; (Department of information and Communication sciences); Zagreb
• Defense date and country: 2024-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: završni rad; Dijkstra; a*; d* lite; hps*; algoritmi; pronalazak puta; teorija grafa
• Keywords (english): BA thesis; Dijkstra; a*; d* lite; hpa*; algorithms; pathfinding; graph theory
• Language: croatian
• URN:NBN: urn:nbn:hr:131:658624
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-09-16 12:38:59