我当时使用一段代码来使用动态编程来实现TSP。我已经找到了此代码,但无法弄出compute()函数及其工作方式。我不知道什么是变量,以及它如何计算路径。任何帮助都将受到高度赞赏。
#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;
}
//g(i,S) is length of shortest path starting at i visiting all vertices in S and ending at 1
这个评论很重要。
当前我们处于“开始”的图像,而我们访问的城市是“集合”(以集合的二进制表示),我们如何计算其他状态?
例如,我们有一条边“ start”->“ i”,然后
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
}
这是使用g [start] [set]和边沿(start,i)计算状态g [start] [masked]
如我们所见,作者使用递归和动态编程来解决该问题。时间是O(2 ^ n * n ^ 2)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句