prikaz prve stranice dokumenta Heurističke metode rješavanja problema trgovačkog putnika
No public access
master's thesis
Heurističke metode rješavanja problema trgovačkog putnika
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2017. urn:nbn:hr:168:226211
Šulc, Dorian
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Šulc, D. (2017). Heurističke metode rješavanja problema trgovačkog putnika (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, Dorian. "Heurističke metode rješavanja problema trgovačkog putnika." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2017. https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, Dorian. "Heurističke metode rješavanja problema trgovačkog putnika." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2017. https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, D. (2017). 'Heurističke metode rješavanja problema trgovačkog putnika', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 24 August 2024, https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc D. Heurističke metode rješavanja problema trgovačkog putnika [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2017 [cited 2024 August 24] Available at: https://urn.nsk.hr/urn:nbn:hr:168:226211

D. Šulc, "Heurističke metode rješavanja problema trgovačkog putnika", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:168:226211

Metadata
TitleHeurističke metode rješavanja problema trgovačkog putnika
Title (english)Heuristic Methods for the Traveling-Salesman Problem
AuthorDorian Šulc
MentorAnte Đerek (mentor)
Committee memberAnte Đerek (predsjednik povjerenstva)
Committee memberDomagoj Jakobović (član povjerenstva)
Committee memberAlan Jović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2017-07-10, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
Problem trgovačkog putnika je NP-težak problem, ali ga se može dovoljno dobro riješiti u razumnom vremenu koristeći heuristike. U radu opisujemo jednu takvu po imenu Lin-Kernighan heuristika. Implementiramo i testiramo istu. Na temelju rezultata nudimo mišljenja i ideje kako ubrzati i efikasno implementirati novu inačicu. Provodimo temeljite testove i uspoređujemo se s drugim rješenjima. Dodatno, iskušavamo metodu koja ponovnim rješavanjem istog problema i prijenosom informacija između pokušaja unaprjeđuje konačna rješenja. Konačni algoritam radi u izmjerenoj vremenskoj složenosti O(n1.9). Jedan pokušaj rješavanja potpuno povezanog grafa od 1000 čvorova traje svega nekoliko milisekundi dok je za 15 tisuća čvorova potrebno oko 300 milisekundi.
Abstract (english)
Traveling salesman problem belongs to the class of NP-hard problems but, using heuristics, it can be solved well enough within reasonable time. In this paper we describe one such heuristic called Lin-Kernighan heuristic. We implement and test it. Based on results we offer ideas on how to speed up and efficiently implement a new version the algorithm. We perform extensive tests and compare ourselves with other solutions. Additionally, we try out a method which repeatedly solves the problem and uses the gained information through the process to yield better results. The final algorithm has measured time complexity of O(n1.9). One trial for solving a 1000 node graph takes but a few milliseconds, while 15 thousand node problems take about 300 milliseconds.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:226211
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2019-03-14 01:28:28