Problém s cestovným predajcom pomocou pobočky a viazaných
Vzhľadom na súbor miest a vzdialenosť medzi každým párom miest je problém nájsť najkratšiu možnú prehliadku, ktorá navštívi každé mesto presne raz a vráti sa do východiskového bodu.
Napríklad zvážte graf zobrazený na obrázku na pravej strane. Prehliadka TSP v grafe je 0-1-3-2-0. Náklady na prehliadku sú 10+25+30+15, čo je 80.
Diskutovali sme o nasledujúcich riešeniach
1) Naivné a dynamické programovanie
2) Približné riešenie pomocou MST
Vetvenie a viazané roztok
Ako je vidieť v predchádzajúcich článkoch v vetve a viazanej metóde pre aktuálny uzol v strome, vypočítame viazanie na najlepšie možné riešenie, ktoré môžeme získať, ak budeme tento uzol. Ak je hranica na najlepšom možnom riešení horšia ako najlepšia súčasná (zatiaľ najlepšie vypočítaná), ignorujeme podstrom zakoreneného s uzlom.
Všimnite si, že náklady prostredníctvom uzla obsahujú dve náklady.
1) Náklady na dosiahnutie uzla z koreňa (keď dosiahneme uzol, máme vypočítané tieto náklady)
2) Náklady na dosiahnutie odpovede z aktuálneho uzla na list (vypočítame viazanie týchto nákladov, aby sme sa rozhodli, či budeme ignorovať podstrom týmto uzlom alebo nie).
- V prípadoch a maximalizácia Horná hranica nám hovorí maximálne možné riešenie, ak sledujeme daný uzol. Napríklad v 0/1 bathack sme použili chamtivé prístupy na nájdenie hornej hranice .
- V prípadoch a problém minimalizácie Spodná hranica nám hovorí minimálne možné riešenie, ak sledujeme daný uzol. Napríklad v Problém s priradením úlohy Dostávame nižšiu hranicu tým, že pracovníkovi priraďujeme najmenej cenovú prácu.
V pobočke a viazanej náročnej časti je zisťovanie spôsobu vypočítania viazania na najlepšie možné riešenie. Nižšie je uvedený nápad, ktorý sa používa na výpočet hraníc pre problém s cestovaním predavača.
Náklady na akékoľvek turné je možné napísať, ako je uvedené nižšie.
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
Napríklad zvážte vyššie uvedený graf. Nižšie sú nižšie minimálne náklady na dve hrany susediace s každým uzlom.
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.
Teraz máme predstavu o výpočte dolnej hranice. Pozrime sa na to, ako ho použiť strom vyhľadávania stavu. Začneme vymenovať všetky možné uzly (najlepšie v lexikografickom poradí)
1. Koreňový uzol: Bez straty všeobecnosti predpokladáme, že začíname na vrchole „0“, pre ktoré bola vypočítaná dolná hranica vyššie.
Zaobchádzanie s úrovňou 2: Ďalšia úroveň vymenúva všetky možné vrcholy, na ktoré môžeme ísť (nezabudnite, že v akejkoľvek ceste musí vyskytnúť vrchol iba raz), ktoré sú 1 2 3 ... N (všimnite si, že graf je dokončený). Zvážte, že počítame pre vrchol 1, pretože sme sa presunuli z 0 na 1, naša prehliadka teraz zahrnula Edge 0-1. To nám umožňuje vykonať potrebné zmeny v dolnej hranici koreňa.
Lower Bound for vertex 1 = Old lower bound - ((minimum edge cost of 0 + minimum edge cost of 1) / 2) + (edge cost 0-1)
Ako to funguje? Aby sme zahrnuli okraj 0-1, pridáme hrany náklady 0-1 a odpočítame hmotnosť okraja tak, že spodná hranica zostáva čo najtesnejšia, čo by bolo súčtom minimálnych hrán 0 a 1 vydelených 2. Je zrejmé, že odpočítaná hrana nemôže byť menšia ako táto.
Zaobchádzanie s inými úrovňami: Keď prejdeme na ďalšiu úroveň, znova vymenujeme všetky možné vrcholy. Pre vyššie uvedený prípad ide ďalej po 1, aby sme sa pozreli na 2 3 4 ... n.
Zvážte dolnú hranicu pre 2, keď sme sa presunuli z 1 na 1, zahrnujeme hranicu 1-2 na prehliadku a meníme novú dolnú hranicu pre tento uzol.
Lower bound(2) = Old lower bound - ((second minimum edge cost of 1 + minimum edge cost of 2)/2) + edge cost 1-2)
Poznámka: Jedinou zmenou vo vzorci je, že tentoraz sme zahrnuli druhé minimálne náklady na hrany za 1, pretože minimálne náklady na okraj sa už odpočítali na predchádzajúcej úrovni.
// 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.
Výstup:
Minimum cost : 80 Path Taken : 0 1 3 2 0
Zaokrúhlenie sa vykonáva v tomto riadku kódu:
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);
V algoritme vetvenia a viazaného TSP vypočítame dolnú hranicu celkových nákladov na optimálne riešenie spočítaním minimálnych nákladov na okraj pre každý vrchol a potom rozdelím dvoma. Táto spodná hranica však nemusí byť celé číslo. Aby sme získali celé číslo dolnej hranice, môžeme použiť zaokrúhlenie.
Vo vyššie uvedenom kóde je premenná Curr_bound drží aktuálnu dolnú hranicu celkových nákladov na optimálne riešenie. Keď navštívime nový vrchol na úrovni úrovne, vypočítame nový dolnú hranicu New_bound tým, že vezmeme súčet minimálnych nákladov na okraj pre nový vrchol a jeho dvoch najbližších susedov. Potom aktualizujeme premennú Curr_bound zaokrúhľovaním new_bound na najbližšie celé číslo.
Ak je úroveň 1, zaokrúhlime sa nadol na najbližšie celé číslo. Je to preto, že sme doteraz navštívili iba jeden vrchol a my chceme byť konzervatívni v našom odhade celkových nákladov na optimálne riešenie. Ak je úroveň vyššia ako 1, používame agresívnejšiu stratégiu zaokrúhľovania, ktorá zohľadňuje skutočnosť, že sme už navštívili niektoré vrcholy, a preto môžeme urobiť presnejší odhad celkových nákladov na optimálne riešenie.
Časová zložitosť: Najhoršia zložitosť vetvy a viazaného zostáva rovnaká ako v prípade brutálnej sily jasne, pretože v najhoršom prípade nikdy nebudeme mať šancu prerezať uzol. Zatiaľ čo v praxi to funguje veľmi dobre v závislosti od rôznych prípadov TSP. Zložitosť závisí aj od výberu ohraničujúcej funkcie, pretože sú to, že sa rozhodujú, koľko uzlov sa má prerezať.
Referencie:
http://lcm.csa.iisc.ernet.in/dsa/node187.html
