Rejsende sælger problem: Python, C++ Algoritme

Hvad er Traveling Salesman Problem (TSP)?

Den Rejsende Sælgers Problem (TSP) er et klassisk kombinatorisk optimeringsproblem inden for teoretisk datalogi. Givet en graf over byer, spørger TSP efter den korteste vej, der besøger hver node præcis én gang og vender tilbage til oprindelsesbyen.

Problemformuleringen indeholder en liste over byer sammen med afstandene mellem hvert par af byer.

Formål: Start i oprindelsesbyen, besøg hver anden by præcis én gang, og vend tilbage til startbyen. Målet er at finde den kortest mulige rundtur.

Eksempel på TSP

Se grafen nedenfor, hvor 1, 2, 3 og 4 repræsenterer byerne, og vægten på hver kant repræsenterer afstanden mellem disse byer.

Målet er at finde den kortest mulige tur, der starter fra oprindelsesbyen, besøger alle andre byer præcis én gang og vender tilbage til oprindelsesbyen.

For ovenstående graf er den optimale rute 1-2-4-3-1Den korteste turpris er 10 + 25 + 30 + 15 = 80.

Forskellige løsninger på rejsende sælgerproblem

Problemet med den rejsende sælger klassificeres som NP-svært, fordi ingen kendt polynomialtidsalgoritme løser det præcist. Kompleksiteten vokser eksponentielt med antallet af byer.

Der er flere måder at angribe TSP på. De mest almindelige tilgange er:

Brute Force-tilgang: Den naive metode beregner alle mulige ture og sammenligner dem. Antallet af ture i en graf med n byer er n!, hvilket gør brute force beregningsmæssigt meget dyrt for alt ud over omkring ti byer.

Forgrenings- og bundmetoden: Problemet er opdelt i delproblemer, og løsningerne på disse delproblemer kombineres til en optimal løsning. Effektiv beskæring fjerner delvise ture, der ikke kan slå den nuværende bedste pris.

Denne vejledning demonstrerer dynamisk programmeringstilgang, som er den memoserede version af branch og bound og matcher Bellman-Held-Karp-algoritmen.

Dynamisk programmering: Dette er en præcis metode, der søger den optimale løsning ved at genbruge overlapping resultater for delproblemer. Det er langsommere end det næsten optimale grådige metoder, men det returnerer altid en globalt optimal tur.

Den beregningsmæssige kompleksitet af denne tilgang er O(N² × 2^N), som vi diskuterer senere i artiklen.

Nærmeste nabo-metode: En heuristisk, grådig tilgang, der altid hopper til den nærmeste ubesøgte by. Den er meget billigere end dynamisk programmering, men garanterer ikke en optimal tur, så den bruges til næsten optimale løsninger, når hastighed er vigtigere end præcise minima.

Algoritme for rejsende sælgerproblem

Vi bruger den dynamiske programmeringsmetode til at løse TSP. Før vi starter algoritmen, lad os afklare et par terminologier:

• En graf G = (V, E) er et sæt af hjørner og kanter.
• V er mængden af ​​hjørner.
• E er mængden af ​​kanter.
• Hjørner er forbundet gennem kanter.
• Dist(i, j) betegner den ikke-negative afstand mellem hjørnerne i og j.

Antag at S er en delmængde af byer trukket fra {1, 2, 3, …, n}, hvor i og j er to byer i den delmængde. Så cost(i, S, j) er længden af ​​den korteste rute, der starter ved i, besøger hver by i S præcis én gang og slutter ved j.

For eksempel: cost(1, {2, 3, 4}, 1) angiver den korteste vej, hvor:

• Startby er 1
• By 2, 3 og 4 besøges kun én gang
• Slutpunktet er 1

Den dynamiske programmeringsgentagelse er:

• sæt cost(i, {}, i) = 0, hvilket betyder, at vi starter og slutter ved i med nul omkostninger.
• Når |S| > 1, definere cost(i, S, 1) = ∞ forum i ≠ 1, fordi den reelle pris for turen endnu ikke er kendt.
• Start med by 1, og vælg den næste by, så cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] forum i ∈ S og i ≠ j.

For grafen ovenfor er adjacensmatricen følgende:

Sådan forløber algoritmen:

Trin 1) Rejsen starter i by 1, besøger alle andre byer én gang og vender tilbage til by 1.

Trin 2) S er en delmængde af byer. For hver |S| > 1, initialiser cost(i, S, 1) = ∞. Her cost(i, S, j) betegner en tur, der starter ved i, besøger byerne i S én gang og når til j. Vi starter fra uendeligheden, fordi afstanden er ukendt på dette punkt. Så værdierne er:

