prikaz prve stranice dokumenta Heurističke metode rješavanja problema trgovačkog putnika
Rad nije dostupan
diplomski rad
Heurističke metode rješavanja problema trgovačkog putnika
2017. urn:nbn:hr:168:226211
Šulc, Dorian
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Citirajte ovaj rad

Šulc, D. (2017). Heurističke metode rješavanja problema trgovačkog putnika (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, Dorian. "Heurističke metode rješavanja problema trgovačkog putnika." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2017. https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, Dorian. "Heurističke metode rješavanja problema trgovačkog putnika." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2017. https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc, D. (2017). 'Heurističke metode rješavanja problema trgovačkog putnika', Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 15.04.2024., https://urn.nsk.hr/urn:nbn:hr:168:226211

Šulc D. Heurističke metode rješavanja problema trgovačkog putnika [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2017 [pristupljeno 15.04.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:226211

D. Šulc, "Heurističke metode rješavanja problema trgovačkog putnika", Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:226211

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:226211
Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.
Podaci o radu
NaslovHeurističke metode rješavanja problema trgovačkog putnika
Naslov (engleski)Heuristic Methods for the Traveling-Salesman Problem
AutorDorian Šulc
MentorAnte Đerek (mentor)
Član povjerenstvaAnte Đerek (predsjednik povjerenstva)
Član povjerenstvaDomagoj Jakobović (član povjerenstva)
Član povjerenstvaAlan Jović (č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 obrane2017-07-10, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:226211
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2019-03-14 01:28:28