Utazó értékesítő probléma: Python, C++ Algoritmus

Mi az utazó értékesítő probléma (TSP)?

Az Utazó Ügynök Probléma (TSP) egy klasszikus kombinatorikus optimalizálási probléma az elméleti számítástechnikában. Adott egy városgráf, ahol a TSP a legrövidebb utat kéri, amely minden csomópontot pontosan egyszer érint, és visszatér a kiindulási városba.

A problémafelvetés tartalmazza a városok listáját, valamint az egyes várospárok közötti távolságokat.

Célkitűzés: Kezdd a kiindulási várossal, látogass meg minden más várost pontosan egyszer, majd térj vissza a kiindulási városba. A cél a lehető legrövidebb oda-vissza útvonal megtalálása.

Példa a TSP-re

Tekintsük az alábbi grafikont, ahol az 1, 2, 3 és 4 a városokat jelöli, és az egyes élek súlya a városok közötti távolságot jelöli.

A cél a lehető legrövidebb útvonal megtalálása, amely a kiindulási városból indul, minden más várost pontosan egyszer érint, és visszatér a kiindulási városba.

A fenti grafikon esetében az optimális útvonal a következő: 1-2-4-3-1A legrövidebb túra költsége 10 + 25 + 30 + 15 = 80.

Különböző megoldások utazó értékesítői problémára

Az utazó ügynök problémáját NP-nehéznek minősítik, mivel egyetlen ismert polinomiális idejű algoritmus sem oldja meg pontosan. A komplexitás exponenciálisan nő a városok számával.

Többféleképpen lehet támadni a TSP-t. A leggyakoribb megközelítések a következők:

Nyers erő megközelítés: A naiv módszer kiszámítja az összes lehetséges túrát és összehasonlítja azokat. Egy n városból álló gráfban a túrák száma: n!, ami a nyers erő számítási szempontból nagyon költségessé teszi a körülbelül tíz városon túli területek esetében.

Elágazás és kötött módszer: A problémát részproblémákra bontják, és ezen részproblémák megoldásait kombinálják egy optimális megoldássá. A hatékony metszés elveti azokat a részleges túrákat, amelyek nem tudják felülmúlni a jelenlegi legjobb költséget.

Ez az oktatóanyag bemutatja a dinamikus programozási megközelítés, amely a branch és a bound memoizált változata, és megfelel a Bellman-Held-Karp algoritmusnak.

Dinamikus programozás: Ez egy egzakt módszer, amely az átfedés újrafelhasználásával keresi az optimális megoldást.ping részprobléma eredményei. Lassabb, mint a közel optimális mohó módszerek, de mindig egy globálisan optimális túrát ad vissza.

Ennek a megközelítésnek a számítási összetettsége az O(N² × 2^N), amiről a cikk későbbi részében lesz szó.

Legközelebbi szomszéd módszer: Egy heurisztikus mohó megközelítés, amely mindig a legközelebbi még nem látogatott városra ugrik. Sokkal olcsóbb, mint a dinamikus programozás, de nem garantál optimális túrát, ezért közel optimális megoldásokhoz használják, amikor a sebesség fontosabb, mint a pontos minimumok.

Algoritmus utazó értékesítő problémához

A TSP megoldásához dinamikus programozási megközelítést alkalmazunk. Az algoritmus megkezdése előtt tisztázzunk néhány terminológiát:

• Egy grafikon G = (V, E) csúcsok és élek halmaza.
• V a csúcsok halmaza.
• E az élek halmaza.
• A csúcsok éleken keresztül kapcsolódnak össze.
• Dist(i, j) az i és j csúcsok közötti nemnegatív távolságot jelöli.

Tegyük fel, hogy S az {1, 2, 3, …, n} halmazból vett városok egy részhalmaza, ahol i és j két város ebben a részhalmazban. Ekkor cost(i, S, j) az i-ben kezdődő, S minden városát pontosan egyszer eléri, és j-ben ér véget.

