Προσεγγιστικοί αλγόριθμοι του προβλήματος του περιοδεύοντος πωλητή

Λαμπάτος, Παναγιώτης Γ.

dc.contributor.advisor	Κωνσταντόπουλος, Χαράλαμπος
dc.contributor.author	Λαμπάτος, Παναγιώτης Γ.
dc.date.accessioned	2014-06-26T08:28:44Z
dc.date.available	2014-06-26T08:28:44Z
dc.date.issued	2014-06-26T08:28:44Z
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/5907
dc.description.abstract	Στην εργασία αυτή παρουσιάζεται το πρόβλημα του Περιοδεύοντος Πωλητή (Traveling Sales man Problem, TSP) και οι προσεγγιστικοί αλγόριθμοι επίλυσης του. Το πρόβλημα συνίσταται στην προσπάθεια εύρεσης της οικονομικότερης – άριστης περιοδείας, που πρέπει να ακολουθήσει ένας περιοδεύων πωλητής, ώστε να επισκεφθεί κάθε πόλη, ενός συνόλου πόλεων, ακριβώς μια φορά και να επιστέψει στην αρχική πόλη. Η επίλυση του προβλήματος έχει αποδειχτεί πολύ δύσκολη και το πρόβλημα κατηγοριοποιείται στα NP-Πλήρη (Np-Complete) προβλήματα, καθώς για μεγάλο αριθμό πόλεων ο χρόνος που απαιτείται για όλους τους υπολογισμούς είναι κυριολεκτικά ασύλληπτος. Η εργασία ξεκινά με την ιστορική παρουσίαση του προβλήματος και των εφαρμογών του. Ακολουθεί παρουσίαση της πολυπλοκότητας του προβλήματος και των διάφορων παραλλαγών του. Στην συνέχεια παρουσιάζονται οι ακριβείς (exact) αλγόριθμοι επίλυσης του TSP οι οποίοι υπολογίζουν πάντα την άριστη λύση του προβλήματος αλλά αποδίδουν ικανοποιητικά μόνο σε προβλήματα λίγων πόλεων. Κατόπιν παρουσιάζονται οι ευρετικοί (heuristics) αλγόριθμοι, οι οποίοι δίνουν αποδεδειγμένα λύσεις που προσεγγίζουν την άριστη σε πολύ μικρότερο χρόνο και ανάλογα με την τεχνική που χρησιμοποιούν κατηγοριοποιούνται σε Κατασκευαστικούς και Βελτιωτικούς. Στη συνέχεια παρουσιάζονται οι προσεγγιστικοί αλγόριθμοι σταθερού λόγου προσέγγισης και τέλος τα Προσεγγιστικά Σχήματα Πολυωνυμικού Χρόνου (Polynomial Time Approximation Scheme, PTAS) για το πρόβλημα του Ευκλείδειου-TSP.
dc.language.iso	el
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.el
dc.subject	Combinatorial optimization
dc.subject	Traveling-salesman problem
dc.subject	Selling
dc.title	Προσεγγιστικοί αλγόριθμοι του προβλήματος του περιοδεύοντος πωλητή
dc.title.alternative	Approximation algorithms for the travelling salesman problem	en
dc.type	Master Thesis
europeana.isShownAt	https://dione.lib.unipi.gr/xmlui/handle/unipi/5907
dc.identifier.call	511.6 ΛΑΜ
dc.description.abstractEN	This paper presents the Traveling Salesman Problem (TSP) and the approximation algorithms solving it. The problem consists in trying to find the most economical - optimal tour, to be followed by a traveling salesman in order to visit each city from a set of cities, exactly once, starting and ending at the same city. Solving the problem has proven to be very difficult and the problem is classified as NP-hard due to the fact that for a large number of cities the time required for all calculations are virtually inconceivable. The paper begins with the historical presentation of the problem and its applications. It is followed by a presentation of the complexity of the problem and its variants. Further on, we present the exact algorithms for TSP, which find the optimal tour for the problem and for this reason they perform well only in few cities problems. Then we present the heuristics algorithms, which provide solutions that are proven close to optimal in a much shorter time. Depending on the technique they use they are categorized as construction and improvement heuristics. Next we present constant ratio approximation algorithms and finally the Polynomial Time Approximation Schemes, PTAS, for the Euclidean-TSP problem.

Files in this item

Name:: Lampatos.pdf
Size:: 2.541Mb
Format:: PDF

View/Open

This item appears in the following Collection(s)

Τμήμα Πληροφορικής
Department of Informatics

Show simple item record

Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές