izpis_h1_title_alt

Obhod trgovskega potnika po zemljevidu Slovenije
ID Eržen, Nika (Avtor), ID Fijavž, Gašper (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (6,00 MB)
MD5: 6AB5425CCBE06C23741EB62FE97AD432

Izvleček
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.

Jezik:Slovenski jezik
Ključne besede:problem trgovskega potnika, geografski podatki
Vrsta gradiva:Magistrsko delo/naloga
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2018
PID:20.500.12556/RUL-104981 Povezava se odpre v novem oknu
Datum objave v RUL:19.10.2018
Število ogledov:1355
Število prenosov:247
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Traveling salesman problem on the map of Slovenia
Izvleček:
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.

Ključne besede:traveling salesman problem, geographical data

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj