Naslov | Primjena metaheuristike tabu pretraživanja kod rješavanja problema trgovačkog putnika |
Autor | Sven Srebot |
Voditelj/Mentor | Lea Skorin-Kapov (mentor)
|
Sažetak rada | Cilj ovog rada je primijeniti algoritam tabu pretraživanja na problem trgovačkog putnika i analizirati utjecaj pojedinih parametara pretraživanja na kvalitetu rješenja i trajanje izvođenja algoritma. Problem trgovačkog putnika spada u skupinu NP-teških problema. Rješenje problema trgovačkog putnika egzaktnim algoritmom nije moguće naći u polinomnom vremenu, zbog čega se za rješavanje problema trgovačkog putnika često koriste metaheuristike. Metaheuristike se koriste za pronalazak dovoljno dobrog rješenja u razumnom vremenu. Tabu pretraživanje je iterativna metaheuristika zasnovana na pojedinačnom rješenju, koja prilikom pretraživanja koristi pamćenje. Tabu pretraživanje je čest pristup rješavanju problema trgovačkog putnika. |
Ključne riječi | problem trgovačkog putnika tabu pretraživanje |
Naslov na drugom jeziku (engleski) | Applicability of the Tabu Search Metaheuristic in Solving the Traveling Salesman Problem |
Povjerenstvo za obranu | Lea Skorin-Kapov (predsjednik povjerenstva) Tomislav Grgić (član povjerenstva) Ivan Slivar (član povjerenstva)
|
Ustanova koja je dodijelila akademski/stručni stupanj | Sveučilište u Zagrebu Fakultet elektrotehnike i računarstva |
Mjesto | Zagreb |
Država obrane | Hrvatska |
Znanstveno područje, polje, grana | TEHNIČKE ZNANOSTI Računarstvo
|
Vrsta studija | sveučilišni |
Stupanj | preddiplomski |
Naziv studijskog programa | Elektrotehnika i informacijska tehnologija |
Akademski / stručni naziv | sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka elektrotehnike i informacijske tehnologije |
Kratica akademskog / stručnog naziva | univ. bacc. ing. el. techn. inf. |
Vrsta rada | završni rad |
Jezik | hrvatski |
Datum obrane | 2016-09-05 |
Sažetak rada na drugom jeziku (engleski) | The goal of this thesis is to apply the tabu search algorithm in solving the travelling salesman problem, and to analyse the influence of the search parameters on the quality of solution and algorithm execution time. The travelling salesman problem belongs to the class of NP-hard optimization problems. Solutions to the travelling salesman problem cannot be found by exact methods in polynomial time, and because of that metaheuristics are often used to solve this class of problem. Metaheuristics are used to find acceptable solutions in reasonable time. Tabu search is a single solution-based iterative metaheuristic, which uses memory during the search. Tabu search is a common approach to solving the travelling salesman problem. |
Ključne riječi na drugom jeziku (engleski) | travelling salesman problem tabu search |
Vrsta resursa | tekst |
Prava pristupa | Rad nije dostupan |
Uvjeti korištenja rada |  |
URN:NBN | https://urn.nsk.hr/urn:nbn:hr:168:081617 |