Problem trgovačkog putnika: Python, C++ Algoritam

Što je problem trgovačkog putnika (TSP)?

Problem trgovačkog putnika (TSP) je klasični kombinatorni optimizacijski problem u teorijskom računarstvu. Za graf gradova, TSP traži najkraći put koji posjećuje svaki čvor točno jednom i vraća se u početni grad.

U opisu problema navodi se popis gradova zajedno s udaljenostima između svakog para gradova.

Cilj: Krenite u početnom gradu, posjetite svaki drugi grad točno jednom i vratite se u početni grad. Cilj je pronaći najkraću moguću rutu za oba smjera.

Primjer TSP-a

Razmotrite graf ispod gdje 1, 2, 3 i 4 predstavljaju gradove, a težina na svakom bridu predstavlja udaljenost između tih gradova.

Cilj je pronaći najkraću moguću turu koja počinje iz grada polazišta, posjećuje svaki drugi grad točno jednom i vraća se u grad polazišta.

Za gornji graf, optimalna ruta je 1-2-4-3-1Najkraća cijena ture je 10 + 25 + 30 + 15 = 80.

Različita rješenja problema trgovačkog putnika

Problem trgovačkog putnika klasificiran je kao NP-težak jer ga nijedan poznati algoritam s polinomnim vremenom ne rješava točno. Složenost raste eksponencijalno s brojem gradova.

Postoji više načina za napad na TSP. Najčešći pristupi su:

Pristup grube sile: Naivna metoda izračunava svaku moguću turu i uspoređuje ih. Broj tura u grafu s n gradova je n!, što brutalnu silu čini računalno vrlo skupom za sve izvan desetak gradova.

Metoda grananja i ograđivanja: Problem se dijeli na podprobleme, a rješenja tih podproblema kombiniraju se u optimalno rješenje. Učinkovito obrezivanje odbacuje djelomične ture koje ne mogu nadmašiti trenutno najbolju cijenu.

Ovaj tutorijal pokazuje pristup dinamičkog programiranja, što je memoizirana verzija metode grananja i ograničavanja i odgovara Bellman-Held-Karp algoritmu.

Dinamičko programiranje: Ovo je egzaktna metoda koja traži optimalno rješenje ponovnim korištenjem preklapanjaping rezultati podproblema. Sporiji je od gotovo optimalnog pohlepne metode, ali uvijek vraća globalno optimalnu turu.

Računalna složenost ovog pristupa je O(N² × 2^N), o čemu ćemo kasnije raspravljati u članku.

Metoda najbližeg susjeda: Heuristički pohlepni pristup koji uvijek skače na najbliži neposjećeni grad. Mnogo je jeftiniji od dinamičkog programiranja, ali ne jamči optimalnu turu, pa se koristi za gotovo optimalna rješenja kada je brzina važnija od točnih minimuma.

Algoritam za problem trgovačkog putnika

Za rješavanje TSP-a koristimo pristup dinamičkog programiranja. Prije pokretanja algoritma, razjasnimo nekoliko termina:

• Graf G = (V, E) je skup vrhova i bridova.
• V je skup vrhova.
• E je skup rubova.
• Vrhovi su povezani bridovima.
• Dist(i, j) označava nenegativnu udaljenost između vrhova i i j.

Pretpostavimo da je S podskup gradova izvučenih iz {1, 2, 3, …, n} gdje su i i j dva grada u tom podskupu. Tada cost(i, S, j) je duljina najkraćeg puta koji počinje u i, posjećuje svaki grad u S točno jednom i završava u j.

Na primjer, cost(1, {2, 3, 4}, 1) označava najkraći put gdje je:

• Početni grad je 1
• Gradovi 2, 3 i 4 posjećuju se samo jednom
• Završna točka je 1

Rekurentnost dinamičkog programiranja je:

• Postaviti cost(i, {}, i) = 0, što znači da počinjemo i završavamo na i s nultim troškovima.
• Kada |S| > 1, definirati cost(i, S, 1) = ∞ za i ≠ 1, jer stvarna cijena putovanja još nije poznata.
• Počevši od grada 1, odaberite sljedeći grad tako da cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] za i ∈ S i i ≠ j.

Za gornji graf, matrica susjednosti je sljedeća:

Evo kako algoritam napreduje:

Korak 1) Putovanje počinje u gradu 1, posjećuje svaki drugi grad jednom i vraća se u grad 1.

Korak 2) S je podskup gradova. Za svaki |S| > 1, inicijalizirajte cost(i, S, 1) = ∞, Ovdje cost(i, S, j) označava turu koja počinje u i, jednom posjećuje gradove u S i dolazi do j. Počinjemo od beskonačnosti jer je udaljenost u ovoj točki nepoznata. Dakle, vrijednosti su:

cost(2, {3, 4}, 1) = ∞ znači da počinjemo u gradu 2, prolazimo kroz gradove 3 i 4 i dolazimo do grada 1, s nepoznatom cijenom. Slično:

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

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

Korak 3) Za svaki podskup od S, izračunajte:

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

To je tura s minimalnim troškom koja počinje u i, jednom posjećuje podskup gradova i vraća se u j. Budući da tura počinje u gradu 1, optimalni trošak je cost(1, {other cities}, 1).

Rad s ponavljanjem korak po korak

Sada je S = {1, 2, 3, 4}. Postoje četiri elementa, pa je broj podskupova jednak 2^4 = 16Ti podskupovi su:

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

