izpis_h1_title_alt

Metrični trgovski potnik
ID Šavli, Maj (Author), ID Robič, Borut (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (394,34 KB)
MD5: 5A496F958D224D8C4121A438FDCD24B0

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.

Language:Slovenian
Keywords:problem trgovskega potnika, metrični trgovski potnik, aproksimacija, NP-težkost
Work type:Bachelor thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2019
PID:20.500.12556/RUL-109865 This link opens in a new window
COBISS.SI-ID:1538320835 This link opens in a new window
Publication date in RUL:09.09.2019
Views:1419
Downloads:217
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:The Metric Salesperson Problem
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.

Keywords:traveling salesperson problem, metric traveling salesperson problem, approximability, NP-hardness

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back