ブランチとバウンドを使用した旅行セールスマンの問題
あらゆる都市間の一連の都市と距離を考えると、問題は、すべての都市を一度訪れて出発点に戻る可能性が最も短いツアーを見つけることです。
たとえば、右側の図に示されているグラフを検討してください。グラフのTSPツアーは0-1-3-2-0です。ツアーのコストは10+25+30+15で、80です。
以下のソリューションについて説明しました
1） 素朴で動的なプログラミング
2） MSTを使用した近似ソリューション
分岐および結合ソリューション
Treeの現在のノードのBranch and Bound Methodの以前の記事で見られるように、このノードを下ると得られる可能性のあるソリューションのバインドを計算します。可能な限り最良のソリューション自体にバインドされている場合、現在のベスト（これまでのところベスト計算）よりも悪い場合、ノードでルート化されたサブツリーを無視します。
ノードを介したコストには2つのコストが含まれていることに注意してください。
1）ルートからノードに到達するコスト（ノードに到達すると、このコストが計算されます）
2）現在のノードから葉への回答に到達するコスト（このコストでバウンドを計算して、このノードでサブツリーを無視するかどうかを決定します）。
- の場合 最大化の問題 指定されたノードに従うと、上限が最大のソリューションを示します。たとえばで 0/1ナップサック私たちは貪欲なアプローチを使用して上限を見つけました 。
- の場合 最小化の問題 下限は、指定されたノードに従う場合、最小限のソリューションを示します。たとえばで ジョブの割り当ての問題 最小コストの仕事を労働者に割り当てることにより、下限を取得します。
ブランチとバウンドでは、挑戦的な部分は、可能な限り最良のソリューションで境界を計算する方法を考えています。以下は、旅行セールスマンの問題の境界を計算するために使用されるアイデアです。
ツアーの費用は以下のように書くことができます。
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
たとえば、上記のグラフを検討してください。以下は、すべてのノードに隣接する最小コスト2つのエッジです。
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.
これで、下限の計算についてのアイデアがあります。 State Space Search Treeを適用する方法を見てみましょう。考えられるすべてのノードの列挙を開始します（できれば辞書順に）
1。ルートノード： 一般性を失うことなく、下限が上記で計算された頂点「0」から始まると仮定します。
レベル2を扱う： 次のレベルでは、1 2 3 ... nです（グラフが完了していることに注意してください）。私たちは0から1に移動したので、頂点1を計算していると考えてください。ツアーにはエッジ0-1が含まれています。これにより、ルートの下限に必要な変更を加えることができます。
Lower Bound for vertex 1 = Old lower bound - ((minimum edge cost of 0 + minimum edge cost of 1) / 2) + (edge cost 0-1)
どのように機能しますか？エッジ0-1を含めるには、エッジコストが0-1のエッジコストを追加し、エッジ重量を減算して、下限が可能な限りタイトなままになります。
他のレベルを扱う： 次のレベルに進むと、可能なすべての頂点を再び列挙します。上記のケースについては、1後にさらに進む場合は、2 3 4 ... nをチェックします。
1から1に移動したので、2の下限を検討してください。エッジ1-2をツアーに含め、このノードの新しい下限を変更します。
Lower bound(2) = Old lower bound - ((second minimum edge cost of 1 + minimum edge cost of 2)/2) + edge cost 1-2)
注：式の唯一の変更は、最小エッジコストが以前のレベルですでに減算されているため、今回は1の2番目の最小エッジコストを含めたことです。
// C++ program to solve Traveling Salesman Problem // using Branch and Bound. #include using namespace std ; const int N = 4 ; // final_path[] stores the final solution ie the // path of the salesman. int final_path [ N + 1 ]; // visited[] keeps track of the already visited nodes // in a particular path bool visited [ N ]; // Stores the final minimum weight of shortest tour. int final_res = INT_MAX ; // Function to copy temporary solution to // the final solution 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 int firstMin ( int adj [ N ][ N ] int i ) { int min = INT_MAX ; 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 int secondMin ( int adj [ N ][ N ] int i ) { int first = INT_MAX second = INT_MAX ; 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[] void TSPRec ( int adj [ N ][ N ] 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 memset ( visited false sizeof ( visited )); for ( int j = 0 ; j <= level -1 ; j ++ ) visited [ curr_path [ j ]] = true ; } } } // This function sets up final_path[] void TSP ( int adj [ N ][ N ]) { int curr_path [ 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 ; memset ( curr_path -1 sizeof ( curr_path )); memset ( visited 0 sizeof ( curr_path )); // 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 int main () { //Adjacency matrix for the given graph int adj [ N ][ N ] = { { 0 10 15 20 } { 10 0 35 25 } { 15 35 0 30 } { 20 25 30 0 } }; TSP ( adj ); printf ( 'Minimum cost : %d n ' final_res ); printf ( 'Path Taken : ' ); for ( int i = 0 ; i <= N ; i ++ ) printf ( '%d ' final_path [ i ]); return 0 ; }
Java // 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 ( 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 ; 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 # 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# // 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
JavaScript 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.
出力：
Minimum cost : 80 Path Taken : 0 1 3 2 0
丸めはこのコードの行で行われています：
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);
ブランチおよびバウンドTSPアルゴリズムでは、各頂点の最小エッジコストを追加してから2で割ることにより、最適ソリューションの総コストの下限を計算します。ただし、この下限は整数ではない場合があります。整数の下限を取得するには、丸めを使用できます。
上記のコードでは、Curr_bound変数は、最適なソリューションの総コストに関する電流の下限を保持します。レベルレベルの新しい頂点にアクセスすると、新しい頂点とその2つの最も近い近隣の最小エッジコストの合計を取ることにより、新しい下限new_boundを計算します。次に、new_boundを最も近い整数に丸めてCurr_bound変数を更新します。
レベルが1の場合、最寄りの整数まで締めくくります。これは、これまでに1つの頂点しか訪れておらず、最適なソリューションの総コストの推定において保守的になりたいからです。レベルが1を超える場合は、すでにいくつかの頂点にアクセスしているため、最適なソリューションの総コストをより正確に推定できるという事実を考慮した、より積極的な丸め戦略を使用します。
時間の複雑さ： 最悪のケースの複雑さは、最悪の場合はノードを剪定する機会を得ることができない可能性があるため、ブルートフォースの最悪の場合と同じままです。一方、実際には、TSPの異なるインスタンスに応じて非常にうまく機能します。複雑さは、剪定されるノードの数を決定するものであるため、境界関数の選択にも依存します。
参考文献：
http://lcm.csa.iisc.ernet.in/dsa/node187.html
