Problem trgovskega potnika

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2012
Source:	Ljubljana
Typology:	2.11 - Undergraduate Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[K. Zupanc]
UDC:	519.1(043.2)
COBISS:	9366089
Views:	2172
Downloads:	365
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	The travelling salesman problem
Secondary abstract:	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.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. Ljubljana, Pedagoška fak., Matematika in računalništvo
Pages:	IV, 76 str., [14] str. pril.
Type (ePrints):	thesis
Title (ePrints):	The travelling salesman problem
Keywords (ePrints):	problem trgovskega potnika
Keywords (ePrints, secondary language):	travelling salesman problem
Abstract (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.
Abstract (ePrints, secondary language):	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.
Keywords (ePrints, secondary language):	travelling salesman problem
ID:	8310709