Πρόβλημα ταξιδιώτη πωλητή: Python, C++ Αλγόριθμος
Σάρα Τσεν
Τι είναι το Πρόβλημα του Ταξιδιώτη Πωλητή (TSP);
Το πρόβλημα του ταξιδιωτικού πωλητή (TSP) είναι ένα κλασικό πρόβλημα συνδυαστικής της θεωρητικής επιστήμης των υπολογιστών. Το πρόβλημα ζητά να βρεθεί η συντομότερη διαδρομή σε ένα γράφημα με την προϋπόθεση να επισκεφτούμε όλους τους κόμβους μόνο μία φορά και να επιστρέψουμε στην πόλη προέλευσης.
Η δήλωση προβλήματος δίνει μια λίστα με τις πόλεις μαζί με τις αποστάσεις μεταξύ κάθε πόλης.
Στόχος: Για να ξεκινήσετε από την πόλη προέλευσης, επισκεφθείτε άλλες πόλεις μόνο μία φορά και επιστρέψτε ξανά στην αρχική πόλη. Στόχος μας είναι να βρούμε τη συντομότερη δυνατή διαδρομή για να ολοκληρώσουμε τη διαδρομή μετ' επιστροφής.
Παράδειγμα TSP
Εδώ δίνεται ένα γράφημα όπου τα 1, 2, 3 και 4 αντιπροσωπεύουν τις πόλεις και το βάρος που σχετίζεται με κάθε ακμή αντιπροσωπεύει την απόσταση μεταξύ αυτών των πόλεων.
Ο στόχος είναι να βρεθεί η συντομότερη δυνατή διαδρομή για την περιήγηση που ξεκινά από την πόλη προέλευσης, διασχίζει το γράφημα ενώ επισκέπτεται μόνο μία φορά τις άλλες πόλεις ή κόμβους και επιστρέφει στην πόλη προέλευσης.
Για το παραπάνω γράφημα, η βέλτιστη διαδρομή είναι να ακολουθήσετε τη διαδρομή ελάχιστου κόστους: 1-2-4-3-1. Και αυτή η συντομότερη διαδρομή θα κόστιζε 10+25+30+15 =80
Διαφορετικές λύσεις στο πρόβλημα του ταξιδιώτη πωλητή
Το πρόβλημα του ταξιδιώτη πωλητή (TSP) ταξινομείται ως πρόβλημα NP-σκληρό λόγω του ότι δεν έχει πολυωνυμικό αλγόριθμο χρόνου. Η πολυπλοκότητα αυξάνεται εκθετικά αυξάνοντας τον αριθμό των πόλεων.
Υπάρχουν πολλοί τρόποι για να λύσετε το πρόβλημα του περιοδεύοντος πωλητή (tsp). Μερικές δημοφιλείς λύσεις είναι:
Η προσέγγιση της ωμής δύναμης είναι η αφελής μέθοδος για την επίλυση προβλημάτων ταξιδιωτών πωλητών. Σε αυτή την προσέγγιση, υπολογίζουμε πρώτα όλες τις πιθανές διαδρομές και στη συνέχεια τις συγκρίνουμε. Ο αριθμός των μονοπατιών σε ένα γράφημα που αποτελείται από n πόλεις είναι n! Είναι υπολογιστικά πολύ ακριβό να λυθεί το πρόβλημα του ταξιδιώτη πωλητή σε αυτήν την προσέγγιση ωμής βίας.
Η μέθοδος διακλάδωσης και δέσμευσης: Το πρόβλημα αναλύεται σε υποπροβλήματα σε αυτήν την προσέγγιση. Η λύση αυτών των επιμέρους υποπροβλημάτων θα παρείχε τη βέλτιστη λύση.
Αυτό το σεμινάριο θα παρουσιάσει μια δυναμική προσέγγιση προγραμματισμού, την αναδρομική έκδοση αυτής της μεθόδου διακλάδωσης και δέσμευσης, για την επίλυση του προβλήματος του πλανόδιου πωλητή.
Δυναμικός προγραμματισμός είναι μια τέτοια μέθοδος για την αναζήτηση βέλτιστων λύσεων αναλύοντας όλες τις πιθανές διαδρομές. Είναι μια από τις ακριβείς μεθόδους λύσης που λύνει προβλήματα ταξιδιωτών πωλητών μέσω σχετικά υψηλότερου κόστους από το άπληστες μεθόδους που παρέχουν μια σχεδόν βέλτιστη λύση.
Η υπολογιστική πολυπλοκότητα αυτής της προσέγγισης είναι O(N^2 * 2^N) που συζητείται αργότερα σε αυτό το άρθρο.
Η μέθοδος του πλησιέστερου γείτονα είναι μια ευρετική βασισμένη άπληστη προσέγγιση όπου επιλέγουμε τον πλησιέστερο γειτονικό κόμβο. Αυτή η προσέγγιση είναι υπολογιστικά λιγότερο δαπανηρή από τη δυναμική προσέγγιση. Αλλά δεν παρέχει την εγγύηση για μια βέλτιστη λύση. Αυτή η μέθοδος χρησιμοποιείται για σχεδόν βέλτιστες λύσεις.
Αλγόριθμος για το πρόβλημα του ταξιδιώτη πωλητή
Θα χρησιμοποιήσουμε την προσέγγιση δυναμικού προγραμματισμού για να λύσουμε το Πρόβλημα του Ταξιδιώτη Πωλητή (TSP).
Πριν ξεκινήσουμε τον αλγόριθμο, ας εξοικειωθούμε με ορισμένες ορολογίες:
- Ένα γράφημα G=(V, E), το οποίο είναι ένα σύνολο κορυφών και ακμών.
- V είναι το σύνολο των κορυφών.
- Ε είναι το σύνολο των ακμών.
- Οι κορυφές συνδέονται μέσω άκρων.
- Το Dist(i,j) δηλώνει τη μη αρνητική απόσταση μεταξύ δύο κορυφών, i και j.
Ας υποθέσουμε ότι το S είναι το υποσύνολο των πόλεων και ανήκει στο {1, 2, 3, …, n} όπου 1, 2, 3…n είναι οι πόλεις και i, j είναι δύο πόλεις σε αυτό το υποσύνολο. Τώρα το κόστος(i, S, j) ορίζεται με τέτοιο τρόπο ως το μήκος του συντομότερου μονοπατιού που επισκέπτεται τον κόμβο στο S, ο οποίος ακριβώς μια φορά έχει το σημείο έναρξης και τέλους ως i και j αντίστοιχα.
Για παράδειγμα, το κόστος (1, {2, 3, 4}, 1) υποδηλώνει το μήκος της συντομότερης διαδρομής όπου:
- Η πόλη εκκίνησης είναι 1
- Οι πόλεις 2, 3 και 4 επισκέπτονται μόνο μία φορά
- Το τελικό σημείο είναι 1
Ο δυναμικός αλγόριθμος προγραμματισμού θα είναι:
- Ορίστε το κόστος(i, , i) = 0, που σημαίνει ότι ξεκινάμε και τελειώνουμε στο i και το κόστος είναι 0.
- Πότε |S| > 1, ορίζουμε το κόστος(i, S, 1) = ∝ όπου i !=1 . Επειδή αρχικά, δεν γνωρίζουμε το ακριβές κόστος για να φτάσουμε από την πόλη i στην πόλη 1 μέσω άλλων πόλεων.
- Τώρα, πρέπει να ξεκινήσουμε στη 1 και να ολοκληρώσουμε την περιήγηση. Πρέπει να επιλέξουμε την επόμενη πόλη με τέτοιο τρόπο-
κόστος(i, S, j)=ελάχιστο κόστος (i, S−{i}, j)+dist(i,j) όπου i∈S και i≠j
Για το δεδομένο σχήμα, ο πίνακας γειτνίασης θα ήταν ο ακόλουθος:
| dist(i,j) | 1 | 2 | 3 | 4 |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
Ας δούμε πώς λειτουργεί ο αλγόριθμός μας:
Βήμα 1) Σκεφτόμαστε το ταξίδι μας να ξεκινά από την πόλη 1, να επισκεφτούμε άλλες πόλεις μία φορά και να επιστρέψουμε στην πόλη 1.
Βήμα 2) S είναι το υποσύνολο των πόλεων. Σύμφωνα με τον αλγόριθμό μας, για όλα τα |S| > 1, θα ορίσουμε το κόστος απόστασης(i, S, 1) = ∝. Εδώ το κόστος(i, S, j) σημαίνει ότι ξεκινάμε από την πόλη i, επισκεπτόμαστε τις πόλεις του S μία φορά και τώρα βρισκόμαστε στην πόλη j. Ορίσαμε αυτό το κόστος διαδρομής ως άπειρο γιατί δεν γνωρίζουμε ακόμη την απόσταση. Άρα οι τιμές θα είναι οι εξής:
Κόστος (2, {3, 4}, 1) = ∝ ; ο συμβολισμός υποδηλώνει ότι ξεκινάμε από την πόλη 2, περνάμε από τις πόλεις 3, 4 και φτάνουμε στο 1. Και το κόστος διαδρομής είναι άπειρο. Ομοίως-
κόστος(3, {2, 4}, 1) = ∝
κόστος(4, {2, 3}, 1) = ∝
Βήμα 3) Τώρα, για όλα τα υποσύνολα του S, πρέπει να βρούμε τα εξής:
κόστος(i, S, j)=ελάχιστο κόστος (i, S−{i}, j)+dist(i,j), όπου j∈S και i≠j
Αυτό σημαίνει τη διαδρομή ελάχιστου κόστους για την έναρξη από το i, τη διέλευση από το υποσύνολο των πόλεων μία φορά και την επιστροφή στην πόλη j. Λαμβάνοντας υπόψη ότι το ταξίδι ξεκινά από την πόλη 1, το βέλτιστο κόστος διαδρομής θα ήταν= κόστος(1, {άλλες πόλεις}, 1).
Ας μάθουμε πώς θα μπορούσαμε να το πετύχουμε:
Τώρα S = {1, 2, 3, 4}. Υπάρχουν τέσσερα στοιχεία. Επομένως, ο αριθμός των υποσυνόλων θα είναι 2^4 ή 16. Αυτά τα υποσύνολα είναι-
1) |S| = Μηδενικό:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
Καθώς ξεκινάμε από το 1, θα μπορούσαμε να απορρίψουμε τα υποσύνολα που περιέχουν την πόλη 1.
Υπολογισμός αλγορίθμου:
1) |S| = Φ:
κόστος (2, Φ, 1) = απόσταση (2, 1) = 10
κόστος (3, Φ, 1) = απόσταση (3, 1) = 15
κόστος (4, Φ, 1) = απόσταση (4, 1) = 20
2) |S| = 1:
κόστος (2, {3}, 1) = απόσταση (2, 3) + κόστος (3, Φ, 1) = 35+15 = 50
κόστος (2, {4}, 1) = απόσταση (2, 4) + κόστος (4, Φ, 1) = 25+20 = 45
κόστος (3, {2}, 1) = απόσταση (3, 2) + κόστος (2, Φ, 1) = 35+10 = 45
κόστος (3, {4}, 1) = απόσταση (3, 4) + κόστος (4, Φ, 1) = 30+20 = 50
κόστος (4, {2}, 1) = απόσταση (4, 2) + κόστος (2, Φ, 1) = 25+10 = 35
κόστος (4, {3}, 1) = απόσταση (4, 3) + κόστος (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
κόστος (2, {3, 4}, 1) = ελάχ. [ απόσταση[2,3]+Κόστος(3,{4},1) = 35+50 = 85,
dist[2,4]+Κόστος(4,{3},1) = 25+45 = 70 ] = 70
κόστος (3, {2, 4}, 1) = ελάχ. [ απόσταση[3,2]+Κόστος(2,{4},1) = 35+45 = 80,
dist[3,4]+Κόστος(4,{2},1) = 30+35 = 65 ] = 65
κόστος (4, {2, 3}, 1) = ελάχ. [ απόσταση[4,2]+Κόστος(2,{3},1) = 25+50 = 75
dist[4,3]+Κόστος(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
κόστος (1, {2, 3, 4}, 1) = ελάχ. [ απόσταση[1,2]+Κόστος(2,{3,4},1) = 10+70 = 80
dist[1,3]+Κόστος(3,{2,4},1) = 15+65 = 80
dist[1,4]+Κόστος(4,{2,3},1) = 20+75 = 95 ] = 80
Άρα η βέλτιστη λύση θα ήταν 1-2-4-3-1
Ψευδοκώδικας
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, … , n} of size s
Cost (s, S, 1) = Infinity
for all i Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Υλοποίηση σε Γ/C++
Εδώ είναι η υλοποίηση C++:
#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
int min_cost = MAX;
while(next_permutation(vertex.begin(), vertex.end()))
{
int current_cost = 0;
int j = s;
for (int i = 0; i < vertex.size(); i++) {
current_cost += graph[j][vertex[i]];
j = vertex[i];
}
current_cost += graph[j][s];
min_cost = min(min_cost, current_cost);
return min_cost;
}
}
int main()
{
int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };
int s = 0;
cout << tsp(graph, s) << endl;
return 0;
}
Παραγωγή:
80
Εφαρμογή στο Python
from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_cost = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
current_cost += graph[k][j]
k = j
current_cost += graph[k][s]
min_cost = min(min_cost, current_cost)
return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))
Παραγωγή:
80
Ακαδημαϊκές λύσεις στο TSP
Οι επιστήμονες υπολογιστών έχουν αφιερώσει χρόνια αναζητώντας έναν βελτιωμένο πολυωνυμικό αλγόριθμο χρόνου για το πρόβλημα του ταξιδιώτη πωλητή. Μέχρι τώρα, το πρόβλημα εξακολουθεί να είναι NP-σκληρό.
Αν και μερικές από τις ακόλουθες λύσεις δημοσιεύθηκαν τα τελευταία χρόνια που μείωσαν την πολυπλοκότητα σε κάποιο βαθμό:
- Το κλασικό συμμετρικό TSP επιλύεται με τη μέθοδο Zero Suffix.
- Ο αλγόριθμος βελτιστοποίησης που βασίζεται στη βιογεωγραφία βασίζεται στη στρατηγική μετάβασης για την επίλυση των προβλημάτων βελτιστοποίησης που μπορούν να προγραμματιστούν ως TSP.
- Ο εξελικτικός αλγόριθμος πολλαπλών αντικειμένων έχει σχεδιαστεί για την επίλυση πολλαπλών TSP με βάση το NSGA-II.
- Το σύστημα πολλαπλών πρακτόρων επιλύει το TSP των Ν πόλεων με σταθερούς πόρους.
Εφαρμογή Προβλήματος Περιοδεύοντος Πωλητή
Το Πρόβλημα του Ταξιδιωτικού Πωλητή (TSP) εφαρμόζεται στον πραγματικό κόσμο και στις πιο καθαρές και τροποποιημένες μορφές του. Μερικά από αυτά είναι:
- Σχεδιασμός, logistics και κατασκευή μικροτσίπ: Τα προβλήματα εισαγωγής τσιπ προκύπτουν φυσικά στη βιομηχανία μικροτσίπ. Αυτά τα προβλήματα μπορούν να προγραμματιστούν ως προβλήματα ταξιδιωτικού πωλητή.
- αλληλουχίας DNA: Μικρή τροποποίηση του προβλήματος του περιοδεύοντος πωλητή μπορεί να χρησιμοποιηθεί στον προσδιορισμό της αλληλουχίας DNA. Εδώ, οι πόλεις αντιπροσωπεύουν τα θραύσματα DNA και η απόσταση αντιπροσωπεύει το μέτρο ομοιότητας μεταξύ δύο θραυσμάτων DNA.
- Αστρονομία: Το Πρόβλημα του Ταξιδιώτη Πωλητή εφαρμόζεται από τους αστρονόμους για να ελαχιστοποιηθεί ο χρόνος που αφιερώνεται στην παρατήρηση διαφόρων πηγών.
- Πρόβλημα βέλτιστου ελέγχου: Η διατύπωση Προβλήματος Ταξιδιωτών Πωλητών μπορεί να εφαρμοστεί σε προβλήματα βέλτιστου ελέγχου. Μπορεί να προστεθούν αρκετοί άλλοι περιορισμοί.
Ανάλυση πολυπλοκότητας TSP
- Χρόνος πολυπλοκότητας: Υπάρχουν συνολικά 2N υποπροβλήματα για κάθε κόμβο. Άρα ο συνολικός αριθμός των υποπροβλημάτων θα ήταν N*2N. Κάθε ένα από τα υποπροβλήματα απαιτεί γραμμικό χρόνο για να λυθεί. Εάν ο κόμβος προέλευσης δεν έχει καθοριστεί, πρέπει να εκτελέσουμε βρόχους για Ν κόμβους.
Έτσι, η συνολική χρονική πολυπλοκότητα για μια βέλτιστη λύση θα ήταν ο αριθμός κόμβων * αριθμός υποπροβλημάτων * χρόνος επίλυσης κάθε υποπροβλήματος. Η χρονική πολυπλοκότητα μπορεί να οριστεί ως O(N2 * 2^Ν).
- Διαστημική πολυπλοκότητα: Η προσέγγιση δυναμικού προγραμματισμού χρησιμοποιεί μνήμη για την αποθήκευση C(S, i), όπου το S είναι ένα υποσύνολο του συνόλου κορυφών. Υπάρχουν συνολικά 2N υποσύνολα για κάθε κόμβο. Άρα, η πολυπλοκότητα του χώρου είναι O(2^N).
Στη συνέχεια, θα μάθετε για Αλγόριθμος Κοσκινού Ερατοσθένη
