fork(12) download
copy 
  1. // C++ Program to solve Traveling Salesman Problem using Branch and Bound.
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // N is number of total nodes on the graph or the cities in the map
  6. #define N 5
  7. // Sentinal value for representing infinity
  8. #define INF INT_MAX
  9.  
  10. // State Space Tree nodes
  11. struct Node
  12. {
  13.     // stores edges of state space tree
  14.     // helps in tracing path when answer is found
  15.     vector<pair<int, int> > path;
  16.  
  17.     // stores the reduced matrix
  18.     int reducedMatrix[N][N];
  19.  
  20.     // stores the lower bound 
  21.     int cost;
  22.  
  23. 	//stores current city number
  24.     int vertex;
  25.  
  26. 	// stores number of cities visited so far
  27.     int level;
  28. };
  29.  
  30. // Function to allocate a new node
  31. // (i, j) corresponds to visiting city j from city i
  32. Node* newNode(int parentMatrix[N][N], 
  33. 			vector<pair<int, int> > path, 
  34. 			int level, int i, int j)
  35. {
  36.     Node* node = new Node;
  37.  
  38. 	// stores ancestors edges of state space tree
  39.     node->path = path;
  40. 	// skip for root node
  41.     if(level != 0 )
  42. 		// add current edge to path
  43.         node->path.push_back(make_pair(i, j));
  44.  
  45.     // copy data from parent node to current node
  46.     memcpy(node->reducedMatrix, parentMatrix, 
  47.     		sizeof node->reducedMatrix);
  48.  
  49. 	// Change all entries of row i and column j to infinity
  50. 	// skip for root node
  51.     for(int k = 0; level != 0 && k < N; k++)
  52. 		// set outgoing edges for city i to infinity
  53.         node->reducedMatrix[i][k] = INF,
  54. 		// set incoming edges to city j to infinity
  55.         node->reducedMatrix[k][j] = INF;
  56.  
  57. 	// Set (j, 0) to infinity 
  58. 	// here start node is 0
  59.     node->reducedMatrix[j][0] = INF;
  60.  
  61.     // set number of cities visited so far
  62.     node->level = level;
  63.  
  64. 	// assign current city number
  65.     node->vertex = j;
  66.  
  67. 	// return node
  68.     return node;
  69. }
  70.  
  71. // Function to reduce each row in such a way that 
  72. // there must be at least one zero in each row
  73. int rowReduction(int reducedMatrix[N][N], int row[N])
  74. {
  75. 	// initialize row array to INF 
  76.     fill_n(row, N, INF);
  77.  
  78. 	// row[i] contains minimum in row i
  79.     for(int i = 0; i < N; i++)
  80.         for(int j = 0; j < N; j++)
  81.             if( reducedMatrix[i][j] < row[i])
  82.                 row[i] = reducedMatrix[i][j];
  83.  
  84. 	// reduce the minimum value from each element in each row.
  85.     for(int i = 0; i < N; i++)
  86.         for(int j = 0; j < N; j++)
  87.             if(reducedMatrix[i][j] != INF && row[i] != INF)
  88.                 reducedMatrix[i][j] -= row[i];
  89. }
  90.  
  91.  
  92. // Function to reduce each column in such a way that
  93. // there must be at least one zero in each column
  94. int columnReduction(int reducedMatrix[N][N], int col[N])
  95. {
  96. 	// initialize col array to INF 
  97.     fill_n(col, N, INF);
  98.  
  99. 	// col[j] contains minimum in col j
  100.     for(int i = 0; i < N; i++)
  101.         for(int j = 0; j < N; j++)
  102.             if(reducedMatrix[i][j] < col[j])
  103.                 col[j] = reducedMatrix[i][j];
  104.  
  105. 	// reduce the minimum value from each element in each column
  106.     for(int i = 0; i < N; i++)
  107.         for(int j = 0; j < N; j++)
  108.             if(reducedMatrix[i][j] != INF && col[j] != INF)
  109.                 reducedMatrix[i][j] -= col[j];	
  110. }
  111.  
  112. // Function to get the lower bound on
  113. // on the path starting at current min node
  114. int calculateCost(int reducedMatrix[N][N])
  115. {
  116. 	// initialize cost to 0
  117.     int cost = 0;
  118.  
  119. 	// Row Reduction
  120.     int row[N];
  121. 	rowReduction(reducedMatrix, row);
  122.  
  123. 	// Column Reduction
  124.     int col[N];
  125.     columnReduction(reducedMatrix, col);
  126.  
  127. 	// the total expected cost 
  128. 	// is the sum of all reductions
  129.     for(int i = 0; i < N; i++)
  130.         cost += (row[i] != INT_MAX) ? row[i] : 0,
  131.         cost += (col[i] != INT_MAX) ? col[i] : 0;
  132.  
  133.     return cost;
  134. }
  135.  
  136. // print list of cities visited following least cost
  137. void printPath(vector<pair<int, int> > list)
  138. {
  139.     for(int i = 0; i < list.size(); i++)
  140.         cout << list[i].first + 1<< " -> " <<
  141.                 list[i].second + 1<< endl;
  142. }
  143.  
  144. // Comparison object to be used to order the heap
  145. struct comp
  146. {
  147.     bool operator()(const Node* lhs, const Node* rhs) const
  148.     {
  149.         return lhs->cost > rhs->cost;
  150.     }
  151. };
  152.  
  153. // Function to solve Traveling Salesman Problem using Branch and Bound.
  154. int solve(int costMatrix[N][N])
  155. {
  156.     // Create a priority queue to store live nodes of
  157.     // search tree;
  158.     priority_queue<Node*, std::vector<Node*>, comp> pq;
  159.  
  160.     vector<pair<int, int> > v;
  161.     // create a root node and calculate its cost
  162. 	// The TSP starts from first city i.e. node 0
  163.     Node* root = newNode(costMatrix, v, 0, -1, 0);
  164. 	// get the lower bound of the path starting at node 0
  165.     root->cost = calculateCost(root->reducedMatrix);
  166.  
  167.     // Add root to list of live nodes;
  168.     pq.push(root);
  169.  
  170.     // Finds a live node with least cost,
  171.     // add its children to list of live nodes and
  172.     // finally deletes it from the list.
  173.     while(!pq.empty())
  174.     {
  175.         // Find a live node with least estimated cost
  176.         Node* min = pq.top();
  177.  
  178.         // The found node is deleted from the list of
  179.         // live nodes
  180.         pq.pop();
  181.  
  182. 		// i stores current city number
  183.         int i = min->vertex;
  184.  
  185.         // if all cities are visited
  186.         if(min->level == N - 1)
  187.         {
  188.             // return to starting city
  189.             min->path.push_back(make_pair(i, 0));
  190. 			// print list of cities visited;
  191.             printPath(min->path);
  192.  
  193. 			// return optimal cost
  194.             return min->cost;
  195.         }
  196.  
  197.         // do for each child of min
  198.         // (i, j) forms an edge in space tree
  199.         for(int j = 0; j < N; j++)
  200.         {
  201.             if(min->reducedMatrix[i][j] != INF)
  202.             {
  203.                 // create a child node and calculate its cost
  204.                 Node* child = newNode(min->reducedMatrix, min->path, 
  205. 										min->level+1, i, j);
  206.  
  207. 				/* Cost of the child = 
  208. 					cost of parent node + 
  209. 					cost of the edge(i, j) +
  210. 					lower bound of the path starting at node j
  211. 				*/
  212.                 child->cost = min->cost + min->reducedMatrix[i][j] + 
  213.                 			  calculateCost(child->reducedMatrix);
  214.  
  215.                 // Add child to list of live nodes
  216.                 pq.push(child);
  217.             }
  218.         }
  219. 		// free node as we have already stored edges (i, j) in vector
  220. 		// So no need for parent node while printing solution.
  221.         free(min);
  222.     }
  223. }
  224.  
  225. // Driver function to test above functions
  226. int main()
  227. {
  228.     // cost matrix for traveling salesman problem.
  229.     /*int costMatrix[N][N] =
  230.     {
  231.         {INF, 5,   INF, 6,   5,   4},
  232.         {5,   INF, 2,   4,   3,   INF},
  233.         {INF, 2,   INF, 1,   INF, INF},
  234.         {6,   4,   1,   INF, 7,   INF},
  235.         {5,   3,   INF, 7,   INF, 3},
  236.         {4,   INF, INF, INF, 3,   INF}
  237.     };
  238. */
  239.     // cost 34
  240.     int costMatrix[N][N] =
  241.     {
  242.         {INF, 10,  8,   9,   7},
  243.         {10,  INF, 10,  5,   6},
  244.         {8,  10,   INF, 8,   9},
  245.         {9,  5,    8,   INF, 6},
  246.         {7,  6,    9,   6,   INF}
  247.     };
  248.  
  249.     /*// cost 16
  250.     int costMatrix[N][N] =
  251.     {
  252.         {INF, 3,   1,   5,   8},
  253.         {3,   INF, 6,   7,   9},
  254.         {1,   6,   INF, 4,   2},
  255.         {5,   7,   4,   INF, 3},
  256.         {8,   9,   2,   3,   INF}
  257.     };*/
  258.  /*
  259.     // cost 8
  260.     int costMatrix[N][N] =
  261.     {
  262.         {INF, 2,   1,   INF},
  263.         {2,   INF, 4,   3},
  264.         {1,   4,   INF, 2},
  265.         {INF, 3,   2,   INF}
  266.     };
  267.  
  268.     //cost 12
  269.     int costMatrix[N][N] =
  270.     {
  271.         {INF, 5,   4,   3},
  272.         {3,   INF, 8,   2},
  273.         {5,   3,   INF, 9},
  274.         {6,   4,   3,   INF}
  275.     };
  276. */
  277.     cout << "\n\nTotal Cost is " << solve(costMatrix);
  278.  
  279.     return 0;
  280. }
  281.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 -> 3
3 -> 4
4 -> 2
2 -> 5
5 -> 1


Total Cost is 34
https://ideone.com/0TBgxr
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!