Reisende selgerproblem: Python, C++ Algoritme

Hva er Traveling Salesman Problem (TSP)?

Den reisende selgerproblemet (TSP) er et klassisk kombinatorisk optimaliseringsproblem innen teoretisk informatikk. Gitt en graf av byer, spør TSP etter den korteste veien som besøker hver node nøyaktig én gang og returnerer til opprinnelsesbyen.

Problemstillingen gir en liste over byer sammen med avstandene mellom hvert bypar.

Målet: Start i startbyen, besøk hver annen by nøyaktig én gang, og returner til startbyen. Målet er å finne den korteste mulige tur-retur-ruten.

Eksempel på TSP

Se på grafen nedenfor, hvor 1, 2, 3 og 4 representerer byene, og vekten på hver kant representerer avstanden mellom disse byene.

Målet er å finne den kortest mulige turen som starter fra opprinnelsesbyen, besøker alle andre byer nøyaktig én gang, og returnerer til opprinnelsesbyen.

For grafen ovenfor er den optimale ruten 1-2-4-3-1Den korteste turkostnaden er 10 + 25 + 30 + 15 = 80.

Forskjellige løsninger på reisende selgerproblem

Problemet med den reisende selgeren er klassifisert som NP-vanskelig fordi ingen kjent polynomisk tidsalgoritme løser det eksakt. Kompleksiteten vokser eksponentielt med antall byer.

Det finnes flere måter å angripe TSP på. De vanligste tilnærmingene er:

Brute Force-tilnærming: Den naive metoden beregner alle mulige turer og sammenligner dem. Antall turer i en graf med n byer er n!, noe som gjør brute force beregningsmessig svært dyrt for alt utover omtrent ti byer.

Gren- og bundet metode: Problemet er delt inn i delproblemer, og løsningene på disse delproblemene kombineres til en optimal løsning. Effektiv beskjæring forkaster delvise turer som ikke kan slå dagens beste kostnad.

Denne veiledningen demonstrerer dynamisk programmeringstilnærming, som er den memobaserte versjonen av branch og bound, og samsvarer med Bellman-Held-Karp-algoritmen.

Dynamisk programmering: Dette er en eksakt metode som søker den optimale løsningen ved å gjenbruke overlappingping resultater for delproblemer. Det er tregere enn det nesten optimale grådige metoder, men det gir alltid en globalt optimal tur.

Beregningskompleksiteten til denne tilnærmingen er O(N² × 2^N), som vi diskuterer senere i artikkelen.

Nærmeste nabo-metode: En heuristisk, grådig tilnærming som alltid hopper til nærmeste ubesøkte by. Den er mye billigere enn dynamisk programmering, men garanterer ikke en optimal tur, så den brukes til nesten optimale løsninger når hastighet er viktigere enn eksakte minima.

Algoritme for reisende selgerproblem

Vi bruker den dynamiske programmeringsmetoden for å løse TSP. Før vi starter algoritmen, la oss avklare noen terminologier:

• En graf G = (V, E) er et sett med hjørner og kanter.
• V er settet med hjørner.
• E er settet med kanter.
• Topppunkter er forbundet gjennom kanter.
• Dist(i, j) betegner den ikke-negative avstanden mellom hjørnene i og j.

Anta at S er en delmengde av byer trukket fra {1, 2, 3, …, n} hvor i og j er to byer i den delmengden. Da cost(i, S, j) er lengden på den korteste ruten som starter ved i, besøker hver by i S nøyaktig én gang, og slutter ved j.

For eksempel, cost(1, {2, 3, 4}, 1) angir den korteste veien der:

• Startby er 1
• Byene 2, 3 og 4 besøkes bare én gang
• Sluttpunktet er 1

Den dynamiske programmeringsrepetansen er:

• Sett cost(i, {}, i) = 0, som betyr at vi starter og slutter på i med null kostnad.
• Når |S| > 1, definere cost(i, S, 1) = ∞ forum i ≠ 1, fordi den faktiske turkostnaden er ukjent ennå.
• Start med by 1, velg den neste byen slik at cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] forum i ∈ S og i ≠ j.

For grafen ovenfor er adjacensmatrisen følgende:

Slik går algoritmen frem:

Trinn 1) Reisen starter i by 1, besøker alle andre byer én gang og går tilbake til by 1.

Trinn 2) S er en delmengde av byer. For hver |S| > 1, initialiser cost(i, S, 1) = ∞. Her cost(i, S, j) betegner en tur som starter ved i, besøker byene i S én gang og når j. Vi starter fra uendelig fordi avstanden er ukjent på dette punktet. Så verdiene er:

