TSP с использованием динамического программирования
Я изучаю TSP и нашел это рекурсивное решение для TSP
int compute(int start,int set)
{ int masked,mask,result=INT_MAX,temp,i;//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
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
}
Я не мог понять, как работает маскирование, как можно изменить его на решение динамического программирования без использования рекурсии, пожалуйста, помогите мне.
Решение
Вот это традиционная проблема TSP, и вот решение для нее. Я думаю, что это может быть полезно для вас.
int map[15][15];
int dp[(1<<12)+5][12];
int main() {
int i,j,n,ans,k,p;
while(1) {
scanf("%d",&n);
if (n==0) break;
n++;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
scanf("%d",&map[i][j]);
}
}
//floyd algorithm, get any two points's minimum distance
for (k=0; k<n; k++) {
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
if (i!=j && i!=k && j!=k) map[i][j]=min(map[i][k]+map[k][j],map[i][j]);
}
}
}
memset(dp,-1,sizeof(dp));
dp[1][0]=0;
// TSP solution here,bitmask and DP
for (i=1; i<(1<<n); i++) {// the current state
for (j=0; j<n; j++) {// during the current state,the last station is j
if (dp[i][j]==-1) continue;
for (k=1; k<n; k++) {//the next state is k
if ((i & (1<<k))!=0) continue;
p=(i | (1<<k));// the new state(join k)
if (dp[p][k]==-1) dp[p][k]=dp[i][j]+map[j][k];
dp[p][k]=min(dp[p][k],dp[i][j]+map[j][k]);
}
}
}
ans=INF;
// get answer
for (i=1; i<n; i++) {
if (dp[(1<<n)-1][i]>0) ans=min(ans,dp[(1<<n)-1][i]+map[i][0]);
}
printf("%d\n",ans);
}
return 0;
}
Другие решения