Algoritmi za pronalaženje puta

master's thesis

• Title (english): Path finding algorithms
• Author: Ivan Bucić
• Mentor: Dragan Jevtić (mentor)
• Committee member: Dragan Jevtić (predsjednik povjerenstva)
• Committee member: Marin Vuković (član povjerenstva)
• Committee member: Miljenko Mikuc (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): 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
• Language: croatian
• URN:NBN: urn:nbn:hr:168:511698
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 09:48:54