Metrični trgovski potnik

diplomsko delo

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Šavli]
UDK:	004(043.2)
COBISS:	1538320835
Št. ogledov:	705
Št. prenosov:	187
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The Metric Salesperson Problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	traveling salesperson problem;metric traveling salesperson problem;approximability;NP-hardness;computer and information science;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	39 str.
ID:	11220279