prikaz prve stranice dokumenta Heuristički algoritmi za geometrijski problem trgovačkog putnika
No public access
undergraduate thesis
Heuristički algoritmi za geometrijski problem trgovačkog putnika
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. urn:nbn:hr:168:998359
Mihalj, Petar
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Mihalj, P. (2019). Heuristički algoritmi za geometrijski 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:998359

Mihalj, Petar. "Heuristički algoritmi za geometrijski problem trgovačkog putnika." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj, Petar. "Heuristički algoritmi za geometrijski problem trgovačkog putnika." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj, P. (2019). 'Heuristički algoritmi za geometrijski problem trgovačkog putnika', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 30 June 2024, https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj P. Heuristički algoritmi za geometrijski problem trgovačkog putnika [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2019 [cited 2024 June 30] Available at: https://urn.nsk.hr/urn:nbn:hr:168:998359

P. Mihalj, "Heuristički algoritmi za geometrijski problem trgovačkog putnika", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2019. Available at: https://urn.nsk.hr/urn:nbn:hr:168:998359

Metadata
TitleHeuristički algoritmi za geometrijski problem trgovačkog putnika
Title (english)Heuristic Algorithms for Geometric Traveling Salesman Problem
AuthorPetar Mihalj
MentorMario Osvin Pavčević (mentor)
Committee memberMario Osvin Pavčević (predsjednik povjerenstva)
Committee memberMario Krnić (član povjerenstva)
Committee memberDomagoj Kovačević (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2019-07-12, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
Problem trgovačkog putnika (TSP) poznati je problem kombinatorne optimizacije koji se bavi određivanjem hamiltonovskog ciklusa najmanje težine u danom grafu. Istražujemo heurističke algoritme za posebnu vrstu ovog problema - geometrijski TSP (GTSP). GTSP je poseban slučaj TSP-a koji zahtijeva da vrhovima odgovaraju točke euklidskog prostora i da težine bridova odgovaraju udaljenostima između točaka. Implementirali smo i egzaktne i heurističke algoritme, zajedno sa potrebnim strukturama podataka. Nakon procjene performansi heurističkih algoritama na uniformnim skupovima podataka, testirali smo ih na grafovima iz TSPLIB baze grafova. Heuristički algoritmi dali su relativno dobre rezultate za neke primjene, i implementirani sa prikladnim strukturama podataka, pokazali iznimnu brzinu izvođenja.
Abstract (english)
Travelling salesman problem (TSP) is a well known combinatorial optimisation problem concerned with finding a Hamiltonian cycle with minimum weight in a given graph. We discuss heuristic algorithms for a specific type of this problem - geometric TSP (GTSP). GTSP is a specific case of TSP that requires vertices to be assigned points in Euclidean space and edge weights to be equal to Euclidean distances between points. We have implemented both exact and heuristic algorithms, along with required data structures. After evaluating the performance of heuristic algorithms on uniform datasets, we have tested algorithms on graphs in TSPLIB graph library. Heuristic algorithms have given relatively good results for some applications, and have shown exceptional runtime speed when implemented using appropriate data structures.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:998359
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 on2020-01-07 20:22:15