Μια υλοποίηση του αλγόριθμου του Arora για το πρόβλημα k-TSP

Abstract

Το Πρόβλημα του Πλανώδιου Πωλητή αποτελεί ένα από τα πρώτα γνωστά προβλήματα στην θεωρία των γραφημάτων, του οποίου η δημοφιλία εξηγείται από τις πρακτικές εφαρμογές στις οποίες μία αποδοτική υλοποίηση θα έδινε λύση. Ανά τα χρόνια έχει χρησιμοποιηθεί ως πρόβλημα σταθμός για την αξιολόγηση νέων αλγορίθμων και οι τεχνικές που έχουν εφαρμοστεί προσέφεραν στην Επιστήμη των Υπολογιστών με τις καινοτομίες τους στα θέματα των ευριστικών και προσεγγιστικών τεχνικών. Στην παρούσα έρευνα παρουσιάζεται, επεξηγείται και υλοποιείται ο προσεγγιστικός αλγόριθμος του Sanjeev Arora, ο οποίος μετέπειτα επεκτείνεται ώστε να μπορεί να αντιμετωπίσει και μία παραλλαγή του Προβλήματος του Πλανώδιου Πωλητή, στην οποία ο ζητούμενος αριθμός των κόμβων μίας λύσης διαφοροποιείται από τον ορισμό του αρχικού προβλήματος. Παραθέτονται με επεξηγήσεις κομμάτια ψευδοκώδικα καθώς και αποτελέσματα της εκτέλεσης των αλγορίθμων σε κάθε περίπτωση. Η παρούσα εργασία έχει ως στόχο να αποδείξει ότι αλγόριθμοι με αυστηρή μαθηματική θεμελίωση και μαθηματικά αποδεδειγμένη ακρίβεια είναι δυνατόν να έχουν την πρακτική αξία η οποία έχει πιο συχνά συνδεθεί με τους ευριστικούς αλγορίθμους στη σύγχρονη βιβλιογραφία. Σκοπεύει επίσης να δώσει κατευθυντήριες γραμμές για το πώς θα μπορούσαν να προσαρμοστούν τα τμήματα στα οποία η μεταφορά από τη θεωρία στην πράξη θα οδηγούσαν σε εξαντλητικούς υπολογισμούς.