algorithm
Vendeur ambulant
Recherche…
Remarques
Le problème du vendeur itinérant est le problème de trouver le coût minimum de déplacement à travers N sommets exactement une fois par sommet. Il y a un coût de cost[i][j] pour passer du sommet i au sommet j .
Il existe 2 types d’algorithmes pour résoudre ce problème: Algorithmes exacts et algorithmes d’approximation
Algorithmes exacts
- Algorithme de force brutale
- Algorithme de programmation dynamique
Algorithmes d'approximation
Être ajouté
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.
