动态规划中的旅行商问题

Question

我正在尝试用 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;
}

Answer 1

让我们引入一个新的路径函数，它使用先前计算的 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);
}

动态规划中的旅行商问题

Travelling Salesman problem in dynamic programming

c++

dynamic-programming

traveling-salesman