In the previous post I posted on the idea of using BFS to enumerate the subsets incrementally based on the size (see the previous post). The power of this core framework is so immense let me show how we can implement the TSP based on the framework. The extra code is between the lines 82-90 (TSP Initialization) and 113-175. The same core can be easily adapted to solve several sub-set based Dynamic programming optimizations like the job-scheduling, vehicle routing problem (VRP). If you have not looked into one of the Google Code Jam 2008 (practice) problems the problem#4 which is a shopping problem can be easily solved by this core framework. Check this code TSP.C (use -std=c99 to compile).
1 /******************************* 2 * Subset Enumeration Algorithmic 3 * Framework and its illustration in 4 * finding TSP. 5 ******************************/ 6 #include<stdio.h> 7 #include<stdlib.h> 8 #include<string.h> 9 #include<assert.h> 10 #include<math.h> 11 #include "List.h" 12 unsigned int **GRAPH; 13 unsigned int subset_count=0; 14 //#define VERBOSE_MODE 1 15 void EnumSubSetsBFS(unsigned int n); 16 17 void CreateGraph(unsigned int *n){ 18 unsigned int i,j; 19 printf("Enter the Graph Size\n"); 20 scanf("%u",n); 21 if(*n>32){ 22 fprintf(stderr,"TODO: The Bitset currently supports only 32 bits\n"); 23 exit(1); 24 } 25 printf("Enter the weighted graph\n"); 26 GRAPH = (unsigned int **) malloc(sizeof(unsigned int *)*(*n)); 27 for(i=0;i<*n;i++){ 28 GRAPH[i] = (unsigned int *) malloc(sizeof(unsigned int)*(*n)); 29 for(j=0;j<*n;j++){ 30 scanf("%u",&(GRAPH[i][j])); 31 } 32 } 33 } 34 35 int main(){ 36 /*Create the Graph*/ 37 unsigned int n; 38 CreateGraph(&n); 39 EnumSubSetsBFS(n); 40 41 } 42 /*Returns the new tail of the list*/ 43 inline List* ListAppend(List **tail,void *_data){ 44 List *new_node = (List *)malloc(sizeof(new_node)*1); 45 assert(new_node); 46 if(!(*tail)){ 47 (*tail) = new_node; 48 (*tail)->_data = _data; 49 (*tail)->next = NULL; 50 return *tail; 51 } 52 new_node->_data = _data; 53 new_node->next = NULL; 54 (*tail)->next = new_node; 55 return new_node; 56 } 57 typedef struct _subset_{ 58 /*if i^th bit is set then subset has i^th 59 *element*/ 60 unsigned int ebits; 61 unsigned int max; /*Maximum element in the subset*/ 62 unsigned int size; /*Size of subset*/ 63 /*Pointer to the sub-problem */ 64 void *sub_problem; 65 }SubSet; 66 /*Enumerate the Subset using BFS, n is 67 *the set size [1,2...n] */ 68 void EnumSubSetsBFS(unsigned int n){ 69 unsigned int check_sub_set,k,i,j; 70 unsigned int current_level = 0; 71 List *bfs_list = NULL; 72 List *tail = NULL; List *free_node,*ptr; 73 SubSet *sub_set,*new_sub_set; 74 SubSet *one_sets = NULL; 75 76 one_sets = (SubSet *)malloc(sizeof(SubSet)*n); 77 assert(one_sets); 78 /*Add the 1-subsets*/ 79 for(i=1;i<n;i++){ 80 one_sets[i].ebits = 0; one_sets[i].ebits |= (1<<i); 81 one_sets[i].max = i; one_sets[i].size = 1; 82 /****SUBPROBLEM SPECIFIC*****/ 83 one_sets[i].sub_problem = (float *)malloc(sizeof(float)*n); 84 for(j=1;j<n;j++){ 85 if(i==j){ continue; } 86 /* TSP({i},j) */ 87 ((float *)one_sets[i].sub_problem)[j] = GRAPH[0][i]+GRAPH[i][j]; 88 printf("S({%u},%u) = %f\n",i+1,j+1,((float *)one_sets[i].sub_problem)[j]); 89 } 90 /*****************************/ 91 if(!tail){ 92 ListAppend(&bfs_list,(void *)&(one_sets[i])); 93 tail = bfs_list; 94 continue; 95 } 96 tail = ListAppend(&tail,(void *)&(one_sets[i])); 97 } 98 /*Now do the BFS*/ 99 while(bfs_list){ 100 sub_set = (SubSet *)bfs_list->_data; 101 free_node = bfs_list; 102 bfs_list=bfs_list->next; 103 subset_count++; 104 assert(sub_set->max < n); 105 for(i=((sub_set->max)+1);i<n;i++){ 106 new_sub_set = (SubSet *) malloc(sizeof(SubSet)*1); 107 new_sub_set->size = (sub_set->size)+1; 108 new_sub_set->max = i; 109 new_sub_set->ebits = (sub_set->ebits | (1<<i)); 110 111 112 113 /*****<begin>**SUBPROBLEM SPECIFIC******/ 114 /* S(X,j) = min_k {S(X-k,k) + d[k][j]}*/ 115 ptr = free_node; 116 float current_min = HUGE_VAL; 117 float *new_sub_problem; 118 float *sub_problem; float local_min; 119 unsigned int k1,jstart,jend; 120 List *ptr_prev; 121 122 new_sub_set->sub_problem = (float *) malloc(sizeof(float)*n); 123 new_sub_problem = (float *)new_sub_set->sub_problem; 124 125 if(new_sub_set->size == n-1){ 126 jstart = 0; jend = 1; 127 }else{ 128 jstart = 1; jend = n; 129 } 130 131 for(j=jstart;j<jend;j++){ 132 ptr = free_node; 133 current_min = HUGE_VAL; 134 if(new_sub_set->ebits & (1<<j)){ 135 /*Avoid computation of redundant subproblems like 136 *S({....,x_i,x_j,x_k,....},x_i) */ 137 new_sub_problem[j]=HUGE_VAL; 138 continue; 139 } 140 141 for(k=1;k<=new_sub_set->size;k++){ 142 do{ 143 check_sub_set = ((SubSet *)ptr->_data)->ebits; 144 check_sub_set ^= new_sub_set->ebits; 145 k1 = (int)log2(check_sub_set); 146 ptr_prev = ptr; 147 ptr=ptr->next; 148 }while(check_sub_set & (check_sub_set-1)); 149 sub_problem = (float *)((SubSet *)ptr_prev->_data)->sub_problem; 150 local_min = sub_problem[k1] + GRAPH[k1][j]; 151 152 if(local_min < current_min){ 153 current_min = local_min; 154 new_sub_problem[j] = current_min; 155 } 156 157 } 158 } 159 /*Print Solution to the Subproblem */ 160 unsigned int i1,istart,iend; 161 unsigned int j1; 162 163 for(i1=jstart;i1<jend;i1++){ 164 check_sub_set = new_sub_set->ebits; 165 if(check_sub_set & (1<<i1)){ continue; } 166 printf("S(%u,{ ",i1+1); 167 /*Get the elements back*/ 168 for(j1=0;j1<n;j1++){ 169 if(check_sub_set & (1<<j1)){ 170 printf(" %u ",j1+1); 171 } 172 } 173 printf("})=%f\n",((float *)(new_sub_set->sub_problem))[i1]); 174 } 175 /**********<END>***SUBPROBLEM SPECIFIC*************/ 176 177 178 tail = ListAppend(&tail,(void *)new_sub_set); 179 } 180 if(!(sub_set >= one_sets && sub_set <= &(one_sets[n-1]))){ 181 free(sub_set->sub_problem); 182 free(sub_set); 183 } 184 free(free_node); 185 } 186 for(i=0;i<n;i++){ 187 free(one_sets[i].sub_problem); 188 } 189 free(one_sets); 190 printf("SubsetCount=%u\n",subset_count); 191 } 192
Sample Input.
---------test5.txt----------
5
0 3 1 5 4
1 0 5 4 3
5 4 0 2 1
3 1 3 0 3
5 2 4 1 0
---------------------
[vamsik@abadon ~]$ ./a.out < test5.txt
Enter the Graph Size
Enter the weighted graph
S({2},3) = 8.000000
S({2},4) = 7.000000
S({2},5) = 6.000000
S({3},2) = 5.000000
S({3},4) = 3.000000
S({3},5) = 2.000000
S({4},2) = 6.000000
S({4},3) = 8.000000
S({4},5) = 8.000000
S({5},2) = 6.000000
S({5},3) = 8.000000
S({5},4) = 5.000000
S(4,{ 2 3 })=9.000000
S(5,{ 2 3 })=8.000000
S(3,{ 2 4 })=10.000000
S(5,{ 2 4 })=9.000000
S(3,{ 2 5 })=10.000000
S(4,{ 2 5 })=7.000000
S(2,{ 3 4 })=4.000000
S(5,{ 3 4 })=6.000000
S(2,{ 3 5 })=4.000000
S(4,{ 3 5 })=3.000000
S(2,{ 4 5 })=6.000000
S(3,{ 4 5 })=8.000000
S(5,{ 2 3 4 })=7.000000
S(4,{ 2 3 5 })=8.000000
S(3,{ 2 4 5 })=10.000000
S(2,{ 3 4 5 })=4.000000
S(1,{ 2 3 4 5 })=5.000000
SubsetCount=15
No comments:
Post a Comment