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

Abstract

Στόχος της πτυχιακής εργασίας ήταν η εφαρμογή της ανάλυσης υπεροχής σε ευριστικούς αλγορίθμους για το Πρόβλημα του Πλανόδιου Πωλητή (TSP). Η ανάλυση υπεροχής αποτελεί μια μέθοδο αξιολόγησης της απόδοσης ενός ευριστικού και βασίζεται στην καταμέτρηση του πλήθους λύσεων που δεν είναι χειρότερες από τη λύση που παράγει ο ευριστικός. Ο αριθμός των λύσεων αυτών είναι γνωστός και ως αριθμός υπεροχής. Η βασική προσέγγιση της μεθόδου αυτής συνίσταται στην κατασκευή ενός στιγμιοτύπου στο οποίο η εφαρμογή του υπό αξιολόγηση ευριστικού δίνει τον χαμηλότερο δυνατό αριθμό υπεροχής. Αποδεικύεται έτσι ότι κάποιοι από τους πιο διαδεδομένους ευριστικούς για το TSP (όπως ο Άπληστος Αλγόριθμος και ο Πλήσιέστερος Γείτονας) έχουν αριθμό υπεροχής ίσο με 1, που σημαίνει ότι υπάρχει ένα στιγμιότυπο για το οποίο η λύση του ευριστικού είναι η χειρότερη δυνατή. Τα αποτελέσματα είναι καλύτερα στην περίπτωση του Επαναληπτικού Πλησιέσερου Γείτονα και του Αλγόριθμου Εισαγωγής Κορυφής καθώς οι αριθμοί υπεροχής τους είναι εκθετικής και παραγοντικής τάξης αντίστοιχα. Τέλος, μια εναλλακτική προσέγγιση αποτελεί η εφαρμογή της ανάλυσης υπεροχής σε ευριστικούς που δίνουν την βέλτιστη λύση ενός περιορισμού του αρχικού προβλήματος. Ένα τέτοιο παράδειγμα αποτελεί η εφαρμογή των αλγορίθμων Glover - Punnen σε ένα G* γράφημα. Οι αλγόριθμοι αυτοί δίνουν τη βέλτιστη από ένα υποσύνολο όλων των δυνατών λύσεων και συνεπώς σε αυτήν την περίπτωση, ο υπολογισμός του αριθμού υπεροχής ισοδυναμεί με την απαρίθμηση των λύσεων που ανήκουν στο υποσύνολο αυτό.