algorithm
Podróżujący sprzedawca

Uwagi

Algorytm Brute Force

Ścieżka przez każdy wierzchołek dokładnie raz jest taka sama, jak uporządkowanie wierzchołka w jakiś sposób. Tak więc, aby dokładnie obliczyć minimalny koszt podróży przez każdy wierzchołek, możemy brutalnie użyć siły każdego z N! permutacje liczb od 1 do N

Psuedocode

minimum = INF
for all permutations P

    current = 0                                

    for i from 0 to N-2
        current = current + cost[P[i]][P[i+1]]  <- Add the cost of going from 1 vertex to the next
    
    current = current + cost[P[N-1]][P[0]]      <- Add the cost of going from last vertex to the first

    if current < minimum                        <- Update minimum if necessary
        minimum = current
    
output minimum

Złożoność czasu

Jest N! przejść przez permutacje, a koszt każdej ścieżki jest obliczany w O(N) , dlatego ten algorytm potrzebuje O(N * N!) czasu na podanie dokładnej odpowiedzi.

Algorytm programowania dynamicznego

Zauważ, że jeśli weźmiemy pod uwagę ścieżkę (w kolejności):

(1,2,3,4,6,0,5,7)

i ścieżka

(1,2,3,5,0,6,7,4) 

Koszt przejścia od wierzchołka 1 do wierzchołka 2 do wierzchołka 3 pozostaje taki sam, więc dlaczego trzeba go ponownie obliczyć? Ten wynik można zapisać do późniejszego wykorzystania.

Niech dp[bitmask][vertex] reprezentuje minimalny koszt podróży przez wszystkie wierzchołki, których odpowiadający bit w bitmask jest ustawiony na 1 kończący się na vertex . Na przykład:

dp[12][2] 

   12   =   1 1 0 0
            ^ ^ 
vertices:   3 2 1 0

Ponieważ 12 oznacza 1100 , dp[12][2] oznacza przechodzenie przez wierzchołki 2 i 3 na wykresie ze ścieżką kończącą się na wierzchołku 2.

Zatem możemy mieć następujący algorytm (implementacja C ++):

int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int TSP(int bitmask, int pos){
    int cost = INF;
    if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
        return cost[pos][0];             //Cost to go back
    }
    if (memo[bitmask][pos] != -1){       //If this has already been computed
        return memo[bitmask][pos];       //Just return the value, no need to recompute
    }
    for (int i = 0; i < N; ++i){         //For every vertex 
        if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
            cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
        } 
    }
    memo[bitmask][pos] = cost;           //Save the result
    return cost;
}
//Call TSP(1,0)

Ta linia może być trochę myląca, więc przejdźmy ją powoli:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

Tutaj, bitmask | (1 << i) ustawia i-ty bit bitmask na 1, co oznacza, że i-ty wierzchołek został odwiedzony. i po przecinku reprezentuje nowe pos w tym wywołania funkcji, która reprezentuje nową „ostatni” wierzchołek. cost[pos][i] to suma kosztu podróży z wierzchołka pos do wierzchołka i .

Zatem wiersz ten ma zaktualizować wartość cost do minimalnej możliwej wartości podróży do każdego innego wierzchołka, który nie był jeszcze odwiedzany.

Złożoność czasu

Funkcja TSP(bitmask,pos) ma 2^N wartości dla bitmask i N wartości dla pos . Każda funkcja potrzebuje czasu O(N) do uruchomienia (pętla for ). Tak więc implementacja zajmuje czas O(N^2 * 2^N) aby uzyskać dokładną odpowiedź.