Problém obchodního cestujícího: Python, C++ Algoritmus

Co je problém cestujícího prodejce (TSP)?

Problém obchodního cestujícího (TSP) je klasický kombinatorický optimalizační problém v teoretické informatice. Pro daný graf měst se TSP ptá na nejkratší cestu, která navštíví každý uzel právě jednou a vrátí se do původního města.

Vyjádření problému poskytuje seznam měst spolu se vzdálenostmi mezi jednotlivými dvojicemi měst.

Cíl: Začněte v původním městě, navštivte každé další město právě jednou a vraťte se do výchozího města. Cílem je najít nejkratší možnou trasu tam i zpět.

Příklad TSP

Vezměte si graf níže, kde 1, 2, 3 a 4 představují města a váha na každé hraně představuje vzdálenost mezi těmito městy.

Cílem je najít nejkratší možnou trasu, která začíná v původním městě, navštíví všechna ostatní města právě jednou a vrátí se do původního města.

Pro výše uvedený graf je optimální trasa 1-2-4-3-1Nejkratší cena zájezdu je 10 + 25 + 30 + 15 = 80.

Různá řešení problému cestujícího prodejce

Problém obchodního cestujícího je klasifikován jako NP-těžký, protože žádný známý polynomiální algoritmus jej přesně neřeší. Složitost roste exponenciálně s počtem měst.

Existuje několik způsobů, jak zaútočit na TSP. Nejběžnější přístupy jsou:

Přístup hrubé síly: Naivní metoda vypočítá všechny možné zájezdy a porovná je. Počet zájezdů v grafu s n městy je n!, což činí hrubou sílu výpočetně velmi nákladnou pro cokoli nad rámec zhruba deseti měst.

Metoda větvení a hranic: Problém je rozdělen na dílčí problémy a řešení těchto dílčích problémů se sloučí do optimálního řešení. Efektivní prořezávání vyřazuje dílčí trasy, které nemohou překonat aktuální nejlepší cenu.

Tento tutoriál ukazuje, přístup dynamického programování, což je memoizovaná verze metody větvení a hranic a odpovídá algoritmu Bellman-Held-Karp.

Dynamické programování: Jedná se o přesnou metodu, která hledá optimální řešení opakovaným využitím překrytí.ping výsledky dílčích problémů. Je pomalejší než téměř optimální zištné metody, ale vždy vrací globálně optimální trasu.

Výpočetní náročnost tohoto přístupu je O(N² × 2^N), o čemž si povíme dále v článku.

Metoda nejbližšího souseda: Heuristický chamtivý přístup, který vždy skočí na nejbližší nenavštívené město. Je mnohem levnější než dynamické programování, ale nezaručuje optimální prohlídku, takže se používá pro téměř optimální řešení, když je rychlost důležitější než přesná minima.

Algoritmus pro problém cestujícího prodejce

K řešení TSP používáme přístup dynamického programování. Než algoritmus spustíme, ujasněme si několik terminologie:

• Graf G = (V, E) je množina vrcholů a hran.
• V je množina vrcholů.
• E je množina hran.
• Vrcholy jsou spojeny přes hrany.
• Dist(i, j) označuje nezápornou vzdálenost mezi vrcholy i a j.

Předpokládejme, že S je podmnožina měst vybraná z {1, 2, 3, …, n}, kde i a j jsou dvě města v této podmnožině. Pak cost(i, S, j) je délka nejkratší cesty, která začíná v bodě i, navštíví každé město v S právě jednou a končí v bodě j.

Například, cost(1, {2, 3, 4}, 1) označuje nejkratší cestu, kde:

• Počáteční město je 1
• Města 2, 3 a 4 jsou navštívena pouze jednou
• Koncový bod je 1

Rekurence dynamického programování je:

• sada cost(i, {}, i) = 0, což znamená, že začínáme a končíme v i s nulovými náklady.
• Kdy |S| > 1, definovat cost(i, S, 1) = ∞ for i ≠ 1, protože skutečná cena zájezdu zatím není známa.
• Počínaje městem 1 vyberte další město tak, aby cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] for i ∈ S a i ≠ j.

Pro výše uvedený graf je matice sousednosti následující:

Zde je postup algoritmu:

Krok 1) Cesta začíná ve městě 1, jednou navštíví každé další město a vrací se do města 1.

Krok 2) S je podmnožinou měst. Pro každé |S| > 1 inicializujte cost(i, S, 1) = ∞. Tady cost(i, S, j) označuje cestu, která začíná v bodě i, jednou navštíví města v S a dosáhne bodu j. Začínáme od nekonečna, protože vzdálenost je v tomto bodě neznámá. Hodnoty jsou tedy:

cost(2, {3, 4}, 1) = ∞ znamená, že začneme ve městě 2, projdeme městy 3 a 4 a dosáhneme města 1, s neznámou cenou. Podobně:

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

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

Krok 3) Pro každou podmnožinu S vypočítejte:

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

To je zájezd s minimálními náklady, který začíná v i, jednou navštíví podmnožinu měst a vrátí se do j. Protože zájezd začíná ve městě 1, optimální náklady jsou cost(1, {other cities}, 1).

Práce s rekurzí krok za krokem

