Problem trgovskega potnika

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2012
Izvor:	Ljubljana
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[K. Zupanc]
UDK:	519.1(043.2)
COBISS:	9366089
Št. ogledov:	2172
Št. prenosov:	365
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The travelling salesman problem
Sekundarni povzetek:	In the travelling salesman problem we are given a graph. The task of the salesman is to find the shortest (or cheapest) possible route by visiting each vertex (that represents cities) exactly once and returning to the initial vertex (city). A Hamilton cycle is a cycle in a graph, in which each vertex is visited only once. In the travelling salesman problem we are thus searching for a Hamilton cycle with a minimum price. The problem was posed in 19th century by the Irish mathematician W. R. Hamilton. Today, this is one of the most intensively studied problems in combinatorial optimization. The travelling salesman problem belongs to the class of NP-hard problems. In particular, this means that we (so far) cannot construct a polynomial-time algorithm that would solve this problem. The bachelor's thesis deals with exact and approximation algorithms for solving the traveling salesman problem. We present an exact Concorde algorithm for solving symmetric traveling salesman problems and use it to examine how good two approximation algorithms are: the nearest neighbour algorithm and the double-tree algorithm. We also explore applicability of the travelling salesman problem to various problems encountered in the fields of science and engineering.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. Ljubljana, Pedagoška fak., Matematika in računalništvo
Strani:	IV, 76 str., [14] str. pril.
Vrsta dela (ePrints):	thesis
Naslov (ePrints):	The travelling salesman problem
Ključne besede (ePrints):	problem trgovskega potnika
Ključne besede (ePrints, sekundarni jezik):	travelling salesman problem
Povzetek (ePrints):	Pri problemu trgovskega potnika imamo podan graf, trgovski potnik pa mora obiskati vse točke grafa (ki predstavljajo mesta), vsako natanko enkrat, in se vrniti v izhodišče. Pri tem želi, da bo skupna cena (razdalja) poti najmanjša (najkrajša). Hamiltonov cikel grafa je sklenjen sprehod po grafu, v katerem vsako točko obiščemo natanko enkrat. Pri problemu trgovskega potnika torej iščemo Hamiltonov cikel z minimalno ceno. Problem je v 19. stoletju prvi matematično obravnaval irski matematik W. R. Hamilton, danes pa je eden izmed najbolj preučevanih problemov kombinatorične optimizacije. Problem trgovskega potnika je NP-težak problem, kar med drugim pomeni, da zanj (zaenkrat) ne poznamo algoritma rešljivega v polinomskem času. V diplomskem delu obravnavamo eksaktne in aproksimacijske algoritme za reševanje problema trgovskega potnika. Ogledamo si eksaktni algoritem Concorde za reševanje tako imenovane simetrične različice problema in s pomočjo računalniškega programa preverimo, kako dobra sta dva aproksimacijska algoritma: algoritem najbližjega soseda in algoritem podvojenega drevesa. Poleg tega spoznamo tudi konkretne situacije, v katerih se problem pojavlja.
Povzetek (ePrints, sekundarni jezik):	In the travelling salesman problem we are given a graph. The task of the salesman is to find the shortest (or cheapest) possible route by visiting each vertex (that represents cities) exactly once and returning to the initial vertex (city). A Hamilton cycle is a cycle in a graph, in which each vertex is visited only once. In the travelling salesman problem we are thus searching for a Hamilton cycle with a minimum price. The problem was posed in 19th century by the Irish mathematician W. R. Hamilton. Today, this is one of the most intensively studied problems in combinatorial optimization. The travelling salesman problem belongs to the class of NP-hard problems. In particular, this means that we (so far) cannot construct a polynomial-time algorithm that would solve this problem. The bachelor's thesis deals with exact and approximation algorithms for solving the traveling salesman problem. We present an exact Concorde algorithm for solving symmetric traveling salesman problems and use it to examine how good two approximation algorithms are: the nearest neighbour algorithm and the double-tree algorithm. We also explore applicability of the travelling salesman problem to various problems encountered in the fields of science and engineering.
Ključne besede (ePrints, sekundarni jezik):	travelling salesman problem
ID:	8310709