Πειραματική μελέτη ενός προσεγγιστικού αλγορίθμου για το πρόβλημα του «περιοδεύοντος πωλητή»
Abstract
Το πρόβλημα του «Περιοδεύοντος Πωλητή» (Travelling Salesman Problem,TSP) είναι ένα από τα σημαντικότερα αλγοριθμικά προβλήματα. Οι υπάρχοντες αλγόριθμοι έχουν κακή πολυπλοκότητα, μπορούν δηλαδή να λύσουν το TSP σε αποδεκτό χρόνο μόνο για μικρό αριθμό πόλεων. Λόγω της δυσκολίας του TSP, έχουν προταθεί προσεγγιστικοί αλγόριθμοι που είναι πιο αποτελεσματικοί από τους υπάρχοντες ακριβείς αλγορίθμους, αλλά των οποίων οι λύσεις δεν είναι υποχρεωτικά βέλτιστες. Ο πιο γνωστός προσεγγιστικός αλγόριθμος για το TSP είναι ο αλγόριθμος του Χριστοφίδη. Ο σκοπός της παρούσης εργασίας είναι η πειραματική μελέτη του αλγορίθμου του Χριστοφίδη σε σχέση με έναν ακριβή αλγόριθμο και εν συνεχεία η διερεύνηση της δυνατότητας βελτίωσης της προσέγγισης που επιτυγχάνεται. Υλοποιούμε έναν αλγόριθμο που επιστρέφει τη βέλτιστη λύση στο TSP και έχει εκθετική πολυπλοκότητα, καθώς και τον
αλγόριθμο του Χριστοφίδη, ο οποίος έχει πολύ καλύτερη πολυπλοκότητα αλλά επιστρέφει μια προσεγγιστική λύση. Θεωρούμε διαφορετικές τοποθετήσεις πόλεων στο επίπεδο, και
εξετάζουμε την προσέγγιση που επιτυγχάνει ο αλγόριθμος του Χριστοφίδη σε σχέση με τη βέλτιστη. Προτείνουμε μια επέκταση στον αλγόριθμο του Χριστοφίδη την οποία εξετάζουμε πειραματικά και δείχνουμε ότι οι προσεγγιστικές λύσεις που επιστρέφει είναι κατά μέσο όρο καλύτερες από τον πρωτότυπο αλγόριθμο. Αυτή η επέκταση θα μπορούσε να χρησιμοποιηθεί στις περιπτώσεις εκείνες που είναι αναγκαίο να εξασφαλίσουμε μια καλύτερη προσεγγιστική λύση από αυτή που επιτυγχάνει ο αλγόριθμος του Χριστοφίδη.
Article Details
- How to Cite
-
Ροντογιάννης Δ., & Καράμπελας Α. (2020). Πειραματική μελέτη ενός προσεγγιστικού αλγορίθμου για το πρόβλημα του «περιοδεύοντος πωλητή». Open Schools Journal for Open Science, 3(6). https://doi.org/10.12681/osj.24312
- Issue
- Vol. 3 No. 6
- Section
- Greece
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution licence that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g. post it to a repository), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
