Πρόβλημα ταξιδιώτη πωλητή: Python, C++ Αλγόριθμος

Τι είναι το Πρόβλημα του Ταξιδιώτη Πωλητή (TSP);

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

Η δήλωση προβλήματος παρέχει μια λίστα πόλεων μαζί με τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων.

Στόχος: Ξεκινήστε από την πόλη προέλευσης, επισκεφθείτε κάθε άλλη πόλη ακριβώς μία φορά και επιστρέψτε στην πόλη εκκίνησης. Στόχος είναι να βρείτε τη συντομότερη δυνατή διαδρομή μετ' επιστροφής.

Παράδειγμα TSP

Σκεφτείτε το παρακάτω γράφημα όπου τα 1, 2, 3 και 4 αντιπροσωπεύουν τις πόλεις και το βάρος σε κάθε ακμή αντιπροσωπεύει την απόσταση μεταξύ αυτών των πόλεων.

Ο στόχος είναι να βρεθεί η συντομότερη δυνατή περιήγηση που ξεκινά από την πόλη προέλευσης, επισκέπτεται κάθε άλλη πόλη ακριβώς μία φορά και επιστρέφει στην πόλη προέλευσης.

Για το παραπάνω γράφημα, η βέλτιστη διαδρομή είναι 1-2-4-3-1Το συντομότερο κόστος εκδρομής είναι 10 + 25 + 30 + 15 = 80.

Διαφορετικές λύσεις στο πρόβλημα του ταξιδιώτη πωλητή

Το πρόβλημα του περιοδεύοντος πωλητή ταξινομείται ως NP-hard επειδή κανένας γνωστός αλγόριθμος πολυωνυμικού χρόνου δεν το λύνει ακριβώς. Η πολυπλοκότητα αυξάνεται εκθετικά με τον αριθμό των πόλεων.

Υπάρχουν πολλοί τρόποι για να επιτεθεί κανείς σε TSP. Οι πιο συνηθισμένες προσεγγίσεις είναι:

Προσέγγιση ωμής βίας: Η απλοϊκή μέθοδος υπολογίζει κάθε πιθανή περιήγηση και τη συγκρίνει. Ο αριθμός των περιηγήσεων σε ένα γράφημα με n πόλεις είναι n!, γεγονός που καθιστά την ωμή βία υπολογιστικά πολύ ακριβή για οτιδήποτε πέρα ​​από περίπου δέκα πόλεις.

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

Αυτό το σεμινάριο παρουσιάζει το δυναμική προσέγγιση προγραμματισμού, η οποία είναι η απομνημονευμένη έκδοση της διακλάδωσης και του ορίου και ταιριάζει με τον αλγόριθμο Bellman-Held-Karp.

Δυναμικός Προγραμματισμός: Αυτή είναι μια ακριβής μέθοδος που αναζητά τη βέλτιστη λύση επαναχρησιμοποιώντας την επικάλυψηping αποτελέσματα υποπροβλήματος. Είναι πιο αργό από το σχεδόν βέλτιστο άπληστες μεθόδους, αλλά πάντα επιστρέφει μια παγκοσμίως βέλτιστη περιήγηση.

Η υπολογιστική πολυπλοκότητα αυτής της προσέγγισης είναι O(N² × 2^N), την οποία θα συζητήσουμε αργότερα στο άρθρο.

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

Αλγόριθμος για το πρόβλημα του ταξιδιώτη πωλητή

Χρησιμοποιούμε την προσέγγιση δυναμικού προγραμματισμού για την επίλυση προβλημάτων TSP. Πριν ξεκινήσουμε τον αλγόριθμο, ας διευκρινίσουμε μερικές ορολογίες:

• Ένα γράφημα G = (V, E) είναι ένα σύνολο κορυφών και ακμών.
• V είναι το σύνολο των κορυφών.
• E είναι το σύνολο των ακμών.
• Οι κορυφές συνδέονται μέσω άκρων.
• Dist(i, j) δηλώνει τη μη αρνητική απόσταση μεταξύ των κορυφών i και j.

Υποθέστε ότι το S είναι ένα υποσύνολο πόλεων που προέρχονται από {1, 2, 3, …, n} όπου i και j είναι δύο πόλεις σε αυτό το υποσύνολο. Τότε cost(i, S, j) είναι το μήκος της συντομότερης διαδρομής που ξεκινά από το σημείο i, επισκέπτεται κάθε πόλη στο S ακριβώς μία φορά και τελειώνει στο σημείο j.

Για παράδειγμα, cost(1, {2, 3, 4}, 1) υποδηλώνει τη συντομότερη διαδρομή όπου:

