fork 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 1000
  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.  
  187.         if(min->level == N - 1)
  188.         {
  189.             // return to starting city
  190.             min->path.push_back(make_pair(i, 0));
  191. 			// print list of cities visited;
  192.             if (min->cost == N)
  193.               printPath(min->path);
  194.  
  195. 			// return optimal cost
  196.             return min->cost;
  197.         }
  198.  
  199.         // do for each child of min
  200.         // (i, j) forms an edge in space tree
  201.         for(int j = 0; j < N; j++)
  202.         {
  203.             if(min->reducedMatrix[i][j] != INF)
  204.             {
  205.                 // create a child node and calculate its cost
  206.                 Node* child = newNode(min->reducedMatrix, min->path,
  207. 										min->level+1, i, j);
  208.  
  209. 				/* Cost of the child =
  210. 					cost of parent node +
  211. 					cost of the edge(i, j) +
  212. 					lower bound of the path starting at node j
  213. 				*/
  214.                 child->cost = min->cost + min->reducedMatrix[i][j] +
  215.                 			  calculateCost(child->reducedMatrix);
  216.  
  217.                 // Add child to list of live nodes
  218.                 pq.push(child);
  219.             }
  220.         }
  221.  
  222. 		// free node as we have already stored edges (i, j) in vector
  223. 		// So no need for parent node while printing solution.
  224.         free(min);
  225.     }
  226. }
  227.  
  228. // Driver function to test above functions
  229. int main()
  230. {
  231.     int costMatrix[N][N];
  232.  
  233.     for (int i=0; i<N; i++){
  234.       for (int j=0; j<N; j++){
  235.         cin >> costMatrix[i][j];
  236.       }
  237.     }
  238.  
  239.     cout << "Criou Matriz, agora aguarde. " << endl ;
  240.  
  241.     //cout << endl << endl ;
  242.  
  243.     if ( solve(costMatrix) == N )
  244.       cout << "Ciclo Hamiltoniano Encontrado!" << endl;
  245.     else
  246.       cout << "Nao ha Ciclo Hamiltoniano no Grafo!" << endl;
  247.  
  248.     return 0;
  249. }
  250.  
Runtime error #stdin #stdout #stderr 3.72s 1042944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Criou Matriz, agora aguarde.
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/qyEipK
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!