Το Πρόβλημα του Μετακινούμενου Πωλητή (Travelling Salesman Problem) TSP θέτει το εξής ερώτημα:
Δοθέντος ενός συνόλου πόλεων και των αποστάσεων μεταξύ τους, ποια είναι η συντομότερη δυνατή διαδρομή που επισκέπτεται κάθε πόλη ακριβώς μία φορά και επιστρέφει στην αρχική πόλη;
Το TSP είναι ένα NP-hard πρόβλημα στη συνδυαστική βελτιστοποίηση και αποτελεί θεμελιώδες αντικείμενο μελέτης στη θεωρητική επιστήμη υπολογιστών και την έρευνα επιχειρησιακών διαδικασιών.
Χρησιμοποιείται εκτενώς ως υπόδειγμα για μεθόδους βελτιστοποίησης. Παρόλο που το πρόβλημα είναι υπολογιστικά δύσκολο, περιπτώσεις με δεκάδες χιλιάδες πόλεις έχουν λυθεί ακριβώς, ενώ προσεγγίσεις με πολύ μικρή απόκλιση (περίπου \(1\%\)) επιτυγχάνονται για προβλήματα με εκατομμύρια πόλεις.
Μαθηματική Διατύπωση
Έστω \( G = (V, E) \) ένα πλήρες γράφημα, όπου:
- \( V \) είναι το σύνολο των πόλεων
- \( E \) είναι τα ζεύγη πόλεων με αντίστοιχες αποστάσεις \( d_{ij} \)
Το TSP μπορεί να διατυπωθεί ως: \[ \min \sum_{(i,j) \in E} d_{ij} x_{ij} \] υπό τους περιορισμούς: \[ \sum_{j \in V} x_{ij} = 1, \quad \forall i \in V \] \[ \sum_{i \in V} x_{ij} = 1, \quad \forall j \in V \] \[ \sum_{i,j \in S} x_{ij} \leq |S| - 1, \quad \forall S \subset V, \; 2 \leq |S| \leq |V| - 1 \] όπου: \( x_{ij} \in \{0,1\} \) υποδηλώνει αν η ακμή μεταξύ των πόλεων ( i ) και ( j ) περιλαμβάνεται στη διαδρομή: $x_{ij} = 1$, αν η ακμή επιλέγεται, και $x_{ij} = 0$ διαφορετικά.
Σημείωση
Η έκδοση απόφασης του TSP (ερώτηση: "υπάρχει περιοδεία μήκους το πολύ $L$;") είναι NP-πλήρης.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου