algorithm
Commesso viaggiatore

Osservazioni

Algoritmo della forza bruta

Un percorso attraverso ogni vertice esattamente una volta equivale a ordinare il vertice in qualche modo. Quindi, per calcolare il costo minimo di attraversare ogni vertice esattamente una volta, possiamo potenziare la forza ogni singolo N! permutazioni dei numeri da 1 a N

psuedocodarlo

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

Complessità del tempo

Ci sono N! permutazioni da passare e il costo di ciascun percorso è calcolato in O(N) , quindi questo algoritmo impiega O(N * N!) per produrre la risposta esatta.

Algoritmo di programmazione dinamica

Si noti che se consideriamo il percorso (in ordine):

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

e il percorso

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

Il costo di andare dal vertice 1 al vertice 2 al vertice 3 rimane lo stesso, quindi perché deve essere ricalcolato? Questo risultato può essere salvato per un uso successivo.

Lascia che dp[bitmask][vertex] rappresenti il ​​costo minimo di viaggiare attraverso tutti i vertici il cui bit corrispondente in bitmask di bitmask è impostato su 1 termina al vertex . Per esempio:

dp[12][2] 

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

Poiché 12 rappresenta 1100 in binario, dp[12][2] rappresenta attraversando i vertici 2 e 3 nel grafico con il percorso che termina al vertice 2.

Quindi possiamo avere il seguente algoritmo (implementazione 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)

Questa linea potrebbe essere un po 'confusa, quindi lasciala scorrere lentamente:

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

Qui, bitmask | (1 << i) imposta il bit di bitmask di bitmask di bitmask su 1, che rappresenta che il vertice di ith è stato visitato. L' i dopo la virgola rappresenta la nuova pos in quella chiamata di funzione, che rappresenta il nuovo vertice "ultimo". cost[pos][i] è quello di aggiungere il costo del viaggio dal vertice pos al vertice i .

Quindi, questa linea è di aggiornare il valore del cost al valore minimo possibile di viaggiare in ogni altro vertice che non è stato ancora visitato.

Complessità del tempo

La funzione TSP(bitmask,pos) ha 2^N valori per la bitmask di bitmask e N valori per pos . Ogni funzione richiede O(N) tempo per l'esecuzione (il ciclo for ). Quindi questa implementazione impiega O(N^2 * 2^N) per produrre la risposta esatta.