fork(93) download
copy 
  1. //Author: Rohan
  2. // Credits to-Aditya Nugroho
  3. //referred from-
  4. //http://w...content-available-to-author-only...d.com/doc/50049931/Final-Report-Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java-Program-Aditya-Nugroho-Ht083276e
  5. //commented and understood myself :)
  6. #include <stdio.h>
  7. #include<limits.h>
  8. #define size 10 //maximum 10 cities
  9. #define min(a,b) a>b?b:a
  10. #define sizePOW 1024 // 2^10
  11. //Space complexity: O(n * 2^n)
  12. //Time complexity: O(n^2 * 2^n)
  13. int n,npow,g[size][sizePOW],p[size][sizePOW],adj[size][size];
  14. int compute(int start,int set)
  15. {	int masked,mask,result=INT_MAX,temp,i;//result stores the minimum 
  16. 	if(g[start][set]!=-1)//memoization DP top-down,check for repeated subproblem
  17. 		return g[start][set];
  18. 	for(i=0;i<n;i++)
  19. 		{	//npow-1 because we always exclude "home" vertex from our set
  20. 			mask=(npow-1)-(1<<i);//remove ith vertex from this set
  21. 			masked=set&mask;
  22. 			if(masked!=set)//in case same set is generated(because ith vertex was not present in the set hence we get the same set on removal) eg 12&13=12
  23. 			{	
  24. 				temp=adj[start][i]+compute(i,masked);//compute the removed set
  25. 				if(temp<result)
  26. 					result=temp,p[start][set]=i;//removing ith vertex gave us minimum
  27. 			}
  28. 		}
  29. 		return g[start][set]=result;//return minimum
  30. }
  31. void getpath(int start,int set)
  32. {
  33. 	if(p[start][set]==-1) return;//reached null set
  34. 	int x=p[start][set];
  35. 	int mask=(npow-1)-(1<<x);
  36. 	int masked=set&mask;//remove p from set
  37. 	printf("%d ",x);
  38. 	getpath(x,masked);
  39. }
  40. void TSP()
  41. {	int i,j;
  42. 	//g(i,S) is length of shortest path starting at i visiting all vertices in S and ending at 1
  43. 	for(i=0;i<n;i++)
  44. 		for(j=0;j<npow;j++) 
  45. 				g[i][j]=p[i][j]=-1; 
  46. 	for(i=0;i<n;i++)g[i][0]=adj[i][0];//g(i,nullset)= direct edge between (i,1)
  47. 	int result=compute(0,npow-2);//npow-2 to exclude our "home" vertex
  48. 	printf("Tour cost:%d\n",result);
  49. 	printf("Tour path:\n0 ");
  50. 	getpath(0,npow-2);
  51. 	printf("0\n");
  52. }
  53. int main(void) {
  54. 	int i,j;
  55. 	printf("Enter number of cities\n");
  56. 	scanf("%d",&n);
  57. 	npow=(int)pow(2,n);//bit number required to represent all possible sets
  58. 	printf("Enter the adjacency matrix\n");
  59. 	for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&adj[i][j]);
  60. 	TSP();
  61. 	return 0;
  62. }
  63. /*
  64. Recursion tree for given input
  65. 					     	g(0,{1,2,3})
  66. 									14
  67.              /                      |                \
  68. 		12							10               6
  69.     g(1,{2,3})                g(2,{1,3})            g(3,{1,2})
  70.  
  71.     /         \             /          \             |       \
  72.   8            4          8             2           4           2
  73. g(2,{3})   g(3,{2})     g(1,{3})     g(3,{1})    g(1,{2})    g(2,{1})  
  74.  
  75.   /            |            |           |           |             |    
  76.  0             0            0           0           0             0
  77. g(3,null)   g(2,null)    g(3,null)   g(1,null)   g{2,null)    g(1,null)
  78. */
  79.  
Success #stdin #stdout 0s 2376KB
comments (?)
stdin
copy 
4
0 10 15 20
5 0 9 10
6 13 0 12

8 8 9 0
stdout
copy 
Enter number of cities
Enter the adjacency matrix
Tour cost:35
Tour path:
0 1 3 2 0
https://ideone.com/tYdrK8
TSP DP using bitmasking g(i,S)
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

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!