Nyní S = {1, 2, 3, 4}. Existují čtyři prvky, takže počet podmnožin je 2^4 = 16Tyto podmnožiny jsou:

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

Protože prohlídka začíná ve městě 1, můžeme při výpočtu mezinákladů zahodit každou podmnožinu, která obsahuje město 1.

Výpočet algoritmu se odvíjí následovně:

1) |S| = Φ:

• cena(2, Φ, 1) = vzdálenost(2, 1) = 10
• cena(3, Φ, 1) = vzdálenost(3, 1) = 15
• cena(4, Φ, 1) = vzdálenost(4, 1) = 20

2) |S| = 1:

• cena(2, {3}, 1) = vzdálenost(2, 3) + cena(3, Φ, 1) = 35 + 15 = 50
• cena(2, {4}, 1) = vzdálenost(2, 4) + cena(4, Φ, 1) = 25 + 20 = 45
• cena(3, {2}, 1) = vzdálenost(3, 2) + cena(2, Φ, 1) = 35 + 10 = 45
• cena(3, {4}, 1) = vzdálenost(3, 4) + cena(4, Φ, 1) = 30 + 20 = 50
• cena(4, {2}, 1) = vzdálenost(4, 2) + cena(2, Φ, 1) = 25 + 10 = 35
• cena(4, {3}, 1) = vzdálenost(4, 3) + cena(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

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

4) |S| = 3:

• cena(1, {2, 3, 4}, 1) = min [ vzdálenost(1, 2) + cena(2, {3, 4}, 1) = 10 + 70 = 80, vzdálenost(1, 3) + cena(3, {2, 4}, 1) = 15 + 65 = 80, vzdálenost(1, 4) + cena(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Optimální řešení je tedy 1-2-4-3-1.

Pseudo 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)

Implementace v C/C++

Zde je implementace v C++Níže uvedená verze opravuje dřívější chybu zdrojového kódu. return chyba, která se vracela hned po první permutaci místo výčtu všech prohlídek.

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

Výstup:

80

provádění Python

Jedno Python implementace odráží C++ verze. Opravuje zdrojovou from itertools, import překlep čárky, špatně umístěná čárka return uvnitř vnitřní smyčky a volně stojící odsazení na 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))

Výstup:

80

Akademická řešení TSP

Počítačoví vědci strávili desetiletí hledáním vylepšených polynomiálních algoritmů pro problém obchodního cestujícího. TSP zatím zůstává NP-těžký.

Několik publikovaných technik snižuje praktickou složitost specifických rodin instancí TSP:

• Klasická symetrická TSP je řešena pomocí Metoda nulové přípony.
• Jedno Optimalizační algoritmus založený na biogeografii používá migrační strategie k řešení optimalizačních problémů, které se mapují na TSP.
• Jedno Vícekriteriální evoluční algoritmus je navržen pro vícekriteriální TSP a staví na NSGA-II.
• Jedno Multiagentní systém přístup řeší TSP pro N měst s pevnými výpočetními zdroji.
• Jedno Lin-Kernighanova heuristika a jeho nástupce LKH zajistit zájezdy s odchylkou 2–3 % od optima pro případy s miliony měst.
• Svornost používá řezné roviny a metodu větvení a řezání k výpočtu přesných optim pro srovnávací instance s desítkami tisíc měst.

Aplikace problému obchodního cestujícího

Problém obchodního cestujícího se v reálném světě objevuje v čisté i modifikované formě. Mezi jeho hlavní aplikace patří:

• Plánování, logistika a výroba mikročipů: Problémy s vkládáním čipů v průmyslu mikročipů jsou modelovány jako varianty TSP, aby se minimalizovala doba pohybu robotického ramene.
• Sekvenování DNA: Modifikovaný TSP se používá v sekvenování DNA, kde města představují fragmenty DNA a vzdálenosti představují podobnost mezi fragmenty.
• Astronomie: Astronomové používají TSP k minimalizaci času stráveného otáčením dalekohledů mezi pozorovacími cíli.
• Optimální řízení: Formulace TSP modelují problémy optimálního řízení, kde musí být respektováno více omezení a zároveň minimalizovány náklady na průchod.
• Dodání na poslední míli: AmazonAplikace , UPS a rozvoz jídla řeší dynamické varianty TSP pro seřazení zastávek pro řidiče.
• Vychystávání ve skladu: Robotické i lidské sběračské jednotky se řídí trasami optimalizovanými pro TSP, které zkracují dobu cestování v distribučních centrech.

Analýza složitosti TSP

• Časová složitost: Dynamický programovací přístup Held-Karp řeší 2^N podmnožiny pro každý počáteční uzel, což dává N × 2^N dílčích problémů. Kombinace každého dílčího problému trvá lineární čas. Pokud není určen počáteční uzel, je vyžadována vnější smyčka přes N uzlů. Celková časová složitost je O(N² × 2^N).
• Prostorová složitost: Tabulka DP ukládá C(S, i) pro každou podmnožinu S vrcholové množiny. Existují 2^N podmnožin na uzel, takže prostorová složitost je O(N × 2^N), což se často píše jako O(2^N) když je N považováno za fixní.

Dále se dozvíte o Síto Eratosthenova algoritmu.

Nejčastější dotazy