Budući da tura počinje u gradu 1, možemo odbaciti svaki podskup koji sadrži grad 1 prilikom izračunavanja međutroškova.

Izračun algoritma odvija se na sljedeći način:

1) |S| = Φ:

• trošak(2, Φ, 1) = udaljenost(2, 1) = 10
• trošak(3, Φ, 1) = udaljenost(3, 1) = 15
• trošak(4, Φ, 1) = udaljenost(4, 1) = 20

2) |S| = 1:

• trošak(2, {3}, 1) = udaljenost(2, 3) + trošak(3, Φ, 1) = 35 + 15 = 50
• trošak(2, {4}, 1) = udaljenost(2, 4) + trošak(4, Φ, 1) = 25 + 20 = 45
• trošak(3, {2}, 1) = udaljenost(3, 2) + trošak(2, Φ, 1) = 35 + 10 = 45
• trošak(3, {4}, 1) = udaljenost(3, 4) + trošak(4, Φ, 1) = 30 + 20 = 50
• trošak(4, {2}, 1) = udaljenost(4, 2) + trošak(2, Φ, 1) = 25 + 10 = 35
• trošak(4, {3}, 1) = udaljenost(4, 3) + trošak(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

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

4) |S| = 3:

• trošak(1, {2, 3, 4}, 1) = min [ udaljenost(1, 2) + trošak(2, {3, 4}, 1) = 10 + 70 = 80, udaljenost(1, 3) + trošak(3, {2, 4}, 1) = 15 + 65 = 80, udaljenost(1, 4) + trošak(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Dakle, optimalno rješenje je 1-2-4-3-1.

Pseudo-kod

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)

Implementacija u C/C++

Evo implementacije u C++Verzija u nastavku ispravlja ranu grešku izvora. return greška koja se vraćala nakon prve permutacije umjesto nabrajanja svih tura.

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

Izlaz:

80

Implementacija u Python

The Python implementacija odražava C++ verzija. Ispravlja izvornu from itertools, import pogreška u pisanju zareza, pogrešno postavljen return unutar unutarnje petlje i zalutalog uvlačenja 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))

Izlaz:

80

Akademska rješenja za TSP

Računalni znanstvenici desetljećima su tragali za poboljšanim algoritmima s polinomnim vremenom za problem trgovačkog putnika. Zasad je TSP ostao NP-težak.

Nekoliko objavljenih tehnika smanjuje praktičnu složenost za specifične obitelji TSP instanci:

• Klasični simetrični TSP rješava se pomoću Metoda nultog sufiksa.
• The Algoritam optimizacije temeljen na biogeografiji koristi strategije migracije za rješavanje optimizacijskih problema koji se mapiraju na TSP.
• The Višekriterijski evolucijski algoritam dizajniran je za višeciljni TSP i temelji se na NSGA-II.
• The Sustav s više agenata pristup rješava TSP za N gradova s ​​fiksnim računalnim resursima.
• The Lin-Kernighan heuristika i njegov nasljednik LKH isporučiti ture unutar 2-3% od optimalnog za slučajeve s milijunima gradova.
• sloga koristi ravnine rezanja i grananje i rezanje za izračunavanje točnih optimuma za referentne instance s desecima tisuća gradova.

Primjena problema trgovačkog putnika

Problem trgovačkog putnika pojavljuje se u stvarnom svijetu i u čistom i u modificiranom obliku. Neke od glavnih primjena su:

• Planiranje, logistika i proizvodnja mikročipova: Problemi s umetanjem čipova u industriji mikročipova modelirani su kao TSP varijante kako bi se smanjilo vrijeme kretanja robotske ruke.
• Sekvenciranje DNK: Modificirani TSP se koristi u sekvenciranju DNK gdje gradovi predstavljaju fragmente DNK, a udaljenosti predstavljaju sličnost između fragmenata.
• Astronomija: Astronomi koriste TSP kako bi smanjili vrijeme provedeno u okretanju teleskopa između promatračkih ciljeva.
• Optimalna kontrola: TSP formulacije modeliraju probleme optimalnog upravljanja gdje se moraju poštovati višestruka ograničenja uz minimiziranje troškova prelaska.
• Dostava zadnje milje: Amazon, UPS i aplikacije za dostavu hrane rješavaju dinamičke varijante TSP-a kako bi odredile zaustavljanja za vozače.
• Prikupljanje u skladištu: Robotski i ljudski berači slijede rute optimizirane od strane TSP-a koje skraćuju vrijeme putovanja unutar distribucijskih centara.

Analiza složenosti TSP-a

• Složenost vremena: Held-Karpov pristup dinamičkog programiranja rješava 2^N podskupovi za svaki početni čvor, dajući N × 2^N podproblemi. Za kombiniranje svakog podproblema potrebno je linearno vrijeme. Ako početni čvor nije određen, potrebna je vanjska petlja preko N čvorova. Ukupna vremenska složenost je O(N² × 2^N).
• Složenost prostora: DP tablica pohranjuje C(S, i) za svaki podskup S skupa vrhova. Postoje 2^N podskupova po čvoru, pa je složenost prostora O(N × 2^N), što se često piše kao O(2^N) kada se N tretira kao fiksan.

Zatim saznajte više o Algoritam Eratostenovog sita.

Pitanja i odgovori