Metrični trgovski potnikŠavli, Maj (Avtor) Robič, Borut (Mentor) problem trgovskega potnikametrični trgovski potnikaproksimacijaNP-težkostProblem trgovskega potnika je eden izmed najbolj znanih problemov kombinatorične optimizacije. Nenehno ga preučujejo že od leta 1930, sprašuje pa naslednje vprašanje: "Če imamo množico mest in množico razdalj med vsakim parom mest, kakšna je najkrajša možna pot, po kateri lahko obiščemo vsa mesta natančno enkrat in se vrnemo v začetno mesto?" Problem trgovskega potnika spada med NP-težke probleme, kar pomeni, da (zaenkrat) ne poznamo algoritma, ki bi ta problem rešil v polinomskem času. Ker pa v praksi ne potrebujemo vedno optimalne rešitve, obstajajo za ta problem tudi aproksimacijski algoritmi. Pri teh algoritmih pa obstaja nekaj ključnih predpostavk. Zaradi teh predpostavk ne moremo več govoriti o splošnem problemu trgovskega potnika, ampak začnemo govoriti o problemu metričnega trgovskega potnika. V diplomskem delu sta predstavljena problema trgovskega potnika in metričnega trgovskega potnika, podroben opis in implementacija dveh trenutno najboljših aproksimacijskih algoritmov za problem metričnega trgovskega potnika ter testiranje, primerjava in analiza implementiranih algoritmov.20192019-09-09 12:00:07Diplomsko delo/naloga109865sl