cost(2, {3, 4}, 1) = ∞ betyr at vi starter i by 2, går gjennom by 3 og 4, og når 1, med ukjent kostnad. På samme måte:

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

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

Trinn 3) For hver delmengde av S, beregn:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Hvor j ∈ S og i ≠ j.

Det er den billigste turen som starter ved i, besøker delmengden av byer én gang og returnerer til j. Fordi turen starter ved by 1, er den optimale kostnaden cost(1, {other cities}, 1).

Arbeide med gjentakelsen trinn for trinn

Nå er S = {1, 2, 3, 4}. Det er fire elementer, så antallet delmengder er 2^4 = 16Disse delmengdene er:

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

Fordi turen starter i by 1, kan vi forkaste alle delmengder som inneholder by 1 mens vi beregner mellomliggende kostnader.

Algoritmeberegningen utfolder seg som følger:

1) |S| = Φ:

• kostnad(2, Φ, 1) = ford(2, 1) = 10
• kostnad(3, Φ, 1) = ford(3, 1) = 15
• kostnad(4, Φ, 1) = ford(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 optimale løsningen er 1-2-4-3-1.

Pseudokode

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

Her er implementeringen i C++Versjonen nedenfor fikser kildekoden sin tidlige return feilen, som kom tilbake etter den aller første permutasjonen i stedet for å liste opp alle turene.

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

Utgang:

80

Gjennomføring i Python

Ocuco Python implementeringen speiler C++ versjon. Den korrigerer kildens from itertools, import komma-skrivefeil, feilplassert return inne i den indre løkken, og det spredte innrykket 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))

Utgang:

80

Akademiske løsninger til TSP

Dataforskere har brukt flere tiår på å lete etter forbedrede polynomtidsalgoritmer for den reisende selgerproblemet. Så langt er TSP fortsatt NP-hard.

Flere publiserte teknikker reduserer den praktiske kompleksiteten for spesifikke familier av TSP-forekomster:

• Den klassiske symmetriske TSP-en løses av Null suffiks metode.
• Ocuco Biogeografibasert optimaliseringsalgoritme bruker migreringsstrategier for å løse optimaliseringsproblemer som er kartlagt til TSP.
• Ocuco Multi-objektiv evolusjonær algoritme er designet for flermåls-TSP og bygger på NSGA-II.
• Ocuco Multiagentsystem Tilnærmingen løser TSP for N byer med faste beregningsressurser.
• Ocuco Lin-Kernighan heuristisk og dens etterfølger LKH levere turer innenfor 2–3 % av det optimale for tilfeller med millioner av byer.
• Concord bruker skjæreplan og forgrening-og-kutt for å beregne eksakte optima for referanseforekomster med titusenvis av byer.

Anvendelse av Traveling Salesman Problem

Problemet med den reisende selgeren dukker opp i den virkelige verden i både ren og modifisert form. Noen av de viktigste anvendelsene er:

• Planlegging, logistikk og mikrochipproduksjon: Problemer med brikkeinnsetting i mikrobrikkeindustrien modelleres som TSP-varianter for å minimere robotarmens reisetid.
• DNA-sekvensering: En modifisert TSP brukes i DNA-sekvensering der byer representerer DNA-fragmenter og avstander representerer likhet mellom fragmenter.
• Astronomi: Astronomer bruker TSP for å minimere tiden brukt på å dreie teleskoper mellom observasjonsmål.
• Optimal kontroll: TSP-formuleringer modellerer optimale kontrollproblemer der flere begrensninger må overholdes samtidig som traverseringskostnadene minimeres.
• Siste mil levering: Amazon, UPS og matleveringsapper løser dynamiske TSP-varianter for å sekvensere stopp for sjåfører.
• Lagerplukking: Robotiske og menneskelige plukkere følger TSP-optimaliserte ruter som forkorter reisetiden inne i distribusjonssentre.

Kompleksitetsanalyse av TSP

• Tidskompleksitet: Held-Karps dynamiske programmeringsmetod løser 2^N delsett for hver startnode, noe som gir N × 2^N delproblemer. Hvert delproblem tar lineær tid å kombinere. Hvis opprinnelsesnoden er uspesifisert, kreves en ytre løkke over N noder. Den totale tidskompleksiteten er O(N² × 2^N).
• Romkompleksitet: DP-tabellen lagrer C(S, i) for hvert delsett S av toppunktsettet. Det er 2^N delmengder per node, så romkompleksiteten er O(N × 2^N), som ofte skrives som O(2^N) når N behandles som fast.

Lær deretter om Sil av Eratosthenes-algoritmen.

Spørsmål og svar