Problem med resande säljare: Python, C++ Algoritm

Vad är problemet med resande säljare (TSP)?

Den resande säljarens problem (TSP) är ett klassiskt kombinatoriskt optimeringsproblem inom teoretisk datavetenskap. Givet en graf över städer frågar TSP efter den kortaste vägen som besöker varje nod exakt en gång och återvänder till ursprungsstaden.

Problemformuleringen ger en lista över städer tillsammans med avstånden mellan varje par av städer.

Mål: Börja vid startstaden, besök varannan stad exakt en gång och återvänd till startstaden. Målet är att hitta den kortaste möjliga vägen tur och retur.

Exempel på TSP

Betrakta grafen nedan där 1, 2, 3 och 4 representerar städerna, och vikten på varje kant representerar avståndet mellan dessa städer.

Målet är att hitta den kortast möjliga turen som börjar från ursprungsstaden, besöker varannan stad exakt en gång och återvänder till ursprungsstaden.

För grafen ovan är den optimala rutten 1-2-4-3-1Den kortaste turkostnaden är 10 + 25 + 30 + 15 = 80.

Olika lösningar på problem med resande säljare

Problemet med den resande säljaren klassificeras som NP-svårt eftersom ingen känd polynomtidsalgoritm löser det exakt. Komplexiteten växer exponentiellt med antalet städer.

Det finns flera sätt att attackera TSP. De vanligaste metoderna är:

Brute Force-metoden: Den naiva metoden beräknar alla möjliga turer och jämför dem. Antalet turer i en graf med n städer är n!, vilket gör brute force beräkningsmässigt mycket dyrt för allt utöver cirka tio städer.

Gren- och bunden metod: Problemet är uppdelat i delproblem, och lösningarna till dessa delproblem kombineras till en optimal lösning. Effektiv beskärning eliminerar partiella turer som inte kan slå den nuvarande bästa kostnaden.

Den här handledningen demonstrerar dynamisk programmeringsmetod, vilket är den memoiserade versionen av branch och bound och matchar Bellman-Held-Karp-algoritmen.

Dynamisk programmering: Detta är en exakt metod som söker den optimala lösningen genom att återanvända överlappningping delproblemresultat. Det är långsammare än det nästan optimala giriga metoder, men det ger alltid en globalt optimal tur.

Beräkningskomplexiteten i detta tillvägagångssätt är O(N² × 2^N), vilket vi diskuterar senare i artikeln.

Närmaste granne-metod: En heuristisk girig metod som alltid hoppar till närmaste obesökta stad. Den är mycket billigare än dynamisk programmering men garanterar inte en optimal tur, så den används för nästan optimala lösningar när hastighet är viktigare än exakta minima.

Algoritm för resande säljareproblem

Vi använder dynamisk programmering för att lösa TSP. Innan vi börjar med algoritmen, låt oss klargöra några terminologier:

• En graf G = (V, E) är en mängd av noder och kanter.
• V är mängden av noder.
• E är mängden kanter.
• Vertices är förbundna genom kanter.
• Dist(i, j) betecknar det icke-negativa avståndet mellan noderna i och j.

Antag att S är en delmängd av städer ritade från {1, 2, 3, …, n} där i och j är två städer i den delmängden. Då cost(i, S, j) är längden på den kortaste vägen som börjar vid i, besöker varje stad i S exakt en gång och slutar vid j.

Till exempel, cost(1, {2, 3, 4}, 1) betecknar den kortaste vägen där:

• Startstad är 1
• Städerna 2, 3 och 4 besöks endast en gång
• Slutpunkten är 1

Den dynamiska programmeringsupprepningen är:

• uppsättning cost(i, {}, i) = 0, vilket innebär att vi börjar och slutar vid i med noll kostnad.
• När |S| > 1, definiera cost(i, S, 1) = ∞ för i ≠ 1, eftersom den faktiska kostnaden för resan ännu är okänd.
• Börja med stad 1 och välj nästa stad så att cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] för i ∈ S och i ≠ j.

För grafen ovan är adjacentmatrisen följande:

Så här går algoritmen till:

Steg 1) Resan börjar i stad 1, besöker alla andra städer en gång och återvänder till stad 1.

Steg 2) S är en delmängd av städer. För varje |S| > 1, initiera cost(i, S, 1) = ∞. Här cost(i, S, j) betecknar en tur som börjar vid i, besöker städerna i S en gång och når j. Vi börjar från oändligheten eftersom avståndet är okänt vid denna punkt. Så värdena är:

cost(2, {3, 4}, 1) = ∞ betyder att vi börjar i stad 2, går igenom städer 3 och 4, och når 1, med okänd kostnad. På liknande sätt:

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

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

Steg 3) För varje delmängd av S, beräkna:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]Där j ∈ S och i ≠ j.

Det är den lägsta kostnadsturen som börjar vid i, besöker delmängden av städer en gång och återvänder till j. Eftersom turen börjar vid stad 1 är den optimala kostnaden cost(1, {other cities}, 1).

Arbeta med repetitionen steg för steg

Nu är S = {1, 2, 3, 4}. Det finns fyra element, så antalet delmängder är 2^4 = 16Dessa delmängder är:

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}}