Például, cost(1, {2, 3, 4}, 1) a legrövidebb utat jelöli, ahol:

• A kezdő város az 1
• A 2., 3. és 4. várost csak egyszer látogatják meg
• A végpont az 1

A dinamikus programozás rekurziója a következő:

• Készlet cost(i, {}, i) = 0, ami azt jelenti, hogy az i-edik ponton kezdünk és végzünk nulla költséggel.
• Amikor |S| > 1, határozza meg cost(i, S, 1) = ∞ mert i ≠ 1mivel a túra pontos költsége még nem ismert.
• Az 1. várostól kezdve válasszuk ki a következő várost úgy, hogy cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] mert i ∈ S és a i ≠ j.

A fenti grafikonon a szomszédsági mátrix a következő:

Így működik az algoritmus:

Step 1) Az utazás az 1-es városból indul, minden más várost egyszer meglátogat, majd visszatér az 1-es városba.

Step 2) Az S a városok egy részhalmaza. Minden |S| > 1 esetén inicializáljuk cost(i, S, 1) = ∞. Itt cost(i, S, j) egy olyan túrát jelöl, amely i-ből indul, egyszer látogatja meg S városait, és eléri j-t. A végtelenből indulunk, mert a távolság ekkor még ismeretlen. Tehát az értékek:

cost(2, {3, 4}, 1) = ∞ azt jelenti, hogy a 2. városból indulunk, átmegyünk a 3. és 4. városon, és ismeretlen költséggel elérjük az 1. várost. Hasonlóképpen:

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

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

Step 3) S minden részhalmazára számítsd ki:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Ahol j ∈ S és a i ≠ j.

Ez az a minimális költségű túra, amely i-ben kezdődik, egyszer meglátogatja a városok részhalmazát, és visszatér j-be. Mivel a túra az 1-es városban kezdődik, az optimális költség: cost(1, {other cities}, 1).

Az ismétlődés kezelése lépésről lépésre

Most S = {1, 2, 3, 4}. Négy elem van, tehát a részhalmazok száma: 2^4 = 16Ezek a részhalmazok a következők:

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

Mivel a túra az 1-es városból indul, minden olyan részhalmazt elvethetünk, amely tartalmazza az 1-es várost, miközben kiszámítjuk a köztes költségeket.

A számítási algoritmus a következőképpen alakul:

1) |S| = Φ:

• költség(2, Φ, 1) = elosztás(2, 1) = 10
• költség(3, Φ, 1) = elosztás(3, 1) = 15
• költség(4, Φ, 1) = elosztás(4, 1) = 20

2) |S| = 1:

