我试图用c++动态编程解决旅行推销员的问题,我找到了一个使用掩码位的方法,我得到了最小的权重,但我不知道如何得到使用的路径,这将是非常有用的,如果有人找到一种方法。这是我的代码。
#include<iostream>
using namespace std;
#define INT_MAX 999999
int n=4;
int dist[10][10] = {
{0,20,42,25},
{20,0,30,34},
{42,30,0,10},
{25,34,10,0}
};
int VISITED_ALL = (1<<n) -1;
int dp[16][4];
int tsp(int mask,int pos){
if(mask==VISITED_ALL){
return dist[pos][0];
}
if(dp[mask][pos]!=-1){
return dp[mask][pos];
}
//Now from current node, we will try to go to every other node and take the min ans
int ans = INT_MAX;
//Visit all the unvisited cities and take the best route
for(int city=0;city<n;city++){
if((mask&(1<<city))==0){
int newAns = dist[pos][city] + tsp( mask|(1<<city), city);
ans = min(ans, newAns);
}
}
return dp[mask][pos] = ans;
}
int main(){
/* init the dp array */
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
dp[i][j] = -1;
}
}
cout<<"Travelling Saleman Distance is "<<tsp(1,0);
return 0;
}
让我们引入一个新的路径函数,它可以给出整个最优路径,使用之前计算的 dp 阵列。
void path(int mask,int pos){
if(mask==VISITED_ALL) return;
int ans = INT_MAX, chosenCity;
for(int city=0;city<n;city++){
if((mask&(1<<city))==0){
int newAns = dist[pos][city] + dp[mask|(1<<city)][city];
if(newAns < ans){
ans = newAns;
chosenCity = city;
}
}
}
printf("%d ",city); // here you get the current city you need to visit
path(mask|(1<<city),city);
}