Compte tenu d'un ensemble de villes et d'une distance entre chaque paire de villes, le problème est de trouver la tournée la plus courte possible qui visite chaque ville une fois exactement et revient au point de départ.
Par exemple, considérez le graphique illustré sur la figure sur le côté droit. Une tournée TSP dans le graphique est de 0-1-3-2-0. Le coût de la visite est de 10 + 25 + 30 + 15, soit 80.
Nous avons discuté des solutions suivantes
1) Programmation naïve et dynamique
2) Solution approximative à l'aide de MST
Branche et solution liée
Comme on le voit dans les articles précédents dans la méthode de la branche et de la liaison pour le nœud actuel dans l'arbre, nous calculons une meilleure solution possible que nous pouvons obtenir si nous baissons ce nœud. Si la meilleure solution possible sur la meilleure solution est pire que le meilleur courant (mieux calculé jusqu'à présent), nous ignorons le sous-arbre enraciné avec le nœud.
Notez que le coût via un nœud comprend deux coûts.
1) Coût d'atteindre le nœud à partir de la racine (lorsque nous atteignons un nœud, nous avons ce coût calculé)
2) Coût d'atteindre une réponse du nœud actuel à une feuille (nous calculons un lien sur ce coût pour décider d'ignorer le sous-arbre avec ce nœud ou non).
- En cas de problème de maximisation Une limite supérieure nous indique la solution maximale possible si nous suivons le nœud donné. Par exemple dans 0/1 Knapsack Nous avons utilisé une approche gourmand pour trouver une limite supérieure .
- En cas de problème de minimisation Une borne inférieure nous indique la solution minimale possible si nous suivons le nœud donné. Par exemple dans Problème d'affectation d'emploi Nous obtenons une limite inférieure en attribuant un travail le moins coûteux à un travailleur.
Dans Branch and Bound, la partie difficile consiste à trouver un moyen de calculer une solution de meilleure solution possible. Vous trouverez ci-dessous une idée utilisée pour calculer les limites du problème des vendeurs itinérants.
Le coût de toute visite peut être écrit comme ci-dessous.
Cost of a tour T = (1/2) * ? (Sum of cost of two edges adjacent to u and in the tour T) where u ? V For every vertex u if we consider two edges through it in T and sum their costs. The overall sum for all vertices would be twice of cost of tour T (We have considered every edge twice.) (Sum of two tour edges adjacent to u) >= (sum of minimum weight two edges adjacent to u) Cost of any tour >= 1/2) * ? (Sum of cost of two minimum weight edges adjacent to u) where u ? V
Par exemple, considérez le graphique affiché ci-dessus. Vous trouverez ci-dessous le coût minimum de deux arêtes adjacentes à chaque nœud.
Node Least cost edges Total cost 0 (0 1) (0 2) 25 1 (0 1) (1 3) 35 2 (0 2) (2 3) 45 3 (0 3) (1 3) 45 Thus a lower bound on the cost of any tour = 1/2(25 + 35 + 45 + 45) = 75 Refer this for one more example.
Nous avons maintenant une idée du calcul de la borne inférieure. Voyons comment l'appliquer l'arbre de recherche d'espace d'état. Nous commençons à énumer tous les nœuds possibles (de préférence dans l'ordre lexicographique)
1. Le nœud racine: Sans perte de généralité, nous supposons que nous commençons au sommet «0» pour lesquels la borne inférieure a été calculée ci-dessus.
Traitant du niveau 2: Le niveau suivant énumère tous les sommets possibles auxquels nous pouvons aller (en gardant à l'esprit que dans n'importe quel chemin, un sommet ne doit se produire qu'une seule fois) qui sont 1 2 3 ... n (notez que le graphique est terminé). Considérons que nous calculons pour le sommet 1 puisque nous sommes passés de 0 à 1. Notre tour a maintenant inclus le bord 0-1. Cela nous permet d'apporter les modifications nécessaires dans la limite inférieure de la racine.
Lower Bound for vertex 1 = Old lower bound - ((minimum edge cost of 0 + minimum edge cost of 1) / 2) + (edge cost 0-1)
Comment ça marche? Pour inclure le bord 0-1, nous ajoutons le coût de bord de 0-1 et soustrayons un poids de bord de telle sorte que la borne inférieure reste aussi serrée que possible, ce qui serait la somme des bords minimaux de 0 et 1 divisé par 2. De toute évidence, le bord soustrait ne peut pas être plus petit que celui-ci.
Traitant d'autres niveaux: Au fur et à mesure que nous passons au niveau suivant, nous énumons à nouveau tous les sommets possibles. Pour le cas ci-dessus, aller plus loin après 1, nous vérifions 2 3 4 ... n.
Considérez la limite inférieure pour 2 lorsque nous avons passé de 1 à 1, nous incluons le bord 1-2 à la tournée et modifiez la nouvelle limite inférieure pour ce nœud.
Lower bound(2) = Old lower bound - ((second minimum edge cost of 1 + minimum edge cost of 2)/2) + edge cost 1-2)
Remarque: Le seul changement dans la formule est que cette fois, nous avons inclus le deuxième coût de bord minimum pour 1 car le coût de bord minimum a déjà été soustrait au niveau précédent.
C++
// C++ program to solve Traveling Salesman Problem // using Branch and Bound. #include
// Java program to solve Traveling Salesman Problem // using Branch and Bound. import java.util.*; class GFG { static int N = 4; // final_path[] stores the final solution ie the // path of the salesman. static int final_path[] = new int[N + 1]; // visited[] keeps track of the already visited nodes // in a particular path static boolean visited[] = new boolean[N]; // Stores the final minimum weight of shortest tour. static int final_res = Integer.MAX_VALUE; // Function to copy temporary solution to // the final solution static void copyToFinal(int curr_path[]) { for (int i = 0; i < N; i++) final_path[i] = curr_path[i]; final_path[N] = curr_path[0]; } // Function to find the minimum edge cost // having an end at the vertex i static int firstMin(int adj[][] int i) { int min = Integer.MAX_VALUE; for (int k = 0; k < N; k++) if (adj[i][k] < min && i != k) min = adj[i][k]; return min; } // function to find the second minimum edge cost // having an end at the vertex i static int secondMin(int adj[][] int i) { int first = Integer.MAX_VALUE second = Integer.MAX_VALUE; for (int j=0; j<N; j++) { if (i == j) continue; if (adj[i][j] <= first) { second = first; first = adj[i][j]; } else if (adj[i][j] <= second && adj[i][j] != first) second = adj[i][j]; } return second; } // function that takes as arguments: // curr_bound -> lower bound of the root node // curr_weight-> stores the weight of the path so far // level-> current level while moving in the search // space tree // curr_path[] -> where the solution is being stored which // would later be copied to final_path[] static void TSPRec(int adj[][] int curr_bound int curr_weight int level int curr_path[]) { // base case is when we have reached level N which // means we have covered all the nodes once if (level == N) { // check if there is an edge from last vertex in // path back to the first vertex if (adj[curr_path[level - 1]][curr_path[0]] != 0) { // curr_res has the total weight of the // solution we got int curr_res = curr_weight + adj[curr_path[level-1]][curr_path[0]]; // Update final result and final path if // current result is better. if (curr_res < final_res) { copyToFinal(curr_path); final_res = curr_res; } } return; } // for any other level iterate for all vertices to // build the search space tree recursively for (int i = 0; i < N; i++) { // Consider next vertex if it is not same (diagonal // entry in adjacency matrix and not visited // already) if (adj[curr_path[level-1]][i] != 0 && visited[i] == false) { int temp = curr_bound; curr_weight += adj[curr_path[level - 1]][i]; // different computation of curr_bound for // level 2 from the other levels if (level==1) curr_bound -= ((firstMin(adj curr_path[level - 1]) + firstMin(adj i))/2); else curr_bound -= ((secondMin(adj curr_path[level - 1]) + firstMin(adj i))/2); // curr_bound + curr_weight is the actual lower bound // for the node that we have arrived on // If current lower bound < final_res we need to explore // the node further if (curr_bound + curr_weight < final_res) { curr_path[level] = i; visited[i] = true; // call TSPRec for the next level TSPRec(adj curr_bound curr_weight level + 1 curr_path); } // Else we have to prune the node by resetting // all changes to curr_weight and curr_bound curr_weight -= adj[curr_path[level-1]][i]; curr_bound = temp; // Also reset the visited array Arrays.fill(visitedfalse); for (int j = 0; j <= level - 1; j++) visited[curr_path[j]] = true; } } } // This function sets up final_path[] static void TSP(int adj[][]) { int curr_path[] = new int[N + 1]; // Calculate initial lower bound for the root node // using the formula 1/2 * (sum of first min + // second min) for all edges. // Also initialize the curr_path and visited array int curr_bound = 0; Arrays.fill(curr_path -1); Arrays.fill(visited false); // Compute initial bound for (int i = 0; i < N; i++) curr_bound += (firstMin(adj i) + secondMin(adj i)); // Rounding off the lower bound to an integer curr_bound = (curr_bound==1)? curr_bound/2 + 1 : curr_bound/2; // We start at vertex 1 so the first vertex // in curr_path[] is 0 visited[0] = true; curr_path[0] = 0; // Call to TSPRec for curr_weight equal to // 0 and level 1 TSPRec(adj curr_bound 0 1 curr_path); } // Driver code public static void main(String[] args) { //Adjacency matrix for the given graph int adj[][] = {{0 10 15 20} {10 0 35 25} {15 35 0 30} {20 25 30 0} }; TSP(adj); System.out.printf('Minimum cost : %dn' final_res); System.out.printf('Path Taken : '); for (int i = 0; i <= N; i++) { System.out.printf('%d ' final_path[i]); } } } /* This code contributed by PrinciRaj1992 */
# Python3 program to solve # Traveling Salesman Problem using # Branch and Bound. import math maxsize = float('inf') # Function to copy temporary solution # to the final solution def copyToFinal(curr_path): final_path[:N + 1] = curr_path[:] final_path[N] = curr_path[0] # Function to find the minimum edge cost # having an end at the vertex i def firstMin(adj i): min = maxsize for k in range(N): if adj[i][k] < min and i != k: min = adj[i][k] return min # function to find the second minimum edge # cost having an end at the vertex i def secondMin(adj i): first second = maxsize maxsize for j in range(N): if i == j: continue if adj[i][j] <= first: second = first first = adj[i][j] elif(adj[i][j] <= second and adj[i][j] != first): second = adj[i][j] return second # function that takes as arguments: # curr_bound -> lower bound of the root node # curr_weight-> stores the weight of the path so far # level-> current level while moving # in the search space tree # curr_path[] -> where the solution is being stored # which would later be copied to final_path[] def TSPRec(adj curr_bound curr_weight level curr_path visited): global final_res # base case is when we have reached level N # which means we have covered all the nodes once if level == N: # check if there is an edge from # last vertex in path back to the first vertex if adj[curr_path[level - 1]][curr_path[0]] != 0: # curr_res has the total weight # of the solution we got curr_res = curr_weight + adj[curr_path[level - 1]] [curr_path[0]] if curr_res < final_res: copyToFinal(curr_path) final_res = curr_res return # for any other level iterate for all vertices # to build the search space tree recursively for i in range(N): # Consider next vertex if it is not same # (diagonal entry in adjacency matrix and # not visited already) if (adj[curr_path[level-1]][i] != 0 and visited[i] == False): temp = curr_bound curr_weight += adj[curr_path[level - 1]][i] # different computation of curr_bound # for level 2 from the other levels if level == 1: curr_bound -= ((firstMin(adj curr_path[level - 1]) + firstMin(adj i)) / 2) else: curr_bound -= ((secondMin(adj curr_path[level - 1]) + firstMin(adj i)) / 2) # curr_bound + curr_weight is the actual lower bound # for the node that we have arrived on. # If current lower bound < final_res # we need to explore the node further if curr_bound + curr_weight < final_res: curr_path[level] = i visited[i] = True # call TSPRec for the next level TSPRec(adj curr_bound curr_weight level + 1 curr_path visited) # Else we have to prune the node by resetting # all changes to curr_weight and curr_bound curr_weight -= adj[curr_path[level - 1]][i] curr_bound = temp # Also reset the visited array visited = [False] * len(visited) for j in range(level): if curr_path[j] != -1: visited[curr_path[j]] = True # This function sets up final_path def TSP(adj): # Calculate initial lower bound for the root node # using the formula 1/2 * (sum of first min + # second min) for all edges. Also initialize the # curr_path and visited array curr_bound = 0 curr_path = [-1] * (N + 1) visited = [False] * N # Compute initial bound for i in range(N): curr_bound += (firstMin(adj i) + secondMin(adj i)) # Rounding off the lower bound to an integer curr_bound = math.ceil(curr_bound / 2) # We start at vertex 1 so the first vertex # in curr_path[] is 0 visited[0] = True curr_path[0] = 0 # Call to TSPRec for curr_weight # equal to 0 and level 1 TSPRec(adj curr_bound 0 1 curr_path visited) # Driver code # Adjacency matrix for the given graph adj = [[0 10 15 20] [10 0 35 25] [15 35 0 30] [20 25 30 0]] N = 4 # final_path[] stores the final solution # i.e. the // path of the salesman. final_path = [None] * (N + 1) # visited[] keeps track of the already # visited nodes in a particular path visited = [False] * N # Stores the final minimum weight # of shortest tour. final_res = maxsize TSP(adj) print('Minimum cost :' final_res) print('Path Taken : ' end = ' ') for i in range(N + 1): print(final_path[i] end = ' ') # This code is contributed by ng24_7
// C# program to solve Traveling Salesman Problem // using Branch and Bound. using System; public class GFG { static int N = 4; // final_path[] stores the final solution ie the // path of the salesman. static int[] final_path = new int[N + 1]; // visited[] keeps track of the already visited nodes // in a particular path static bool[] visited = new bool[N]; // Stores the final minimum weight of shortest tour. static int final_res = Int32.MaxValue; // Function to copy temporary solution to // the final solution static void copyToFinal(int[] curr_path) { for (int i = 0; i < N; i++) final_path[i] = curr_path[i]; final_path[N] = curr_path[0]; } // Function to find the minimum edge cost // having an end at the vertex i static int firstMin(int[ ] adj int i) { int min = Int32.MaxValue; for (int k = 0; k < N; k++) if (adj[i k] < min && i != k) min = adj[i k]; return min; } // function to find the second minimum edge cost // having an end at the vertex i static int secondMin(int[ ] adj int i) { int first = Int32.MaxValue second = Int32.MaxValue; for (int j = 0; j < N; j++) { if (i == j) continue; if (adj[i j] <= first) { second = first; first = adj[i j]; } else if (adj[i j] <= second && adj[i j] != first) second = adj[i j]; } return second; } // function that takes as arguments: // curr_bound -> lower bound of the root node // curr_weight-> stores the weight of the path so far // level-> current level while moving in the search // space tree // curr_path[] -> where the solution is being stored // which // would later be copied to final_path[] static void TSPRec(int[ ] adj int curr_bound int curr_weight int level int[] curr_path) { // base case is when we have reached level N which // means we have covered all the nodes once if (level == N) { // check if there is an edge from last vertex in // path back to the first vertex if (adj[curr_path[level - 1] curr_path[0]] != 0) { // curr_res has the total weight of the // solution we got int curr_res = curr_weight + adj[curr_path[level - 1] curr_path[0]]; // Update final result and final path if // current result is better. if (curr_res < final_res) { copyToFinal(curr_path); final_res = curr_res; } } return; } // for any other level iterate for all vertices to // build the search space tree recursively for (int i = 0; i < N; i++) { // Consider next vertex if it is not same // (diagonal entry in adjacency matrix and not // visited already) if (adj[curr_path[level - 1] i] != 0 && visited[i] == false) { int temp = curr_bound; curr_weight += adj[curr_path[level - 1] i]; // different computation of curr_bound for // level 2 from the other levels if (level == 1) curr_bound -= ((firstMin(adj curr_path[level - 1]) + firstMin(adj i)) / 2); else curr_bound -= ((secondMin(adj curr_path[level - 1]) + firstMin(adj i)) / 2); // curr_bound + curr_weight is the actual // lower bound for the node that we have // arrived on If current lower bound < // final_res we need to explore the node // further if (curr_bound + curr_weight < final_res) { curr_path[level] = i; visited[i] = true; // call TSPRec for the next level TSPRec(adj curr_bound curr_weight level + 1 curr_path); } // Else we have to prune the node by // resetting all changes to curr_weight and // curr_bound curr_weight -= adj[curr_path[level - 1] i]; curr_bound = temp; // Also reset the visited array Array.Fill(visited false); for (int j = 0; j <= level - 1; j++) visited[curr_path[j]] = true; } } } // This function sets up final_path[] static void TSP(int[ ] adj) { int[] curr_path = new int[N + 1]; // Calculate initial lower bound for the root node // using the formula 1/2 * (sum of first min + // second min) for all edges. // Also initialize the curr_path and visited array int curr_bound = 0; Array.Fill(curr_path -1); Array.Fill(visited false); // Compute initial bound for (int i = 0; i < N; i++) curr_bound += (firstMin(adj i) + secondMin(adj i)); // Rounding off the lower bound to an integer curr_bound = (curr_bound == 1) ? curr_bound / 2 + 1 : curr_bound / 2; // We start at vertex 1 so the first vertex // in curr_path[] is 0 visited[0] = true; curr_path[0] = 0; // Call to TSPRec for curr_weight equal to // 0 and level 1 TSPRec(adj curr_bound 0 1 curr_path); } // Driver code static public void Main() { // Adjacency matrix for the given graph int[ ] adj = { { 0 10 15 20 } { 10 0 35 25 } { 15 35 0 30 } { 20 25 30 0 } }; TSP(adj); Console.WriteLine('Minimum cost : ' + final_res); Console.Write('Path Taken : '); for (int i = 0; i <= N; i++) { Console.Write(final_path[i] + ' '); } } } // This code is contributed by Rohit Pradhan
const N = 4; // final_path[] stores the final solution ie the // path of the salesman. let final_path = Array (N + 1).fill (-1); // visited[] keeps track of the already visited nodes // in a particular path let visited = Array (N).fill (false); // Stores the final minimum weight of shortest tour. let final_res = Number.MAX_SAFE_INTEGER; // Function to copy temporary solution to // the final solution function copyToFinal (curr_path){ for (let i = 0; i < N; i++){ final_path[i] = curr_path[i]; } final_path[N] = curr_path[0]; } // Function to find the minimum edge cost // having an end at the vertex i function firstMin (adj i){ let min = Number.MAX_SAFE_INTEGER; for (let k = 0; k < N; k++){ if (adj[i][k] < min && i !== k){ min = adj[i][k]; } } return min; } // function to find the second minimum edge cost // having an end at the vertex i function secondMin (adj i){ let first = Number.MAX_SAFE_INTEGER; let second = Number.MAX_SAFE_INTEGER; for (let j = 0; j < N; j++){ if (i == j){ continue; } if (adj[i][j] <= first){ second = first; first = adj[i][j]; } else if (adj[i][j] <= second && adj[i][j] !== first){ second = adj[i][j]; } } return second; } // function that takes as arguments: // curr_bound -> lower bound of the root node // curr_weight-> stores the weight of the path so far // level-> current level while moving in the search // space tree // curr_path[] -> where the solution is being stored which // would later be copied to final_path[] function TSPRec (adj curr_bound curr_weight level curr_path) { // base case is when we have reached level N which // means we have covered all the nodes once if (level == N) { // check if there is an edge from last vertex in // path back to the first vertex if (adj[curr_path[level - 1]][curr_path[0]] !== 0) { // curr_res has the total weight of the // solution we got let curr_res = curr_weight + adj[curr_path[level - 1]][curr_path[0]]; // Update final result and final path if // current result is better. if (curr_res < final_res) { copyToFinal (curr_path); final_res = curr_res; } } return; } // for any other level iterate for all vertices to // build the search space tree recursively for (let i = 0; i < N; i++){ // Consider next vertex if it is not same (diagonal // entry in adjacency matrix and not visited // already) if (adj[curr_path[level - 1]][i] !== 0 && !visited[i]){ let temp = curr_bound; curr_weight += adj[curr_path[level - 1]][i]; // different computation of curr_bound for // level 2 from the other levels if (level == 1){ curr_bound -= (firstMin (adj curr_path[level - 1]) + firstMin (adj i)) / 2; } else { curr_bound -= (secondMin (adj curr_path[level - 1]) + firstMin (adj i)) / 2; } // curr_bound + curr_weight is the actual lower bound // for the node that we have arrived on // If current lower bound < final_res we need to explore // the node further if (curr_bound + curr_weight < final_res){ curr_path[level] = i; visited[i] = true; // call TSPRec for the next level TSPRec (adj curr_bound curr_weight level + 1 curr_path); } // Else we have to prune the node by resetting // all changes to curr_weight and curr_bound curr_weight -= adj[curr_path[level - 1]][i]; curr_bound = temp; // Also reset the visited array visited.fill (false) for (var j = 0; j <= level - 1; j++) visited[curr_path[j]] = true; } } } // This function sets up final_path[] function TSP (adj) { let curr_path = Array (N + 1).fill (-1); // Calculate initial lower bound for the root node // using the formula 1/2 * (sum of first min + // second min) for all edges. // Also initialize the curr_path and visited array let curr_bound = 0; visited.fill (false); // compute initial bound for (let i = 0; i < N; i++){ curr_bound += firstMin (adj i) + secondMin (adj i); } // Rounding off the lower bound to an integer curr_bound = curr_bound == 1 ? (curr_bound / 2) + 1 : (curr_bound / 2); // We start at vertex 1 so the first vertex // in curr_path[] is 0 visited[0] = true; curr_path[0] = 0; // Call to TSPRec for curr_weight equal to // 0 and level 1 TSPRec (adj curr_bound 0 1 curr_path); } //Adjacency matrix for the given graph let adj =[[0 10 15 20] [10 0 35 25] [15 35 0 30] [20 25 30 0]]; TSP (adj); console.log (`Minimum cost:${final_res}`); console.log (`Path Taken:${final_path.join (' ')}`); // This code is contributed by anskalyan3.
Sortir :
Minimum cost : 80 Path Taken : 0 1 3 2 0
L'arrondissement se fait dans cette ligne de code:
if (level==1) curr_bound -= ((firstMin(adj curr_path[level-1]) + firstMin(adj i))/2); else curr_bound -= ((secondMin(adj curr_path[level-1]) + firstMin(adj i))/2);
Dans l'algorithme de la branche et du TSP lié, nous calculons une limite inférieure sur le coût total de la solution optimale en ajoutant les coûts de bord minimum pour chaque sommet, puis en divisant par deux. Cependant, cette limite inférieure peut ne pas être un entier. Pour obtenir un lien inférieur entier, nous pouvons utiliser l'arrondi.
Dans le code ci-dessus, la variable Curr_Bound contient la limite inférieure actuelle du coût total de la solution optimale. Lorsque nous visitons un nouveau sommet au niveau du niveau, nous calculons un nouveau New_Bound de liaison inférieure en prenant la somme des coûts de bord minimum pour le nouveau sommet et ses deux voisins les plus proches. Nous mettons ensuite à jour la variable Curr_Bound en arrondissant New_Bound vers l'entier le plus proche.
Si le niveau est 1, nous arrondissons vers l'entier le plus proche. En effet, nous n'avons visité qu'un seul sommet jusqu'à présent et que nous voulons être conservateurs dans notre estimation du coût total de la solution optimale. Si le niveau est supérieur à 1, nous utilisons une stratégie d'arrondi plus agressive qui prend en compte le fait que nous avons déjà visité certains sommets et pouvons donc faire une estimation plus précise du coût total de la solution optimale.
Complexité du temps: La pire complexité de la branche et de la liaison reste la même que celle de la force brute clairement parce que dans le pire des cas, nous n'aurons peut-être jamais la possibilité de tailler un nœud. Alors qu'en pratique, il fonctionne très bien en fonction de l'instance différente du TSP. La complexité dépend également du choix de la fonction de délimitation car ce sont les qui décident du nombre de nœuds à tailler.
Références:
http://lcm.csa.iisc.ernet.in/dsa/node187.html