Heurističke metode rješavanja problema trgovačkog putnika : diplomski rad - Šulc, Dorian (D. Šulc, 2017)
Sažetak na hrvatskom: 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.