algorithm
Resande säljare

Anmärkningar

Brute Force Algoritm

En väg genom varje toppunkt exakt en gång är densamma som att beställa toppunktet på något sätt. Således, för att beräkna minimikostnaderna för att resa genom varje toppunkt exakt en gång, kan vi brute tvinga varenda en av N! permutationer av siffrorna från 1 till 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

Tidskomplexitet

Det finns N! permutationer att gå igenom och kostnaden för varje sökväg beräknas i O(N) , alltså tar denna algoritm O(N * N!) tid att mata ut det exakta svaret.

Dynamisk programmeringsalgoritm

Lägg märke till att om vi överväger sökvägen (i ordning):

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

och vägen

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

Kostnaden för att gå från toppunkt 1 till toppunkt 2 till toppunkt 3 förblir desamma, så varför måste det beräknas om? Detta resultat kan sparas för senare användning.

Låt dp[bitmask][vertex] representera lägsta kostnaden för att resa genom alla vertikaler vars motsvarande bit i bitmask är inställd på 1 slutar vid vertex . Till exempel:

dp[12][2] 

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

Eftersom 12 representerar 1100 i binär, representerar dp[12][2] gå igenom hörn 2 och 3 i diagrammet med banan som slutar vid toppunkt 2.

Således kan vi ha följande algoritm (C ++ implementering):

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)

Den här linjen kan vara lite förvirrande, så låter gå långsamt igenom den:

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

Här, bitmask | (1 << i) sätter ith-biten av bitmask till 1, vilket representerar att ith-vertex har besökts. Den i efter kommatecknet representerar nya pos i den funktionsanrop, som representerar den nya "sista" vertex. cost[pos][i] är att lägga till kostnaden för reser från vertex pos genom punkt i .

Således är denna rad att uppdatera värdet på cost till det minsta möjliga värdet av att resa till varje annan toppunkt som ännu inte har besökts.

Tidskomplexitet

Funktionen TSP(bitmask,pos) har 2^N värden för bitmask och N värden för pos . Varje funktion tar O(N) tid att köra ( for loopen). Således tar denna implementering O(N^2 * 2^N) tid att mata ut det exakta svaret.