algorithm
Vendedor ambulante

Observaciones

Algoritmo de fuerza bruta

Una ruta a través de cada vértice exactamente una vez es lo mismo que ordenar el vértice de alguna manera. Por lo tanto, para calcular el costo mínimo de viajar a través de cada vértice exactamente una vez, ¡podemos aplicar fuerza bruta a cada uno de los N! Permutaciones de los números del 1 al 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

Complejidad del tiempo

Hay N! Las permutaciones a recorrer y el costo de cada ruta se calculan en O(N) , por lo tanto, este algoritmo toma tiempo O(N * N!) para dar la respuesta exacta.

Algoritmo de programación dinámico

Observe que si consideramos el camino (en orden):

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

y el camino

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

El costo de ir del vértice 1 al vértice 2 al vértice 3 sigue siendo el mismo, entonces ¿por qué debe recalcularse? Este resultado se puede guardar para su uso posterior.

Sea dp[bitmask][vertex] el costo mínimo de viajar a través de todos los vértices cuyo bit correspondiente en la bitmask de bitmask se establece en 1 termina en el vertex . Por ejemplo:

dp[12][2] 

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

Dado que 12 representa 1100 en binario, dp[12][2] representa ir a través de los vértices 2 y 3 en la gráfica con la ruta que termina en el vértice 2.

Así podemos tener el siguiente algoritmo (implementación de 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)

Esta línea puede ser un poco confusa, así que avancemos lentamente:

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

Aquí, la bitmask | (1 << i) establece el bit i de la bitmask de bitmask en 1, lo que representa que se ha visitado el vértice ith. La i después de la coma representa la nueva pos en esa llamada de función, que representa el nuevo "último" vértice. cost[pos][i] es sumar el costo de viajar del vértice pos al vértice i .

Por lo tanto, esta línea es para actualizar el valor del cost al valor mínimo posible de viajar a cualquier otro vértice que aún no se haya visitado.

Complejidad del tiempo

La función TSP(bitmask,pos) tiene valores de 2^N para la bitmask de bitmask y valores de N para pos . Cada función tarda O(N) en ejecutarse (el bucle for ). Por lo tanto, esta implementación toma tiempo O(N^2 * 2^N) para dar la respuesta exacta.