prikaz prve stranice dokumenta Usporedba odabranih algoritama za problem trgovačkog putnika
No public access
undergraduate thesis
Usporedba odabranih algoritama za problem trgovačkog putnika
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. urn:nbn:hr:168:826280
Korotaj, Mislav
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Korotaj, M. (2024). Usporedba odabranih algoritama za problem trgovačkog putnika (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, Mislav. "Usporedba odabranih algoritama za problem trgovačkog putnika." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, Mislav. "Usporedba odabranih algoritama za problem trgovačkog putnika." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, M. (2024). 'Usporedba odabranih algoritama za problem trgovačkog putnika', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 21 December 2024, https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj M. Usporedba odabranih algoritama za problem trgovačkog putnika [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2024 [cited 2024 December 21] Available at: https://urn.nsk.hr/urn:nbn:hr:168:826280

M. Korotaj, "Usporedba odabranih algoritama za problem trgovačkog putnika", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2024. Available at: https://urn.nsk.hr/urn:nbn:hr:168:826280

Metadata
TitleUsporedba odabranih algoritama za problem trgovačkog putnika
Title (english)Comparison of Algorithms for Solving Traveling Salesman Problem
AuthorMislav Korotaj
MentorIlko Brnetić (mentor)
Committee memberIlko Brnetić (predsjednik povjerenstva)
Committee memberAndrea Aglić Aljinović (član povjerenstva)
Committee memberMate Puljiz (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2024-06-28, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
Problem trgovačkog putnika jedan je od najpoznatijih problema iz područja kombinatoričke optimizacije. U ovom problemu, trgovački putnik mora obići sve gradove točno jednom i vratiti se u početni grad pri čemu se traži minimalna duljina puta. Iako se na prvi pogled čini jednostavnim za manji broj gradova (ili općenito vrhova u grafu), složenost mu eksponencijalno raste s povećanjem broja gradova, što ga čini izrazito teškim za rješavanje U ovom radu proučeni su razni algoritmi za rješavanje simetričnog problema trgovačkog putnika koji pokušavaju zaobići potrebu pretrage svih mogućih Hamiltonovskih ciklusa: iscrpna pretraga s gornjom granicom, branch and bound, dinamičko programiranje i algoritam najbližeg susjeda. Napravljena je analiza vremenske i prostorne složenosti tih algoritama. U praktičnom dijelu razvijeno je programsko rješenje koje implementira sve proučene algoritme. Na kraju su rezultati analizirani, uzete su statistike i doneseni zaključci.
Abstract (english)
The traveling salesman problem (TSP) is one of the most well-known problems in the field of combinatorial optimization. In this problem, a traveling salesman must visit all cities exactly once and return to the starting city, seeking the shortest possible route. Although it may seem straightforward for a small number of cities (or generally vertices in a graph) at first glance, its complexity grows exponentially with the increase in the number of cities, making it extremely difficult to solve. This paper examines various algorithms for solving the symmetric traveling salesman problem that attempt to circumvent the need to search through all possible Hamiltonian cycles: exhaustive search with an upper bound, branch and bound, dynamic programming, and the nearest neighbor algorithm. An analysis of the time and space complexity of these algorithms was conducted. In the practical part, a software solution was developed to implement all the studied algorithms. Finally, the results were analyzed, statistics were collected, and conclusions were drawn.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:826280
Study programmeTitle: Computing
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2024-10-12 21:07:21