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

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

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

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

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

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