algorithm
Vendeur ambulant

Remarques

Algorithme de force brutale

Un chemin à travers chaque sommet exactement une fois est identique à l'ordre du sommet d'une certaine manière. Ainsi, pour calculer le coût minimum de déplacement à travers chaque sommet exactement une fois, nous pouvons forcer chacun des N! permutations des nombres de 1 à 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

La complexité du temps

Il y a N! les permutations doivent se faire et le coût de chaque chemin est calculé dans O(N) , donc cet algorithme prend le temps O(N * N!) pour sortir la réponse exacte.

Algorithme de programmation dynamique

Notez que si nous considérons le chemin (dans l'ordre):

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

et le chemin

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

Le coût pour passer du sommet 1 au sommet 2 jusqu'au sommet 3 reste le même, alors pourquoi faut-il le recalculer? Ce résultat peut être enregistré pour une utilisation ultérieure.

Soit dp[bitmask][vertex] le coût minimum de déplacement à travers tous les sommets dont le bit correspondant dans bitmask est défini sur 1 terminant au vertex . Par exemple:

dp[12][2] 

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

Puisque 12 représente 1100 en binaire, dp[12][2] représente les sommets 2 et 3 du graphe avec le chemin se terminant au sommet 2.

On peut donc avoir l'algorithme suivant (implémentation 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)

Cette ligne peut être un peu déroutante, alors parcourons-la lentement:

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

Ici, bitmask | (1 << i) place le bit i du bitmask à 1, ce qui représente que le iième sommet a été visité. Le i après la virgule représente le nouveau pos dans cet appel de fonction, qui représente le nouveau "dernier" sommet. cost[pos][i] est d'ajouter les frais de déplacement du sommet pos Vertex i .

Ainsi, cette ligne consiste à mettre à jour la valeur du cost à la valeur minimale possible du déplacement vers tous les autres sommets non encore visités.

La complexité du temps

La fonction TSP(bitmask,pos) a 2^N valeurs pour le bitmask et N valeurs pour pos . Chaque fonction prend le temps O(N) pour s'exécuter (la boucle for ). Ainsi, cette implémentation prend du temps O(N^2 * 2^N) pour sortir la réponse exacte.