Heuristički algoritmi za geometrijski problem trgovačkog putnika : završni rad - Mihalj, Petar (P. Mihalj, 2019)
Sažetak na hrvatskom: Problem trgovačkog putnika (TSP) poznati je problem kombinatorne optimizacije koji se bavi određivanjem hamiltonovskog ciklusa najmanje težine u danom grafu. Istražujemo heurističke algoritme za posebnu vrstu ovog problema - geometrijski TSP (GTSP). GTSP je poseban slučaj TSP-a koji zahtijeva da vrhovima odgovaraju točke euklidskog prostora i da težine bridova odgovaraju udaljenostima između točaka. Implementirali smo i egzaktne i heurističke algoritme, zajedno sa potrebnim strukturama podataka. Nakon procjene performansi heurističkih algoritama na uniformnim skupovima podataka, testirali smo ih na grafovima iz TSPLIB baze grafova. Heuristički algoritmi dali su relativno dobre rezultate za neke primjene, i implementirani sa prikladnim strukturama podataka, pokazali iznimnu brzinu izvođenja.