Handelsreiziger Probleem: Python, C++ Algoritme

Wat is het Travelling Salesman Problem (TSP)?

Het handelsreizigersprobleem (TSP) is een klassiek combinatorisch optimalisatieprobleem in de theoretische informatica. Gegeven een graaf van steden, vraagt ​​het TSP naar het kortste pad dat elk knooppunt precies één keer bezoekt en terugkeert naar de startstad.

De probleemstelling bevat een lijst met steden en de afstanden tussen elk paar steden.

Doel: Begin in de startstad, bezoek elke andere stad precies één keer en keer terug naar de startstad. Het doel is om de kortst mogelijke rondreisroute te vinden.

Voorbeeld van TSP

Bekijk de onderstaande grafiek, waarin 1, 2, 3 en 4 de steden voorstellen en het gewicht op elke rand de afstand tussen die steden weergeeft.

Het doel is om de kortst mogelijke route te vinden die begint in de vertrekstad, elke andere stad precies één keer bezoekt en weer terugkeert naar de vertrekstad.

Voor de bovenstaande grafiek is de optimale route 1-2-4-3-1De kosten voor de kortste rondreis bedragen 10 + 25 + 30 + 15 = 80.

Verschillende oplossingen voor het handelsreizigersprobleem

Het handelsreizigersprobleem wordt geclassificeerd als NP-moeilijk omdat er geen bekend algoritme is dat het exact in polynomiale tijd oplost. De complexiteit neemt exponentieel toe met het aantal steden.

Er zijn meerdere manieren om TSP aan te vallen. De meest voorkomende benaderingen zijn:

Brute-force-aanpak: De naïeve methode berekent alle mogelijke routes en vergelijkt ze. Het aantal routes in een graaf met n steden is n!waardoor het gebruik van brute force-methoden rekenkundig zeer kostbaar wordt voor alles wat verder gaat dan ongeveer tien steden.

Branch and Bound-methode: Het probleem wordt opgedeeld in deelproblemen, en de oplossingen van die deelproblemen worden gecombineerd tot een optimale oplossing. Effectief snoeien verwijdert gedeeltelijke routes die de huidige beste kosten niet kunnen overtreffen.

Deze handleiding demonstreert de dynamische programmeerbenaderingDit is de gememoiseerde versie van branch and bound en komt overeen met het Bellman-Held-Karp-algoritme.

Dynamisch programmeren: Dit is een exacte methode die de optimale oplossing zoekt door overlappingen te hergebruiken.ping subprobleemresultaten. Het is trager dan de bijna-optimale oplossing. hebzuchtige methodenmaar het levert altijd een globaal optimale route op.

De rekenkundige complexiteit van deze aanpak is O(N² × 2^N), waar we later in het artikel op ingaan.

Methode van de dichtstbijzijnde buur: Een heuristische, gulzige aanpak die altijd naar de dichtstbijzijnde nog niet bezochte stad springt. Deze methode is veel goedkoper dan dynamische programmering, maar garandeert geen optimale route. Daarom wordt deze gebruikt voor bijna-optimale oplossingen, waarbij snelheid belangrijker is dan een exact minimum.

Algoritme voor het handelsreizigersprobleem

We gebruiken de dynamische programmeerbenadering om het TSP op te lossen. Voordat we met het algoritme beginnen, laten we eerst een paar termen verduidelijken:

• Een grafiek G = (V, E) is een verzameling van hoekpunten en randen.
• V is de verzameling van hoekpunten.
• E is de verzameling randen.
• Hoekpunten zijn verbonden via randen.
• Dist(i, j) Geeft de niet-negatieve afstand tussen hoekpunten i en j aan.

Stel dat S een subset van steden is, getrokken uit {1, 2, 3, …, n}, waarbij i en j twee steden in die subset zijn. Dan cost(i, S, j) is de lengte van het kortste pad dat begint bij i, elke stad in S precies één keer bezoekt en eindigt bij j.

Bijvoorbeeld cost(1, {2, 3, 4}, 1) geeft het kortste pad aan waarbij:

• Startstad is 1
• Steden 2, 3 en 4 worden slechts één keer bezocht
• Het eindpunt is 1

De recursie in dynamische programmering is:

• Set cost(i, {}, i) = 0, wat betekent dat we bij i beginnen en eindigen zonder kosten.
• . |S| > 1, definiëren cost(i, S, 1) = ∞ besteld, i ≠ 1Omdat de werkelijke kosten van de tour nog niet bekend zijn.
• Beginnend bij stad 1, kies de volgende stad zodat cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] besteld, i ∈ S en i ≠ j.

Voor de bovenstaande grafiek is de adjacentiematrix als volgt:

Het algoritme werkt als volgt:

Stap 1) De reis begint in stad 1, bezoekt elke andere stad één keer en keert terug naar stad 1.

Stap 2) S is een subset van steden. Voor elke |S| > 1, initialiseer cost(i, S, 1) = ∞. Hier cost(i, S, j) Dit duidt een rondreis aan die begint bij i, de steden in S één keer bezoekt en j bereikt. We beginnen vanuit oneindigheid omdat de afstand op dit punt onbekend is. De waarden zijn dus:

