tsp using dynamic programming

Question

i was using a piece of code for implementing TSP using dynamic programming. i have found this code but cant figure out the compute() function and how it works. i dont know what are the variables for and also how it computes the path. any help is highly appreciated.

#include <stdio.h>
#include<limits.h>
#define size 10 //maximum 10 cities
#define min(a,b) a>b?b:a
#define sizePOW 1024
int n,npow,g[size][sizePOW],p[size][sizePOW],adj[size][size];
int compute(int start,int set)
{   
int masked,mask,result=INT_MAX,temp,i,t1;//result stores the minimum 
if(g[start][set]!=-1)//memoization DP top-down,check for repeated subproblem
    return g[start][set];
for(i=0;i<n;i++)
    {   //npow-1 because we always exclude "home" vertex from our set

        t1=1<<i;
        mask=(npow-1)-(1<<i);//remove ith vertex from this set
        masked=set&mask;
        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
        {   
            temp=adj[start][i]+compute(i,masked);//compute the removed set
            if(temp<result)
                result=temp,p[start][set]=i;//removing ith vertex gave us minimum
        }
    }
    return g[start][set]=result;//return minimum
}

void TSP()
{     
int i,j;
//g(i,S) is length of shortest path starting at i visiting all vertices in S and ending at 1
for(i=0;i<n;i++)
    for(j=0;j<npow;j++) 
            g[i][j]=p[i][j]=-1; 
for(i=0;i<n;i++){
    g[i][0]=adj[i][0];//g(i,nullset)= direct edge between (i,1)
}

int result=compute(0,npow-2);//npow-2 to exclude our "home" vertex
printf("Tour cost:%d\n",result);
printf("Tour path:\n0 ");
getpath(0,npow-2);
printf("0\n");
}
int main(void) {
int i,j;
printf("Enter number of cities\n");
scanf("%d",&n);
npow=(int)pow(2,n);//bit number required to represent all possible sets
printf("npow = %d   ",npow);
printf("\nEnter the adjacency matrix\n");

for(i=0;i<n;i++)for(j=0;j<n;j++){
scanf("%d",&adj[i][j]);}
TSP();

return 0;
}

Use a debugger, step through the code line by line, while monitoring the variables and their values, write down everything on paper. And do it many times, until you understand everything. — Some programmer dude, Aug 15 '14 at 07:40
He is talking about explaining what does this compute function do? — Am_I_Helpful, Aug 15 '14 at 07:41
`#define min(a,b) a>b?b:a` is not good. [Macro arguments should be enclosed in parentheses](https://stackoverflow.com/q/10820340/995714). A better way [would need some compiler extensions](https://stackoverflow.com/a/3437484/995714) — phuclv, Oct 07 '17 at 15:21

score 0 · Accepted Answer · answered Aug 15 '14 at 08:43

//g(i,S) is length of shortest path starting at i visiting all vertices in S and ending at 1

This comment is very important.

Image currently we are in "start", and the city we visited is "set"(represent in binary of set), how do we calculate the other status ?

For example we have an edge "start"->"i", then

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
    {   
        temp=adj[start][i]+compute(i,masked);//compute the removed set
        if(temp<result)
            result=temp,p[start][set]=i;//removing ith vertex gave us minimum
    }

This is calculating the status g[start][masked], using g[start][set] and the edge (start,i)

As we can see, the author use recursion and dynamic programming to solve the problem. Time is O(2^n * n^2)

tsp using dynamic programming

1 Answers1