Naslov
Algoritmi za rješavanje problema trgovačkog putnika
(Algorithms for the travelling salesman problem)

Autori
Skupnjak, Luka

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
PMF-Matematički odsjek

Mjesto
Zagreb

Datum
14.07

Godina
2011

Stranica
50

Mentor
Krčadinac, Vedran

Neposredni voditelj
Nakić, Anamari

Ključne riječi
problem trgovačkog putnika ; heuristički algoritam
(travelling salesman problem ; heuristic algorithm)

Sažetak
Problem trgovačkog putnika (TSP - Traveling Salesman Problem) jedan je od najzanimljivijih problema teorije grafova. Za zadanu mapu gradova putnik želi obići sve gradove, vratiti se na početak puta i pritom minimalno putovati. Najbolji poznati egzaktni algoritmi za rješavanje ovog problema su eksponencijalne složenosti, što ga čini vrlo zahtjevnim za rješavanje na računalu. Iz tog razloga razvijeni su mnogi heuristički algoritmi koji daju približno optimalna rješenja, a izvode se u polinomijalnom vremenu. U ovom radu su se opisali, implementirali i testirali neki od heurističkih algoritama za rješavanje TSP-a te usporedila njihova efikasnost.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA