Πρόβλημα του πλανόδιου πωλητή

Το πρόβλημα του πλανόδιου πωλητή (συχνά αποκαλούμενο TSP) είναι ένα κλασικό αλγοριθμικό πρόβλημα στον τομέα της επιστήμης των υπολογιστών και της επιχειρησιακής έρευνας. Επικεντρώνεται στη βελτιστοποίηση. Σε αυτό το πλαίσιο, καλύτερη λύση συχνά σημαίνει μια λύση που είναι φθηνότερη, συντομότερη ή ταχύτερη. Το TSP είναι ένα μαθηματικό πρόβλημα. Εκφράζεται ευκολότερα ως γράφημα που περιγράφει τις θέσεις ενός συνόλου κόμβων.

Το πρόβλημα του πλανόδιου πωλητή ορίστηκε το 1800 από τον Ιρλανδό μαθηματικό W. R. Hamilton και τον Βρετανό μαθηματικό Thomas Kirkman. Το Icosian Game του Χάμιλτον ήταν ένα ψυχαγωγικό παζλ που βασιζόταν στην εύρεση ενός Χαμιλτονιανού κύκλου. Η γενική μορφή του TSP φαίνεται ότι μελετήθηκε για πρώτη φορά από μαθηματικούς κατά τη διάρκεια της δεκαετίας του 1930 στη Βιέννη και στο Χάρβαρντ, κυρίως από τον Karl Menger. Ο Menger ορίζει το πρόβλημα, εξετάζει τον προφανή αλγόριθμο ωμής βίας και παρατηρεί τη μη-βελτιστοποίηση της ευρετικής μεθόδου του πλησιέστερου γείτονα:

Ονομάζουμε με τον όρο πρόβλημα αγγελιοφόρου (αφού στην πράξη το ζήτημα αυτό θα πρέπει να επιλύεται από κάθε ταχυδρόμο, ούτως ή άλλως και από πολλούς ταξιδιώτες) το έργο να βρεθεί, για ﬁκαρία σημεία των οποίων οι αποστάσεις ανά ζεύγη είναι γνωστές, η συντομότερη διαδρομή που συνδέει τα σημεία. Φυσικά, το πρόβληµα αυτό είναι επιλύσιµο µε πεπερασµένα πολλές δοκιµές. Κανόνες που θα ωθούσαν τον αριθμό των δοκιμών κάτω από τον αριθμό των μεταθέσεων των δεδομένων σημείων, δεν είναι γνωστοί. Ο κανόνας ότι πρέπει πρώτα να πάμε από το σημείο εκκίνησης στο πλησιέστερο σημείο, μετά στο πλησιέστερο σε αυτό σημείο κ.λπ., γενικά δεν δίνει τη συντομότερη διαδρομή.

Ο Hassler Whitney στο Πανεπιστήμιο Princeton εισήγαγε το πρόβλημα του πλανόδιου πωλητή αμέσως μετά.

Ένας πωλητής θέλει να επισκεφθεί όλες τις πόλεις, Α, Β, Γ και Δ. Ποιος είναι ο καλύτερος τρόπος για να το κάνει αυτό (φθηνότερα αεροπορικά εισιτήρια και ελάχιστος χρόνος ταξιδιού);

Βέλτιστη διαδρομή ενός πωλητή που επισκέπτεται τις 15 μεγαλύτερες πόλεις της Γερμανίας. Η απεικονιζόμενη διαδρομή είναι η συντομότερη από τις 43.589.145.600 πιθανές.

William Rowan Hamilton

Διατύπωση του προβλήματος

Το πρόβλημα του πλανόδιου πωλητή περιγράφει έναν πωλητή που πρέπει να ταξιδέψει μεταξύ Ν πόλεων. Η σειρά με την οποία το κάνει αυτό είναι κάτι που δεν τον ενδιαφέρει, αρκεί να επισκεφθεί την κάθε μία μία φορά κατά τη διάρκεια του ταξιδιού του και να τερματίσει εκεί που ήταν αρχικά. Κάθε πόλη συνδέεται με άλλες κοντινές πόλεις, ή κόμβους, με αεροπλάνα, ή με οδικό ή σιδηροδρομικό δίκτυο. Κάθε μία από αυτές τις συνδέσεις μεταξύ των πόλεων έχει ένα ή περισσότερα βάρη (ή το κόστος). Το κόστος περιγράφει πόσο "δύσκολο" είναι να διασχίσει κανείς αυτή την ακμή στο γράφημα, και μπορεί να δίνεται, για παράδειγμα, από το κόστος ενός αεροπορικού εισιτηρίου ή ενός εισιτηρίου τρένου, ή ίσως από το μήκος της ακμής, ή από το χρόνο που απαιτείται για να ολοκληρωθεί η διάσχιση. Ο πωλητής θέλει να διατηρήσει τόσο το κόστος ταξιδιού, όσο και την απόσταση που διανύει όσο το δυνατόν χαμηλότερα.

Το πρόβλημα του πλανόδιου πωλητή είναι χαρακτηριστικό μιας μεγάλης κατηγορίας "δύσκολων" προβλημάτων βελτιστοποίησης που απασχολούν τους μαθηματικούς και τους επιστήμονες υπολογιστών εδώ και χρόνια. Το πιο σημαντικό, έχει εφαρμογές στην επιστήμη και τη μηχανική. Για παράδειγμα, κατά την κατασκευή μιας πλακέτας κυκλώματος, είναι σημαντικό να καθοριστεί η καλύτερη σειρά με την οποία ένα λέιζερ θα τρυπήσει χιλιάδες οπές. Μια αποτελεσματική λύση σε αυτό το πρόβλημα μειώνει το κόστος παραγωγής για τον κατασκευαστή.

Δυσκολία

Γενικά, το πρόβλημα του πλανόδιου πωλητή είναι δύσκολο να λυθεί. Εάν υπάρχει τρόπος να σπάσει αυτό το πρόβλημα σε μικρότερα προβλήματα που αποτελούν συνιστώσες, οι συνιστώσες θα είναι τουλάχιστον τόσο πολύπλοκες όσο το αρχικό. Αυτό είναι που οι επιστήμονες πληροφορικής ονομάζουν NP-δύσκολα προβλήματα.

Πολλοί άνθρωποι έχουν μελετήσει αυτό το πρόβλημα. Η ευκολότερη (και πιο δαπανηρή) λύση είναι απλώς να δοκιμάσετε όλα τα ενδεχόμενα. Το πρόβλημα με αυτό είναι ότι για Ν πόλεις έχετε (Ν-1) παραγοντικές δυνατότητες. Αυτό σημαίνει ότι για 10 μόνο πόλεις υπάρχουν πάνω από 180 χιλιάδες συνδυασμοί για να δοκιμάσετε (αφού η πόλη εκκίνησης είναι καθορισμένη, μπορούν να υπάρξουν μεταθέσεις για τις υπόλοιπες εννέα). Μετράμε μόνο τις μισές, αφού κάθε διαδρομή έχει μια ίση διαδρομή αντίστροφα με το ίδιο μήκος ή κόστος. 9! / 2 = 181 440

Μπορούν να βρεθούν ακριβείς λύσεις του προβλήματος, χρησιμοποιώντας αλγορίθμους διακλάδωσης και οριοθέτησης. Αυτό είναι επί του παρόντος δυνατό για έως και 85.900 πόλεις.
Οι ευρετικές προσεγγίσεις χρησιμοποιούν ένα σύνολο κατευθυντήριων κανόνων για την επιλογή του επόμενου κόμβου. Επειδή όμως οι ευρετικές μέθοδοι οδηγούν σε προσεγγίσεις, δεν δίνουν πάντα τη βέλτιστη λύση, αν και οι υψηλής ποιότητας παραδεκτές ευρετικές μέθοδοι μπορούν να βρουν μια χρήσιμη λύση σε ένα κλάσμα του χρόνου που απαιτείται για μια πλήρη ωμή λύση του προβλήματος. Ένα παράδειγμα ευρετικής για έναν κόμβο θα ήταν ένα άθροισμα του πόσοι μη επισκέψιμοι κόμβοι βρίσκονται "κοντά" σε έναν συνδεδεμένο κόμβο. Αυτό θα μπορούσε να ενθαρρύνει τον πωλητή να επισκεφτεί μια ομάδα κόμβων που βρίσκονται κοντά, συγκεντρωμένων μαζί, πριν προχωρήσει σε μια άλλη φυσική συστάδα στο γράφημα. Βλέπε αλγόριθμοι Monte Carlo και αλγόριθμοι Las Vegas.

Ερωτήσεις και απαντήσεις

Q: Τι είναι το πρόβλημα του πλανόδιου πωλητή;

A: Το πρόβλημα του πλανόδιου πωλητή (Traveling Salesman Problem, TSP) είναι ένα κλασικό αλγοριθμικό πρόβλημα στον τομέα της επιστήμης των υπολογιστών και της επιχειρησιακής έρευνας. Επικεντρώνεται στη βελτιστοποίηση, με τις καλύτερες λύσεις να σημαίνουν συχνά φθηνότερες, συντομότερες ή ταχύτερες λύσεις.

Ε: Πώς εκφράζεται το TSP;

Α: Το TSP εκφράζεται ευκολότερα ως γράφος που περιγράφει τις θέσεις ενός συνόλου κόμβων.

Ε: Ποιος όρισε πρώτος την TSP;

Α: Το πρόβλημα του πλανόδιου πωλητή ορίστηκε το 1800 από τον Ιρλανδό μαθηματικό W. R. Hamilton και από τον Βρετανό μαθηματικό Thomas Kirkman.

Ερ: Ποιος το μελέτησε περαιτέρω κατά τη διάρκεια της δεκαετίας του 1930;

Α: Κατά τη διάρκεια της δεκαετίας του 1930, οι μαθηματικοί Karl Menger στη Βιέννη και στο Χάρβαρντ το μελέτησαν περαιτέρω.

Ερ: Τι εισήγαγε ο Χάσλερ Γουίτνεϊ αμέσως μετά;

Α: Ο Hassler Whitney στο Πανεπιστήμιο του Princeton εισήγαγε την ονομασία "πρόβλημα του πλανόδιου πωλητή" λίγο μετά τον ορισμό του.

Ερ: Τι σημαίνει "καλύτερη λύση" σε αυτό το πλαίσιο;

Α: Σε αυτό το πλαίσιο, καλύτερη λύση συχνά σημαίνει μια λύση που είναι φθηνότερη, συντομότερη ή ταχύτερη.

Ερ: Ποιος αλγόριθμος θεωρήθηκε προφανής από τον Menger όταν μελετούσε το TSP;

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