Tuesday, July 08, 2008

[TECH] Illustration of how to use the BFS based subset enumeration algorithmic framework to solve TSP.

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);
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
---------------------
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