• költség(2, {3}, 1) = elosztás(2, 3) + költség(3, Φ, 1) = 35 + 15 = 50
• költség(2, {4}, 1) = elosztás(2, 4) + költség(4, Φ, 1) = 25 + 20 = 45
• költség(3, {2}, 1) = elosztás(3, 2) + költség(2, Φ, 1) = 35 + 10 = 45
• költség(3, {4}, 1) = elosztás(3, 4) + költség(4, Φ, 1) = 30 + 20 = 50
• költség(4, {2}, 1) = elosztás(4, 2) + költség(2, Φ, 1) = 25 + 10 = 35
• költség(4, {3}, 1) = elosztás(4, 3) + költség(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• költség(2, {3, 4}, 1) = min [ eltáv(2, 3) + költség(3, {4}, 1) = 35 + 50 = 85, eltáv(2, 4) + költség(4, {3}, 1) = 25 + 45 = 70 ] = 70
• költség(3, {2, 4}, 1) = min [ eltáv(3, 2) + költség(2, {4}, 1) = 35 + 45 = 80, eltáv(3, 4) + költség(4, {2}, 1) = 30 + 35 = 65 ] = 65
• költség(4, {2, 3}, 1) = min [ eltáv(4, 2) + költség(2, {3}, 1) = 25 + 50 = 75, eltáv(4, 3) + költség(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

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

Tehát az optimális megoldás 1-2-4-3-1.

Pszeudo-kód

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)

Megvalósítás C/C++

Itt látható a megvalósítás C++Az alábbi verzió kijavítja a forrás korai hibáit. return hiba, amely az első permutáció után visszatért ahelyett, hogy az összes túrát felsorolta volna.

#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

Végrehajtás Python

Az Python a megvalósítás tükrözi a C++ verzió. Kijavítja a forrás from itertools, import vessző elírása, a rosszul elhelyezett return a belső hurokban belül, és a kóbor behúzás a 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

Akadémiai megoldások a TSP-hez

A számítógéptudósok évtizedek óta keresik a továbbfejlesztett polinom idejű algoritmusokat az utazó ügynök problémájára. A TSP eddig NP-nehéz maradt.

Számos publikált technika csökkenti a gyakorlati bonyolultságot a TSP-példányok specifikus családjai esetében:

• A klasszikus szimmetrikus TSP-t a következő oldja meg: Nulla utótag módszer.
• Az Biogeográfia-alapú optimalizáló algoritmus migrációs stratégiákat használ a TSP-hez kapcsolódó optimalizálási problémák megoldására.
• Az Többcélú evolúciós algoritmus többcélú TSP-hez készült, és az NSGA-II-re épül.
• Az Többügynökös rendszer A megközelítés N városra oldja meg a TSP-t fix számítási erőforrásokkal.
• Az Lin-Kernighan heurisztika és utódja LKH több millió várost érintő esetek esetén az optimálishoz képest 2-3%-on belüli túrákat kínáljon.
• Egyetértés vágósíkokat és elágazás-vágást használ a több tízezer várost tartalmazó benchmark példányok pontos optimumának kiszámításához.

Utazó kereskedő probléma alkalmazása

Az utazó ügynök problémája a való világban mind tiszta, mind módosított formában megjelenik. Néhány főbb alkalmazási lehetőség:

• Tervezés, logisztika és mikrochip gyártás: A mikrochipiparban a chipbehelyezési problémákat TSP-variánsokként modellezik, hogy minimalizálják a robotkar mozgási idejét.
• DNS-szekvenálás: A DNS-szekvenálás során módosított TSP-t használnak, ahol a városok a DNS-fragmentumokat, a távolságok pedig a fragmensek közötti hasonlóságot jelölik.
• Csillagászat: A csillagászok a TSP-t használják a távcsövek megfigyelési célpontok közötti forgatásával töltött idő minimalizálására.
• Optimális szabályozás: A TSP-formulációk olyan optimális szabályozási problémákat modelleznek, ahol több feltételt kell figyelembe venni, miközben minimalizálják a bejárási költségeket.
• Utolsó mérföldes szállítás: AmazonAz UPS és az ételkiszállítási alkalmazások dinamikus TSP-variációkat oldanak meg, hogy a sofőrök számára megállásokat szervezzenek.
• Raktári komissiózás: A robotizált és emberi komissiózók TSP által optimalizált útvonalakat követnek, amelyek lerövidítik az utazási időt az elosztóközpontokon belül.

A TSP komplexitáselemzése

• Idő összetettsége: A Held-Karp dinamikus programozási megközelítés 2-t old meg^N részhalmazok minden kezdő csomóponthoz, megadva N × 2^N részproblémák. Minden részprobléma kombinálása lineáris időt vesz igénybe. Ha az eredetcsomópont nincs meghatározva, akkor egy N csomóponton átívelő külső ciklusra van szükség. A teljes időbonyolultság: O(N² × 2^N).
• Tér összetettsége: A DP tábla tárolja C(S, i) a csúcshalmaz minden S részhalmazára. 2 van^N részhalmazok csomópontonként, tehát a térbeli komplexitás: O(N × 2^N), amelyet gyakran így írnak O(2^N) amikor N-t fixnek tekintjük.

Ezután ismerkedjen meg a Eratosthenes algoritmus szitája.

GYIK