Πειραματική μελέτη ενός προσεγγιστικού αλγορίθμου για το πρόβλημα του «περιοδεύοντος πωλητή» - Ροντογιάννης, Δημήτριος; Καράμπελας, Ανδρέας (Open Schools Journal for Open Science, 2020)
Το πρόβλημα του «Περιοδεύοντος Πωλητή» (Travelling Salesman Problem,TSP) είναι ένα από τα σημαντικότερα αλγοριθμικά προβλήματα. Οι υπάρχοντες αλγόριθμοι έχουν κακή πολυπλοκότητα, μπορούν δηλαδή να λύσουν το TSP σε αποδεκτό χρόνο μόνο για μικρό αριθμό πόλεων. Λόγω της δυσκολίας του TSP, έχουν προταθεί προσεγγιστικοί αλγόριθμοι που είναι πιο αποτελεσματικοί από τους υπάρχοντες ακριβείς αλγορίθμους, αλλά των οποίων οι λύσεις δεν είναι υποχρεωτικά βέλτιστες. Ο πιο γνωστός προσεγγιστικός αλγόριθμος για το TSP είναι ο αλγόριθμος του Χριστοφίδη. Ο σκοπός της παρούσης εργασίας είναι η πειραματική μελέτη του αλγορίθμου του Χριστοφίδη σε σχέση με έναν ακριβή αλγόριθμο και εν συνεχεία η διερεύνηση της δυνατότητας βελτίωσης της προσέγγισης που επιτυγχάνεται. Υλοποιούμε έναν αλγόριθμο που επιστρέφει τη βέλτιστη λύση στο TSP και έχει εκθετική πολυπλοκότητα, καθώς και τον αλγόριθμο του Χριστοφίδη, ο οποίος έχει πολύ καλύτερη πολυπλοκότητα αλλά επιστρέφει μια προσεγγιστική λύση. Θεωρούμε διαφορετικές τοποθετήσεις πόλεων στο επίπεδο, και εξετάζουμε την προσέγγιση που επιτυγχάνει ο αλγόριθμος του Χριστοφίδη σε σχέση με τη βέλτιστη. Προτείνουμε μια επέκταση στον αλγόριθμο του Χριστοφίδη την οποία εξετάζουμε πειραματικά και δείχνουμε ότι οι προσεγγιστικές λύσεις που επιστρέφει είναι κατά μέσο όρο καλύτερες από τον πρωτότυπο αλγόριθμο. Αυτή η επέκταση θα μπορούσε να χρησιμοποιηθεί στις περιπτώσεις εκείνες που είναι αναγκαίο να εξασφαλίσουμε μια καλύτερη προσεγγιστική λύση από αυτή που επιτυγχάνει ο αλγόριθμος του Χριστοφίδη.