You can consider a problem like this, you are in node 1, and you have to visit node 2 5 & 10.  Now, you have to fine the minimum cost for this operation. You can called it DP also.

you have to visit l number of node, like l = 3. then node[] = 2, 3, 4
& your source is 1. now you have to find the minimum cost of the tour.

C[][] = cost matrix of the nodes.
P[0]=1;
for(i=1;i<=15;i++ )
{
P[i] = P[i-1]*2;
}

source = 1;
for(i=0;i<=P[l];i++)
{
for(j=0;j<l;j++)
{
bit[i][j] = MAX;
}
}

for(i=0;i<l;i++)
{
if( C[ source ][ node[i] ]!=MAX )
{
bit[ P[i] ][i] = C[ source ][ node[i] ];
}
}

for(i=0;i<P[l];i++)
{
for(j=0;j<l;j++)
{
if( bit[i][j]!=MAX )
{
for(k=0;k<l;k++)
{
if( (i%P[k+1])/P[k]==0 )
{
if( C[node[j]][node[k]]!=MAX )
{
if( bit[ i+P[k] ][k] > bit[i][j] + C[node[j]][node[k]] )
{
bit[ i+P[k] ][k] = bit[i][j] + C[node[j]][node[k]];
}
}
}
}
}
}
}

int res = MAX;

for(i=0;i<l;i++)
if(bit[P[l]-1][i]!=MAX)
if(res > bit[P[l]-1][i])
res = bit[P[l]-1][i];

printf(“%d\n”,res);

For reduce some complexity, you also can use bfs in bit mask.

Advertisements