• Η πόλη εκκίνησης είναι 1
• Οι πόλεις 2, 3 και 4 επισκέπτονται μόνο μία φορά
• Το τελικό σημείο είναι 1

Η δυναμική επαναληπτικότητα προγραμματισμού είναι:

• σετ cost(i, {}, i) = 0, που σημαίνει ότι ξεκινάμε και τελειώνουμε στο i με μηδενικό κόστος.
• Κατά τη |S| > 1, ορισμός cost(i, S, 1) = ∞ για i ≠ 1, επειδή το πραγματικό κόστος της εκδρομής είναι ακόμη άγνωστο.
• Ξεκινώντας από την πόλη 1, επιλέξτε την επόμενη πόλη έτσι ώστε cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] για i ∈ S και i ≠ j.

Για το παραπάνω γράφημα, ο πίνακας γειτνίασης είναι ο ακόλουθος:

Να πώς προχωρά ο αλγόριθμος:

Βήμα 1) Το ταξίδι ξεκινά από την πόλη 1, επισκέπτεται κάθε άλλη πόλη μία φορά και επιστρέφει στην πόλη 1.

Βήμα 2) Το S είναι ένα υποσύνολο πόλεων. Για κάθε |S| > 1, αρχικοποιήστε cost(i, S, 1) = ∞. Εδώ cost(i, S, j) δηλώνει μια περιήγηση που ξεκινά από το i, επισκέπτεται τις πόλεις στο S μία φορά και φτάνει στο j. Ξεκινάμε από το άπειρο επειδή η απόσταση είναι άγνωστη σε αυτό το σημείο. Έτσι, οι τιμές είναι:

cost(2, {3, 4}, 1) = ∞ σημαίνει ότι ξεκινάμε από την πόλη 2, περνάμε από τις πόλεις 3 και 4 και φτάνουμε στην πόλη 1, με άγνωστο κόστος. Ομοίως:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Βήμα 3) Για κάθε υποσύνολο του S, υπολογίστε:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Όπου j ∈ S και i ≠ j.

Αυτή είναι η περιήγηση με το ελάχιστο κόστος που ξεκινά από το i, επισκέπτεται το υποσύνολο των πόλεων μία φορά και επιστρέφει στο j. Επειδή η περιήγηση ξεκινά από την πόλη 1, το βέλτιστο κόστος είναι cost(1, {other cities}, 1).

Εργασία με την Επανάληψη Βήμα προς Βήμα

Τώρα S = {1, 2, 3, 4}. Υπάρχουν τέσσερα στοιχεία, άρα ο αριθμός των υποσυνόλων είναι 2^4 = 16Αυτά τα υποσύνολα είναι:

