动态规划中的旅行商问题
动态规划中的旅行商问题
提问于 2020-05-18 11:59:43
我试图用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;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2020-05-18 17:09:17
让我们引入一个新的路径函数，它使用先前计算的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);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61869112
复制相关文章
相似问题
腾讯云开发者
