20.500.12556/RUL-104981 Obhod trgovskega potnika po zemljevidu Slovenije Traveling salesman problem on the map of Slovenia Problem trgovskega potnika je dobro znan NP-težak problem. Cilj problema je obresti določeno množico mest tako, da pri tem prehodimo čim krajšo pot in se vrnemo v izhodišče. V magistrski nalogi smo poiskali obhod trgovskega potnika po 6007 naseljih Slovenije glede na geografske razdalje med naselji. Za iskanje smo uporabili programa LKH in Concorde. S programom LKH smo poiskali zgornjo mejo obhoda trgovskega potnika. Nato smo s programom Concorde poiskali spodnjo mejo za obhod trgovskega potnika in jo nato izboljševali, dokler nismo dosegli izenačenja spodnje in zgornje meje. Našli smo obhod dolžine 7733,125km in pokazali njegovo optimalnost. The traveling salesman problem is a well known NP-hard problem. Given a list of cities and the distances between each pair of cities, the goal is to find the shortest possible route that visits each city and returns to the origin city. In the thesis we found the solution to the traveling salesman problem on 6007 settlements in Slovenia using the geographical distance between the settlements. To find the solution we used programs LKH and Concorde. With LKH we obtained the upper bound of traveling salesman tour. Than we used Concorde to obtain and improve the lower bound of the traveling salesman tour. We have found the tour of length 7733,125km and have shown that it is optimal. problem trgovskega potnika geografski podatki traveling salesman problem geographical data true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-10-19 11:40:04 2018-10-19 11:40:05 2022-08-17 03:46:10 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 21248 Erzen_Nika_-_Obhod_trgovskega_potnika_po_zemljevidu_Slovenije.pdf Erzen_Nika_-_Obhod_trgovskega_potnika_po_zemljevidu_Slovenije.pdf 1 6AB5425CCBE06C23741EB62FE97AD432 9fb957be66d76101463d6abac193b22abc2b8988b695153f453a75c6065f75ef 14b3744f-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=115541 Fakulteta za računalništvo in informatiko 0 0 0