cost(2, {3, 4}, 1) = ∞ betyder, at vi starter i by 2, går gennem by 3 og 4 og når frem til 1, med ukendte omkostninger. Tilsvarende:

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

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

Trin 3) For hver delmængde af S, beregn:

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

Det er den minimale tur, der starter ved i, besøger delmængden af ​​byer én gang og vender tilbage til j. Fordi turen starter ved by 1, er den optimale pris cost(1, {other cities}, 1).

Arbejd med gentagelsen trin for trin

Nu er S = {1, 2, 3, 4}. Der er fire elementer, så antallet af delmængder er 2^4 = 16Disse delmængder 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 kassere alle delmængder, der indeholder by 1, mens vi beregner mellemliggende omkostninger.

Algoritmeberegningen udfolder sig som følger:

1) |S| = Φ:

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

2) |S| = 1:

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

3) |S| = 2:

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

4) |S| = 3:

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

Så den optimale løsning er 1-2-4-3-1.

Pseudo-kode

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++Versionen nedenfor retter kildekoden tidligt return fejl, som vendte tilbage efter den allerførste permutation i stedet for at opregne alle ture.

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

Output:

80

Gennemførelse i Python

Python implementeringen afspejler C++ version. Den korrigerer kildens from itertools, import komma-tastefejl, den forkert placerede return indeni den indre løkke, og det tilfældige indryk 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))

Output:

80

Akademiske løsninger til TSP

Dataloger har brugt årtier på at søge efter forbedrede polynomialtidsalgoritmer til den rejsende sælgers problem. Indtil videre er TSP stadig NP-hård.

Adskillige publicerede teknikker reducerer den praktiske kompleksitet for specifikke familier af TSP-instanser:

• Den klassiske symmetriske TSP løses ved Nul-suffiksmetode.
• Biogeografibaseret optimeringsalgoritme bruger migreringsstrategier til at løse optimeringsproblemer, der knyttes til TSP.
• Multi-objektiv evolutionær algoritme er designet til multi-objektiv TSP og bygger på NSGA-II.
• Multiagentsystem Tilgangen løser TSP for N byer med faste beregningsressourcer.
• Lin-Kernighan heuristisk og dens efterfølger LKH levere ture inden for 2-3% af det optimale for tilfælde med millioner af byer.
• Concord bruger skæreplaner og forgrening-og-snit til at beregne nøjagtige optima for benchmark-instanser med titusindvis af byer.

Anvendelse af rejsende sælgerproblem

Problemet med den rejsende sælger optræder i den virkelige verden i både ren og modificeret form. Nogle af de vigtigste anvendelser er:

• Planlægning, logistik og mikrochipproduktion: Problemer med chipindsættelse i mikrochipindustrien modelleres som TSP-varianter for at minimere robotarmens rejsetid.
• DNA-sekventering: En modificeret TSP bruges i DNA-sekventering, hvor byer repræsenterer DNA-fragmenter, og afstande repræsenterer lighed mellem fragmenter.
• Astronomi: Astronomer bruger TSP til at minimere den tid, der bruges på at dreje teleskoper mellem observationsmål.
• Optimal kontrol: TSP-formuleringer modellerer optimale kontrolproblemer, hvor flere begrænsninger skal overholdes, samtidig med at gennemløbsomkostningerne minimeres.
• Last-mile levering: Amazon, UPS og madleveringsapps løser dynamiske TSP-varianter for at sekvensere stop for chauffører.
• Plukning på lager: Robot- og menneskelige plukkere følger TSP-optimerede ruter, der forkorter rejsetiden inden for distributionscentre.

Kompleksitetsanalyse af TSP

• Tidskompleksitet: Held-Karps dynamiske programmeringsmetoder løser 2^N delmængder for hver startnode, hvilket giver N × 2^N delproblemer. Hvert delproblem tager lineær tid at kombinere. Hvis oprindelsesnoden er uspecificeret, kræves en ydre løkke over N noder. Den samlede tidskompleksitet er O(N² × 2^N).
• Rumkompleksitet: DP-tabellen gemmer C(S, i) for hver delmængde S af toppunktsmængden. Der er 2^N delmængder pr. node, så rumkompleksiteten er O(N × 2^N), som ofte skrives som O(2^N) når N behandles som fikseret.

Lær derefter om Sigte af Eratosthenes-algoritmen.

Ofte Stillede Spørgsmål