Algoritmi za pronalaženje puta

diplomski rad

• Naslov (engleski): Path finding algorithms
• Autor: Ivan Bucić
• Mentor: Dragan Jevtić (mentor)
• Član povjerenstva: Dragan Jevtić (predsjednik povjerenstva)
• Član povjerenstva: Marin Vuković (član povjerenstva)
• Član povjerenstva: Miljenko Mikuc (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu su proučeni osnovni pojmovi vezani uz područje matematike - Teorija grafova. Opisana je tema ovog rada te su predstavljena četiri algoritma koja su detaljno opisana i obrađena - pretraživanje u širinu (BFS), pretraživanje u dubinu (DFS), Dijkstrin algoritam, te A* algoritam. Svaki algoritam ima prikazan detaljan pseudokod, način rada sa slikovnim prikazima, te prikaz rada po koracima na testnim primjerima. Prikazana je i programska implementacija svakog od algoritama te je provedena analiza svakog od algoritama. Provedeni su testovi sa svim algoritmima i prikazani rezultati koji sadrže vrijeme izvođenja, duljinu/cijenu puta i ukupan broj posjećenih čvorova, te je provedena analiza dobivenih rezultata. Prikazana je primjena algoritama za pronalaženje puta s njihovim opisom, prikazom rada i vizualnim rezultatima.

Sažetak (engleski)

In this thesis, the basic concepts related to the field of mathematics - Graph Theory have been studied. The topic of this thesis is described and four algorithms are presented and described in detail - Width First Search (BFS), Depth First Search (DFS), Dijkstra's algorithm, and A* algorithm. Each algorithm has a detailed pseudocode, a way of working with image displays, and a step-by-step display of test examples. The programming implementation of each of the algorithms is presented and the analysis of each of the algorithms is performed. Tests with all algorithms were performed and results are containing the execution time, path length/cost and the total number of visited nodes, and an analysis of the obtained results was performed. The application of path finding algorithms with their description, display of work and visual results is presented.

• Ključne riječi: Teorija grafova; algoritmi za pronalaženje puta; mreža čvorova; stabla; pretraživanje u širinu (BFS); pretraživanje u dubinu (DFS); Dijkstrin algoritam; A* algoritam; python; pygame; folium; OSMnx; NetworkX; Mapbox
• Ključne riječi (engleski): Graph theory; path finding algorithms; node networks; trees; Width First Search (BFS); Depth First Search (DFS); Dijkstra’s algorithm; A * algorithm; python; pygame; folium; OSMnx; NetworkX; Mapbox
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:511698
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 09:48:54