Algoritmi pronalaženja najkraćeg puta u grafu

završni rad

• Naslov (engleski): Algorithms for Finding the Shortest Path in a Graph
• Autor: Mateja Potak
• Mentor: Marin Šilić (mentor)
• Član povjerenstva: Marin Šilić (predsjednik povjerenstva)
• Član povjerenstva: Helena Čeović (član povjerenstva)
• Član povjerenstva: Adrian Satja Kurdija (č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: 2023-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Algoritmi pronalaženja najkraćeg puta u grafu dijele se ovisno o strategiji pretraživanja na algoritme slijepog i algoritme usmjerenog pretraživanja. Algoritmi usmjerenog pretraživanja u obzir uzimaju i heuristiku koja nastoji usmjeriti brže k cilju. U radu su obrađena četiri algoritma i njihova programska ostvarenja. U algoritme slijepog pretraživanja spada pretraživanje s jednolikom cijenom (UCS), a u algoritme usmjerenog pretraživanja spadaju pretraživanje „najbolji prvi“, pretraživanje usponom na vrh te algoritam A*. Napravljen programski sustav nastoji oponašati Google Maps za 15 spremljenih konkretnih mjesta u Zagrebu te nudi korisniku mogućnost pretraživanja najkraćeg puta od zadanog početnog do ciljnog mjesta koristeći navedene algoritme. Cilj pretraživanja je optimizacija vremena ili optimizacija udaljenosti.

Sažetak (engleski)

Algorithms for finding the shortest path in a graph are divided depending on the search strategy into uninformed and informed search algorithms. Informed search algorithms also take into account heuristics that try to direct the search faster to the goal. The paper describes four algorithms and their implementation. Uninformed search algorithms include uniform-cost search (UCS) and informed search algorithms include greedy best-first search, hill-climbing search and the A* algorithm. The created program system tries to imitate Google Maps for the stored 15 specific places in Zagreb. It offers the user the possibility to search for the shortest path from the chosen starting point to the destination point using the specified algorithms. The goal of the search is time optimization or distance optimization.

• Ključne riječi: algoritmi pronalaženja najkraćeg puta u grafu; pretraživanje s jednolikom cijenom; algoritam "najbolji prvi"; pretraživanje usponom na vrh; algoritam A*; Google Maps; prostorna optimizacija; vremenska optimizacija
• Ključne riječi (engleski): algorithms for finding the shortest path in a graph; uniform cost search; greedy best-first search; hill-climbing search; A* algorithm; Google Maps; spatial optimization; time optimization
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:586292
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 10:12:32