Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή
Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας κα...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2013
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/6347 |
| id |
nemertes-10889-6347 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-63472022-09-05T20:25:45Z Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή Στυλιανού, Νικόλαος Τσάντας, Νικόλαος Καββαδίας, Δημήτρης Ράγγος, Όμηρος Stylianou, Nikolaos Πρόβλημα πλανόδιου πωλητή Travelling Salesman Problem (TSP) 519.64 Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας. Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος. In this thesis, at short, we present the Travelling Salesman Problem with approximations algorithms, some practical applications and related problems of the main problem. A travelling salesman wants to visit each of a set of towns exactly once starting from and returning to his home town. One of his problems is to find the shortest such trip. We present a self-contained introduction into algorithmic and computational aspects of the TSP along with their theoretical prerequisites as seen from the point of view of an operations researcher who wants to solve practical instances. This thesis is intended to be a guideline of the reader confronted with the question of how to attack a TSP instance depending on its size, its structural properties. Theoretical results are presented in a form which make clear their importance in the design of algorithms for approximate but provably good, and optimal solutions of the TSP. 2013-10-11T19:03:05Z 2013-10-11T19:03:05Z 2013-06-27 2013-10-11 Thesis http://hdl.handle.net/10889/6347 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Πρόβλημα πλανόδιου πωλητή Travelling Salesman Problem (TSP) 519.64 |
| spellingShingle |
Πρόβλημα πλανόδιου πωλητή Travelling Salesman Problem (TSP) 519.64 Στυλιανού, Νικόλαος Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| description |
Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος.
Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας.
Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος. |
| author2 |
Τσάντας, Νικόλαος |
| author_facet |
Τσάντας, Νικόλαος Στυλιανού, Νικόλαος |
| format |
Thesis |
| author |
Στυλιανού, Νικόλαος |
| author_sort |
Στυλιανού, Νικόλαος |
| title |
Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| title_short |
Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| title_full |
Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| title_fullStr |
Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| title_full_unstemmed |
Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| title_sort |
προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή |
| publishDate |
2013 |
| url |
http://hdl.handle.net/10889/6347 |
| work_keys_str_mv |
AT stylianounikolaos prosengizontastoproblēmatouplanodioupōlētē |
| _version_ |
1771297337926221824 |
