|
|
|
|
| LEADER |
02534na a2200229 4500 |
| 003 |
HR-ZaFER |
| 008 |
160221s2017 ci ||||| m||| 00| 0 hr d |
| 035 |
|
|
|a (HR-ZaFER)ferid5245
|
| 040 |
|
|
|a HR-ZaFER
|b hrv
|c HR-ZaFER
|e ppiak
|
| 100 |
1 |
|
|a Šulc, Dorian
|
| 245 |
1 |
0 |
|a Heurističke metode rješavanja problema trgovačkog putnika :
|b diplomski rad /
|c Dorian Šulc ; [mentor Ante Đerek].
|
| 246 |
1 |
|
|a Heuristic Methods for the Traveling-Salesman Problem
|i Naslov na engleskom:
|
| 260 |
|
|
|a Zagreb,
|b D. Šulc,
|c 2017.
|
| 300 |
|
|
|a 34 str. ;
|c 30 cm +
|e CD-ROM
|
| 502 |
|
|
|b diplomski studij
|c Fakultet elektrotehnike i računarstva u Zagrebu
|g smjer: Računarska znanost, šifra smjera: 56, datum predaje: 2017-06-29, datum završetka: 2017-07-10
|
| 520 |
3 |
|
|a 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.
|
| 520 |
3 |
|
|a Sažetak na engleskom: 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.
|
| 653 |
|
1 |
|a trgovački
|a putnik
|a Lin-Kernighan
|a heuristika
|
| 653 |
|
1 |
|a traveling
|a salesman
|a Lin-Kernighan
|a heuristic
|
| 700 |
1 |
|
|a Đerek, Ante
|4 ths
|
| 942 |
|
|
|c Y
|
| 999 |
|
|
|c 50227
|d 50227
|