Eftersom rundturen börjar i stad 1 kan vi ignorera alla delmängder som innehåller stad 1 när vi beräknar mellanliggande kostnader.

Algoritmberäkningen utvecklas enligt följande:

1) |S| = Φ:

• kostnad(2, Φ, 1) = dist(2, 1) = 10
• kostnad(3, Φ, 1) = dist(3, 1) = 15
• kostnad(4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

• kostnad(2, {3}, 1) = dist(2, 3) + kostnad(3, Φ, 1) = 35 + 15 = 50
• kostnad(2, {4}, 1) = dist(2, 4) + kostnad(4, Φ, 1) = 25 + 20 = 45
• kostnad(3, {2}, 1) = dist(3, 2) + kostnad(2, Φ, 1) = 35 + 10 = 45
• kostnad(3, {4}, 1) = dist(3, 4) + kostnad(4, Φ, 1) = 30 + 20 = 50
• kostnad(4, {2}, 1) = dist(4, 2) + kostnad(2, Φ, 1) = 25 + 10 = 35
• kostnad(4, {3}, 1) = dist(4, 3) + kostnad(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• kostnad(2, {3, 4}, 1) = min [ dist(2, 3) + kostnad(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + kostnad(4, {3}, 1) = 25 + 45 = 70 ] = 70
• kostnad(3, {2, 4}, 1) = min [ dist(3, 2) + kostnad(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + kostnad(4, {2}, 1) = 30 + 35 = 65 ] = 65
• kostnad(4, {2, 3}, 1) = min [ dist(4, 2) + kostnad(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + kostnad(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• kostnad(1, {2, 3, 4}, 1) = min [ dist(1, 2) + kostnad(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + kostnad(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + kostnad(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Så den optimala lösningen är 1-2-4-3-1.

Pseudokod

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)

Implementering i C/C++

Här är implementeringen i C++Versionen nedan åtgärdar källkoden tidiga return bugg, som återkom efter den allra första permutationen istället för att räkna upp alla turer.

#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;
}

Produktion:

80

Genomförande i Python

Ocuco-landskapet Python implementeringen speglar C++ version. Den korrigerar källans from itertools, import kommafel, felplacerat return inuti den inre slingan, och den lösryckta indragningen på 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))

Produktion:

80

Akademiska lösningar till TSP

Datavetare har ägnat årtionden åt att leta efter förbättrade polynomtidsalgoritmer för den resande säljarens problem. Hittills är TSP fortfarande NP-svårt.

Flera publicerade tekniker minskar den praktiska komplexiteten för specifika familjer av TSP-instanser:

• Den klassiska symmetriska TSP:n löses med Noll suffixmetod.
• Ocuco-landskapet Biogeografibaserad optimeringsalgoritm använder migreringsstrategier för att lösa optimeringsproblem som mappas till TSP.
• Ocuco-landskapet Multiobjektiv evolutionär algoritm är utformad för TSP med flera mål och bygger på NSGA-II.
• Ocuco-landskapet Multi-Agent System Metoden löser TSP för N städer med fasta beräkningsresurser.
• Ocuco-landskapet Lin-Kernighan heuristisk och dess efterföljare LKH leverera turer inom 2–3 % av det optimala för instanser med miljontals städer.
• Concord använder skärplan och förgrening-och-skärning för att beräkna exakta optima för riktmärkesinstanser med tiotusentals städer.

Tillämpning av resande säljareproblem

Problemet med den resande säljaren uppträder i den verkliga världen i både ren och modifierad form. Några av de viktigaste tillämpningarna är:

• Planering, logistik och mikrochiptillverkning: Problem med chipinsättning i mikrochipindustrin modelleras som TSP-varianter för att minimera robotarmens restid.
• DNA-sekvensering: En modifierad TSP används vid DNA-sekvensering där städer representerar DNA-fragment och avstånd representerar likhet mellan fragment.
• Astronomi: Astronomer använder TSP för att minimera den tid som går åt till att vrida teleskop mellan observationsmål.
• Optimal kontroll: TSP-formuleringar modellerar optimala kontrollproblem där flera begränsningar måste respekteras samtidigt som traverseringskostnaden minimeras.
• Sista milen leverans: Amazon, UPS och matleveransappar löser dynamiska TSP-varianter för att sekvensera stopp för förare.
• Lagerplockning: Robotiska och mänskliga plockare följer TSP-optimerade rutter som förkortar restiderna inom distributionscentraler.

Komplexitetsanalys av TSP

• Tidskomplexitet: Held-Karps dynamiska programmeringsmetod löser 2^N delmängder för varje startnod, vilket ger N × 2^N delproblem. Varje delproblem tar linjär tid att kombinera. Om ursprungsnoden är ospecificerad krävs en yttre loop över N noder. Den totala tidskomplexiteten är O(N² × 2^N).
• Rymdkomplexitet: DP-tabellen lagrar C(S, i) för varje delmängd S av nodermängden. Det finns 2^N delmängder per nod, så rymdkomplexiteten är O(N × 2^N), vilket ofta skrivs som O(2^N) när N behandlas som fixerad.

Lär dig sedan om Sieve of Eratosthenes Algorithm.

Vanliga frågor