Vizualizacija i usporedba algoritama za pronalazak najkraćeg puta

završni rad

• Naslov (engleski): Visualization and comparison of algorithms for finding the shortest path
• Autor: Sebastijan Todorović
• Mentor: Vedran Juričić (mentor)
• Član povjerenstva: Ivan Dunđer (predsjednik povjerenstva)
• Član povjerenstva: Kristijan Klasan (član povjerenstva)
• Član povjerenstva: Vedran 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 obrane: 2024-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: završni rad; Dijkstra; a*; d* lite; hps*; algoritmi; pronalazak puta; teorija grafa
• Ključne riječi (engleski): BA thesis; Dijkstra; a*; d* lite; hpa*; algorithms; pathfinding; graph theory
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:131:658624
• Studijski program: Naziv: 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 resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-09-16 12:38:59