Μια υλοποίηση του αλγόριθμου του Arora για το πρόβλημα k-TSP
An implementation of Arora’s algorithm for the k-TSP problem
View/
Abstract
The Travelling Salesperson Problem is one of the first well-known problems of graph theory, which owes its popularity to the number of practical applications that its implementation can solve. Over the years it has been used as a benchmark for the evaluation of newer algorithms and its proposed solution methods have offered a great number of innovations concerning matters related to heuristics and approximation techniques in Computer Science.
In this thesis, the approximation algorithm of Sanjeev Arora is presented, explained and implemented, and later expanded so that it can offer solution to a variation of the problem, where the needed number of nodes of a solution is differentiated. Code segments are presented in pseudocode, as well as the results of the algorithms’ executions in each case.
The present work aims to prove that algorithms with strict mathematical foundation and mathematically proven accuracy also have the practicality that has lately been associated mainly with heuristic algorithms. It also aims to suggest adjustments to parts of the algorithms that appear to involve too many calculations when the theory is adapted for implementation.
Postgraduate Studies Programme
ΠληροφορικήDepartment
Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα ΠληροφορικήςNumber of pages
80Language
GreekDescription
Ο σχετικός κώδικας έχει αναρτηθεί στο https://github.com/lonerae/tsp-approximationsCollections
Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα