Travelling Salesman -ongelma: Python, C++ algoritmi

Mikä on Travelling Salesman -ongelma (TSP)?

Kauppakamerongelma (TSP) on klassinen kombinatorinen optimointiongelma teoreettisessa tietojenkäsittelytieteessä. Kun kaupunkien verkko on annettu, TSP kysyy lyhintä polkua, joka käy jokaisessa solmussa täsmälleen kerran ja palaa lähtökaupunkiin.

Ongelmankuvauksessa on luettelo kaupungeista sekä niiden välisistä etäisyyksistä.

Tavoite: Aloita lähtökaupungista, vieraile jokaisessa muussa kaupungissa tasan kerran ja palaa lähtökaupunkiin. Tavoitteena on löytää lyhin mahdollinen edestakainen reitti.

Esimerkki TSP:stä

Tarkastellaan alla olevaa kaaviota, jossa 1, 2, 3 ja 4 edustavat kaupunkeja ja jokaisen reunan paino edustaa etäisyyttä näiden kaupunkien välillä.

Tavoitteena on löytää lyhin mahdollinen matka, joka alkaa lähtökaupungista, käy jokaisessa muussa kaupungissa tasan kerran ja palaa lähtökaupunkiin.

Yllä olevassa kaaviossa optimaalinen reitti on 1-2-4-3-1Lyhimmän matkan hinta on 10 + 25 + 30 + 15 = 80.

Erilaisia ​​ratkaisuja matkustavan myyjän ongelmaan

Kauppamatkustajan ongelma luokitellaan NP-vaikeaksi, koska mikään tunnettu polynomiaikainen algoritmi ei ratkaise sitä tarkasti. Monimutkaisuus kasvaa eksponentiaalisesti kaupunkien määrän myötä.

TSP:tä voi hyökätä monella eri tavalla. Yleisimmät lähestymistavat ovat:

Raa'an voiman lähestymistapa: Naiivi menetelmä laskee kaikki mahdolliset kierrokset ja vertaa niitä. Kierrosten lukumäärä graafissa, jossa on n kaupunkia, on n!, mikä tekee raa'an voiman laskennallisesti erittäin kalliiksi yli kymmenen kaupungin osalta.

Haara- ja sidontamenetelmä: Ongelma jaetaan osaongelmiin, ja näiden osaongelmien ratkaisut yhdistetään optimaaliseksi ratkaisuksi. Tehokas karsinta hylkää osittaiset matkat, jotka eivät pysty parantamaan nykyistä parasta kustannustehokkuutta.

Tämä opetusohjelma havainnollistaa dynaaminen ohjelmointimenetelmä, joka on branch- ja bound-lausekkeiden ulkoa tallennettava versio ja vastaa Bellman-Held-Karp-algoritmia.

Dynaaminen ohjelmointi: Tämä on tarkka menetelmä, joka etsii optimaalista ratkaisua käyttämällä uudelleen päällekkäisyyttäping osaongelman tuloksia. Se on hitaampaa kuin lähes optimaalinen ahneita menetelmiä, mutta se palauttaa aina globaalisti optimaalisen kierroksen.

Tämän lähestymistavan laskennallinen monimutkaisuus on O(N² × 2^N), jota käsittelemme myöhemmin artikkelissa.

Lähimmän naapurin menetelmä: Heuristinen ahne lähestymistapa, joka hyppää aina lähimpään vierailemattomaan kaupunkiin. Se on paljon halvempi kuin dynaaminen ohjelmointi, mutta ei takaa optimaalista kierrosta, joten sitä käytetään lähes optimaalisiin ratkaisuihin, kun nopeus on tärkeämpää kuin tarkat minimit.

Algoritmi matkustavan myyjän ongelmalle

Käytämme dynaamista ohjelmointia TSP:n ratkaisemiseen. Ennen algoritmin aloittamista selvitetään muutamia terminologiaa:

• Kaavio G = (V, E) on joukko solmuja ja reunoja.
• V on joukko kärkipisteitä.
• E on reunojen joukko.
• Vertices yhdistetään reunojen kautta.
• Dist(i, j) tarkoittaa pisteiden i ja j välistä ei-negatiivista etäisyyttä.

Oletetaan, että S on joukko kaupunkeja, jotka on johdettu joukosta {1, 2, 3, …, n}, missä i ja j ovat kaksi kaupunkia tässä joukossa. Silloin cost(i, S, j) on lyhimmän reitin pituus, joka alkaa pisteestä i, käy jokaisessa S:n kaupungissa täsmälleen kerran ja päättyy pisteeseen j.

Esimerkiksi cost(1, {2, 3, 4}, 1) tarkoittaa lyhintä polkua, jossa:

• Aloituskaupunki on 1
• Kaupungeissa 2, 3 ja 4 käydään vain kerran
• Loppupiste on 1

Dynaamisen ohjelmoinnin rekursio on:

• Asettaa cost(i, {}, i) = 0, mikä tarkoittaa, että aloitamme ja lopetamme i:hen nollakustannuksella.
• Kun |S| > 1, määrittele cost(i, S, 1) = ∞ varten i ≠ 1koska matkan todellinen hinta ei ole vielä tiedossa.
• Aloita kaupungista 1 ja valitse seuraava kaupunki niin, että cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] varten i ∈ S ja i ≠ j.

Yllä olevassa kaaviossa vierekkäisyysmatriisi on seuraava:

Näin algoritmi etenee:

Vaihe 1) Matka alkaa kaupungista 1, vierailee kerran jokaisessa muussa kaupungissa ja palaa kaupunkiin 1.

Vaihe 2) S on kaupunkien osajoukko. Jokaisella |S| > 1, alusta cost(i, S, 1) = ∞. Tässä cost(i, S, j) tarkoittaa kiertomatkaa, joka alkaa pisteestä i, vierailee kerran S:n kaupungeissa ja saapuu pisteeseen j. Lähdemme liikkeelle äärettömyydestä, koska etäisyys on tässä pisteessä tuntematon. Joten arvot ovat:

cost(2, {3, 4}, 1) = ∞ tarkoittaa, että aloitamme kaupungista 2, kuljemme kaupunkien 3 ja 4 läpi ja saavutamme kaupungin 1, mutta kustannukset ovat tuntemattomat. Samoin:

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

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

Vaihe 3) Laske jokaiselle S:n osajoukolle:

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

Se on pienimmän kustannuksen omaava kiertomatka, joka alkaa kaupungista i, vierailee kerran joukon kaupunkeja sisältävässä joukossa ja palaa kaupunkiin j. Koska kiertomatka alkaa kaupungista 1, optimaalinen kustannus on cost(1, {other cities}, 1).

Toistumisen käsittely vaihe vaiheelta

Nyt S = {1, 2, 3, 4}. Alkioita on neljä, joten osajoukkojen lukumäärä on 2^4 = 16Nuo osajoukot ovat:

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

Koska kierros alkaa kaupungista 1, voimme hylätä kaikki kaupungin 1 sisältävät osajoukot laskiessamme välikustannuksia.

Algoritmin laskenta etenee seuraavasti:

1) |S| = Φ:

• kustannus(2, Φ, 1) = jakauma(2, 1) = 10
• kustannus(3, Φ, 1) = jakauma(3, 1) = 15
• kustannus(4, Φ, 1) = jakauma(4, 1) = 20

2) |S| = 1:

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

3) |S| = 2:

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

4) |S| = 3:

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

Joten optimaalinen ratkaisu on 1-2-4-3-1.

Pseudokoodi

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)

Toteutus C/C++

Tässä on toteutus C++Alla oleva versio korjaa lähteen varhaisen return bugi, joka palasi aivan ensimmäisen permutaation jälkeen kaikkien kierrosten luetteloinnin sijaan.

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

lähtö:

80

Toteutus sisään Python

Python toteutus heijastelee C++ versio. Se korjaa lähteen from itertools, import pilkku kirjoitusvirhe, väärin sijoitettu return sisemmän silmukan sisällä ja harhaileva sisennys päällä 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))

lähtö:

80

Akateemiset ratkaisut TSP:lle

Tietojenkäsittelytieteilijät ovat vuosikymmeniä etsineet parempia polynomiaikaisia ​​algoritmeja kauppamatkustajan ongelmaan. Toistaiseksi kauppamatkustajan ongelma on edelleen NP-vaikea.

Useat julkaistut tekniikat vähentävät käytännön monimutkaisuutta tietyille TSP-instanssiryhmille:

• Klassinen symmetrinen kokonaispistepotenssi ratkaistaan ​​seuraavasti: Nollaliitemenetelmä.
• Biogeografiaan perustuva optimointialgoritmi käyttää migraatiostrategioita TSP:hen liittyvien optimointiongelmien ratkaisemiseen.
• Monitavoitteinen evoluutioalgoritmi on suunniteltu monitavoitteista TSP:tä varten ja perustuu NSGA-II:een.
• Moniagenttijärjestelmä lähestymistapa ratkaisee TSP:n N kaupungille kiinteillä laskentaresursseilla.
• Lin-Kernighanin heuristiikka ja sen seuraaja LKH toimittaa matkoja, jotka ovat 2–3 prosentin sisällä optimaalisesta miljoonien kaupunkien tapauksissa.
• Concorde käyttää leikkaustasoja ja haarautumis-ja-leikkaus-menetelmää laskeakseen tarkat optimaaliset arvot kymmenien tuhansien kaupunkien vertailuinstansseille.

Travelling Salesman -ongelman soveltaminen

Kauppamatkustajan ongelma esiintyy tosielämässä sekä puhtaassa että muunnellussa muodossa. Joitakin tärkeimpiä sovelluksia ovat:

• Suunnittelu, logistiikka ja mikrosirujen valmistus: Mikrosiruteollisuudessa sirun asettamiseen liittyviä ongelmia mallinnetaan TSP-variantteina robottikäsivarren liike-ajan minimoimiseksi.
• DNA-sekvensointi: Modifioitua TSP:tä käytetään DNA-sekvensoinnissa, jossa kaupungit edustavat DNA-fragmentteja ja etäisyydet edustavat fragmenttien välistä samankaltaisuutta.
• Tähtitiede: Tähtitieteilijät käyttävät TSP:tä minimoidakseen teleskooppien siirtämiseen käytetyn ajan havaintokohteiden välillä.
• Optimaalinen hallinta: TSP-formulaatiot mallintavat optimaalisen hallinnan ongelmia, joissa on otettava huomioon useita rajoitteita samalla minimoiden läpikulkukustannukset.
• Viimeisen kilometrin toimitus: Amazon, UPS ja ruokalähettisovellukset ratkaisevat dynaamiset TSP-variantit kuljettajien pysähdysten järjestämiseksi.
• Varastokeräily: Robotti- ja ihmiskeräilijät seuraavat TSP:n optimoimia reittejä, jotka lyhentävät matka-aikaa jakelukeskuksissa.

TSP:n monimutkaisuusanalyysi

• Ajan monimutkaisuus: Held-Karpin dynaaminen ohjelmointimenetelmä ratkaisee 2^N osajoukot kullekin aloitussolmulle, jolloin saadaan N × 2^N aliongelmia. Jokaisen aliongelman yhdistäminen vie lineaarisen ajan. Jos lähtösolmua ei ole määritelty, tarvitaan ulompi silmukka N solmun yli. Kokonaisaikakompleksisuus on O(N² × 2^N).
• Avaruuden monimutkaisuus: DP-pöytä tallentaa C(S, i) jokaiselle solmujoukon osajoukolle S. On olemassa 2^N osajoukkoja solmua kohden, joten avaruuskompleksisuus on O(N × 2^N), joka usein kirjoitetaan muodossa O(2^N) kun N:ää käsitellään kiinteänä.

Seuraavaksi tutustu Eratosthenes-algoritmin seula.

UKK