Πρόβλημα του πλανόδιου πωλητή
αγγλικά : Travelling salesman problem
γαλλικά :
γερμανικά :
Το πρόβλημα του μετακινούμενου πωλητή (που ονομάζεται επίσης και πρόβλημα πλανόδιου πωλητή [1] ή TSP) θέτει την ακόλουθη ερώτηση: "Λαμβάνοντας υπόψη μια λίστα με τις πόλεις και τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων, ποια είναι η συντομότερη διαδρομή που επισκέπτεται κάθε πόλη και επιστρέφει την πόλη προέλευσης; " Πρόκειται για ένα NP-hardness πρόβλημα στη συνδυαστική βελτιστοποίηση, σημαντικό στην έρευνα των λειτουργιών και στη θεωρητική επιστήμη των υπολογιστών.
Η ιδανική διαδρομή για έναν πωλητή μέσω των 15 μεγαλύτερων πόλεων της Γερμανίας. Η δεδομένη διαδρομή είναι η συντομότερη δυνατή από 43589145600 δυνατές διαδρομές.
Το πρόβλημα του αγοραστή που ταξιδεύει και το πρόβλημα της δρομολόγησης του οχήματος είναι και τα δύο γενικεύσεις του TSP.
Στη θεωρία της υπολογιστικής πολυπλοκότητας, η έκδοση απόφασης του TSP (όπου δόθηκε ένα μήκος L, ο σκοπός είναι να αποφασίσει αν το γράφημα έχει περιοδεία το πολύ L) ανήκει στην τάξη NP-πλήρων προβλημάτων. Επομένως, είναι πιθανό ότι ο χειρότερος χρόνος εκτέλεσης για οποιονδήποτε αλγόριθμο για το TSP αυξάνεται πολυωνυμικά (αλλά όχι περισσότερο από εκθετικά) με τον αριθμό των πόλεων.
Το πρόβλημα διατυπώθηκε για πρώτη φορά το 1930 και είναι ένα από τα πιο έντονα μελετημένα προβλήματα βελτιστοποίησης. Χρησιμοποιείται ως σημείο αναφοράς για πολλές μεθόδους βελτιστοποίησης. Αν και το πρόβλημα είναι υπολογιστικά δύσκολο, είναι γνωστοί πολλά θεωρητικοί και ακριβείς αλγόριθμοι, έτσι ώστε ορισμένες περιπτώσεις με δεκάδες χιλιάδες πόλεις να μπορούν να λυθούν πλήρως και ακόμη και προβλήματα με εκατομμύρια πόλεις μπορούν να προσεγγιστούν με ένα μικρό ποσοστό απόκλισης της τάξης του 1%[2].
Το TSP έχει αρκετές εφαρμογές ακόμα και στην απλούστερη μορφή του, όπως ο σχεδιασμός, η εφοδιαστική και η κατασκευή μικροτσίπ. Ελαφρώς τροποποιημένο, εμφανίζεται ως υποπρόβλημα σε πολλές περιοχές, όπως το DNA sequencing. Σε αυτές τις εφαρμογές, η έννοια της πόλης αντιπροσωπεύει, για παράδειγμα, πελάτες, σημεία συγκόλλησης ή DNA fragments και η έννοια της απόστασης (distance) αντιπροσωπεύει τους χρόνους μετακίνησης ή το κόστος ή ένα μέτρο ομοιότητας μεταξύ DNA fragments. Το TSP εμφανίζεται επίσης στην αστρονομία, καθώς οι αστρονόμοι που παρατηρούν πολλές πηγές θα θέλουν να ελαχιστοποιήσουν το χρόνο που αφιερώνουν τη μετακίνηση του τηλεσκοπίου μεταξύ των πηγών. Σε πολλές εφαρμογές, μπορούν να επιβληθούν πρόσθετοι περιορισμοί, όπως περιορισμένοι πόροι ή χρονικά παράθυρα.
Σημειώσεις
Google scholar search for "Traveling Salesperson Problemreturns thousands of results of articles spanning twenty years. Retrieved November 23, 2019.
See the TSP world tour problem which has already been solved to within 0.05% of the optimal solution.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
