Προσεγγιστικοί αλγόριθμοι του προβλήματος του περιοδεύοντος πωλητή
| 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. |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
-
Τμήμα Πληροφορικής
Department of Informatics
Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές