Metrični trgovski potnik

diplomsko delo

Maj Šavli (Author), Borut Robič (Mentor)

Abstract

Problem 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.

Keywords

problem trgovskega potnika;metrični trgovski potnik;aproksimacija;NP-težkost;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[M. Šavli]
UDC:	004(043.2)
COBISS:	1538320835
Views:	705
Downloads:	187
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	The Metric Salesperson Problem
Secondary abstract:	The traveling salesperson problem is one of the best-known problems of combinatorial optimization. It has been continuously studied since 1930 and it asks the following question: "If we have a set of cities and a set of distances between each pair of cities, what is the shortest possible route to visit all the cities, each exactly once, and return to the starting place?" The TSP is an NP-hard problem, which means that (for the time being) we do not know the algorithm that would solve this problem in polynomial time. Since we do not always need the optimal solution, there exist approximation algorithms for this problem. For these algorithms, however, there are some key assumptions. Because of these assumptions, we can no longer deal with the general TSP. Instead, we talk about the so-called metric traveling salesperson problem. The thesis presents the TSP problem, the metric traveling salesperson problem, a detailed procedure and implementation of two currently best approximation algorithms for the metric traveling salesperson problem. In the last part, the implemented algorithms are tested, compared and analysed.
Secondary keywords:	traveling salesperson problem;metric traveling salesperson problem;approximability;NP-hardness;computer and information science;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	39 str.
ID:	11220279