1) |S| = 0: {Φ}

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, απόσταση(2, 4) + κόστος(4, {3}, 1) = 25 + 45 = 70 ] = 70
• κόστος(3, {2, 4}, 1) = ελάχιστο [ απόσταση(3, 2) + κόστος(2, {4}, 1) = 35 + 45 = 80, απόσταση(3, 4) + κόστος(4, {2}, 1) = 30 + 35 = 65 ] = 65
• κόστος(4, {2, 3}, 1) = ελάχιστο [ απόσταση(4, 2) + κόστος(2, {3}, 1) = 25 + 50 = 75, απόσταση(4, 3) + κόστος(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

Υλοποίηση σε Γ/C++

Εδώ είναι η υλοποίηση σε C++Η παρακάτω έκδοση διορθώνει το πρώιμο σφάλμα του πηγαίου κώδικα return σφάλμα, το οποίο επέστρεψε μετά την πρώτη κιόλας μετάθεση αντί να απαριθμήσει όλες τις περιηγήσεις.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

The Python η εφαρμογή αντικατοπτρίζει την C++ έκδοση. Διορθώνει την πηγή from itertools, import τυπογραφικό λάθος με κόμμα, το λάθος τοποθετημένο return μέσα στον εσωτερικό βρόχο και την αδέσποτη εσοχή στο s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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

Οι επιστήμονες υπολογιστών έχουν αφιερώσει δεκαετίες στην αναζήτηση βελτιωμένων αλγορίθμων πολυωνυμικού χρόνου για το πρόβλημα του περιοδεύοντος πωλητή. Μέχρι στιγμής, το TSP παραμένει NP-hard.

Αρκετές δημοσιευμένες τεχνικές μειώνουν την πρακτική πολυπλοκότητα για συγκεκριμένες οικογένειες στιγμιότυπων TSP:

• Το κλασικό συμμετρικό TSP λύνεται από την Μέθοδος μηδενικού επιθήματος.
• The Αλγόριθμος Βελτιστοποίησης Βασισμένος στη Βιογεωγραφία χρησιμοποιεί στρατηγικές μετεγκατάστασης για την επίλυση προβλημάτων βελτιστοποίησης που αντιστοιχίζονται σε TSP.
• The Πολυστόχικός Εξελικτικός Αλγόριθμος Έχει σχεδιαστεί για TSP πολλαπλών στόχων και βασίζεται στο NSGA-II.
• The Σύστημα πολλαπλών πρακτόρων Η προσέγγιση αυτή λύνει το TSP για N πόλεις με σταθερούς υπολογιστικούς πόρους.
• The Ευρετική Lin-Kernighan και του διαδόχου της LKH προσφέρουν περιηγήσεις εντός 2-3% του βέλτιστου για εκδηλώσεις με εκατομμύρια πόλεις.
• Ομόνοια Χρησιμοποιεί επίπεδα κοπής και μέθοδο διακλάδωσης και κοπής για να υπολογίσει τα ακριβή βέλτιστα για στιγμιότυπα αναφοράς με δεκάδες χιλιάδες πόλεις.

Εφαρμογή Προβλήματος Περιοδεύοντος Πωλητή

Το Πρόβλημα του Περιοδεύοντος Πωλητή εμφανίζεται στον πραγματικό κόσμο τόσο σε καθαρή όσο και σε τροποποιημένη μορφή. Μερικές από τις κύριες εφαρμογές είναι:

• Σχεδιασμός, εφοδιαστική και κατασκευή μικροτσίπ: Τα προβλήματα εισαγωγής τσιπ στη βιομηχανία μικροτσίπ μοντελοποιούνται ως παραλλαγές TSP για την ελαχιστοποίηση του χρόνου ταξιδιού του βραχίονα του ρομπότ.
• Αλληλούχιση DNA: Ένα τροποποιημένο TSP χρησιμοποιείται στην αλληλούχιση DNA όπου οι πόλεις αντιπροσωπεύουν θραύσματα DNA και οι αποστάσεις αντιπροσωπεύουν ομοιότητα μεταξύ θραυσμάτων.
• Αστρονομία: Οι αστρονόμοι χρησιμοποιούν το TSP για να ελαχιστοποιήσουν τον χρόνο που αφιερώνεται στην περιστροφή των τηλεσκοπίων μεταξύ των στόχων παρατήρησης.
• Βέλτιστος έλεγχος: Οι διατυπώσεις TSP μοντελοποιούν προβλήματα βέλτιστου ελέγχου όπου πρέπει να τηρούνται πολλαπλοί περιορισμοί, ελαχιστοποιώντας παράλληλα το κόστος διέλευσης.
• Παράδοση στο τελευταίο μίλι: Amazon, η UPS και οι εφαρμογές παράδοσης φαγητού επιλύουν δυναμικές παραλλαγές TSP για την αλληλουχία στάσεων για τους οδηγούς.
• Συλλογή από αποθήκη: Οι ρομποτικοί και ανθρώπινοι συλλέκτες ακολουθούν διαδρομές βελτιστοποιημένες από το TSP που μειώνουν τον χρόνο ταξιδιού μέσα στα κέντρα διανομής.

Ανάλυση πολυπλοκότητας TSP

• Χρόνος πολυπλοκότητας: Η προσέγγιση δυναμικού προγραμματισμού Held-Karp λύνει 2^N υποσύνολα για κάθε αρχικό κόμβο, δίνοντας N × 2^N υποπροβλήματα. Κάθε υποπρόβλημα απαιτεί γραμμικό χρόνο για να συνδυαστεί. Εάν ο κόμβος προέλευσης δεν είναι καθορισμένος, απαιτείται ένας εξωτερικός βρόχος σε N κόμβους. Η συνολική χρονική πολυπλοκότητα είναι O(N² × 2^N).
• Διαστημική πολυπλοκότητα: Ο πίνακας DP αποθηκεύει C(S, i) για κάθε υποσύνολο S του συνόλου κορυφών. Υπάρχουν 2^N υποσύνολα ανά κόμβο, επομένως η πολυπλοκότητα του χώρου είναι O(N × 2^N), το οποίο συχνά γράφεται ως O(2^N) όταν το N αντιμετωπίζεται ως σταθερό.

Στη συνέχεια, μάθετε για το Αλγόριθμος Κοσκινού Ερατοσθένη.

Συχνές Ερωτήσεις