cost(2, {3, 4}, 1) = ∞ Dit betekent dat we beginnen in stad 2, door steden 3 en 4 gaan en uiteindelijk in stad 1 aankomen, met onbekende kosten. Op dezelfde manier:

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

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

Stap 3) Bereken voor elke deelverzameling van S:

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

Dat is de route met de laagste kosten die begint bij i, de subset van steden één keer bezoekt en terugkeert naar j. Omdat de route begint bij stad 1, zijn de optimale kosten cost(1, {other cities}, 1).

De terugkerende cyclus stap voor stap uitwerken

Nu is S = {1, 2, 3, 4}. Er zijn vier elementen, dus het aantal deelverzamelingen is 2^4 = 16Die deelverzamelingen zijn:

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

Omdat de tour begint in stad 1, kunnen we elke subset die stad 1 bevat, negeren bij het berekenen van de tussenliggende kosten.

De berekening van het algoritme verloopt als volgt:

1) |S| = Φ:

• kosten(2, Φ, 1) = afstand(2, 1) = 10
• kosten(3, Φ, 1) = afstand(3, 1) = 15
• kosten(4, Φ, 1) = afstand(4, 1) = 20

2) |S| = 1:

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

3) |S| = 2:

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

4) |S| = 3:

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

De optimale oplossing is dus 1-2-4-3-1.

Pseudo-code

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)

Implementatie in C/C++

Hier volgt de implementatie in C++De onderstaande versie corrigeert een eerdere fout in de broncode. return Een bug die al na de allereerste permutatie terugkeerde in plaats van alle routes op te sommen.

#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

implementatie in Python

De Python de implementatie weerspiegelt de C++ versie. Het corrigeert de bron. from itertools, import komma typefout, de verkeerd geplaatste return binnen de binnenste lus, en de ongewenste inkeping op 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

Academische oplossingen voor TSP

Computerwetenschappers zijn al decennialang op zoek naar verbeterde polynomiale algoritmen voor het handelsreizigersprobleem. Tot nu toe blijft TSP een NP-moeilijk probleem.

Er zijn diverse gepubliceerde technieken die de praktische complexiteit voor specifieke families van TSP-instanties verminderen:

• Het klassieke symmetrische TSP wordt opgelost door de Nul-achtervoegselmethode.
• De Op biogeografie gebaseerd optimalisatiealgoritme maakt gebruik van migratiestrategieën om optimalisatieproblemen op te lossen die overeenkomen met het Traveling Salesperson Problem (TSP).
• De Multi-Objective Evolutionary Algorithm is ontworpen voor multi-objectieve TSP-problemen en bouwt voort op NSGA-II.
• De Multi-Agent Systeem Deze aanpak lost het TSP-probleem op voor N steden met vaste rekenkracht.
• De Lin-Kernighan-heuristiek en zijn opvolger LKH Lever tours aan met een nauwkeurigheid van 2-3% ten opzichte van het optimum, zelfs in miljoenen steden.
• Eendracht Het maakt gebruik van snijvlakken en de branch-and-cut-methode om exacte optima te berekenen voor benchmark-instances met tienduizenden steden.

Toepassing van het handelsreizigersprobleem

Het handelsreizigersprobleem komt in de praktijk voor in zowel pure als aangepaste vormen. Enkele belangrijke toepassingen zijn:

• Planning, logistiek en de productie van microchips: Chip-invoegproblemen in de microchipindustrie worden gemodelleerd als varianten van het Traveling Salesperson Problem (TSP) om de reistijd van de robotarm te minimaliseren.
• DNA sequentie: Bij DNA-sequencing wordt een aangepaste TSP-methode gebruikt, waarbij steden DNA-fragmenten vertegenwoordigen en afstanden de gelijkenis tussen fragmenten weergeven.
• Astronomie: Sterrenkundigen gebruiken TSP om de tijd die nodig is om telescopen tussen observatiedoelen te draaien te minimaliseren.
• Optimale besturing: TSP-formuleringen modelleren optimale besturingsproblemen waarbij aan meerdere beperkingen moet worden voldaan terwijl de doorloopkosten worden geminimaliseerd.
• Last mile levering: AmazonUPS en apps voor maaltijdbezorging lossen dynamische TSP-varianten op om de stops voor chauffeurs in de juiste volgorde te plannen.
• Magazijnpicking: Zowel robotische als menselijke orderverzamelaars volgen TSP-geoptimaliseerde routes die de reistijd binnen distributiecentra verkorten.

Complexiteitsanalyse van TSP

• Tijdscomplexiteit: De dynamische programmeerbenadering van Held-Karp lost 2 op.^N deelverzamelingen voor elk startknooppunt, wat resulteert in N × 2^N deelproblemen. Het combineren van elk deelprobleem kost lineaire tijd. Als het beginknooppunt niet is gespecificeerd, is een buitenste lus over N knooppunten vereist. De totale tijdscomplexiteit is O(N² × 2^N).
• Ruimtecomplexiteit: De DP-tabel slaat gegevens op C(S, i) voor elke deelverzameling S van de verzameling hoekpunten. Er zijn 2^N subsets per knooppunt, dus de ruimtecomplexiteit is O(N × 2^N), wat vaak wordt geschreven als O(2^N) wanneer N als vast wordt beschouwd.

Leer vervolgens over de Zeef van Eratosthenes-algoritme.

Veelgestelde vragen