旅行商问题_牛客博客

问题描述：
给定一个 $n$ 给顶点组成的带权有向图的距离矩阵 $d(i,j)$ 。要求从顶点 $0$ 出发，经过每个顶点恰好一次后在回到顶点 $0$ .问所经过的边的总权重的最小值是多少？

$2<=n<=15$

$0<=d(i,j)<=1000$

所有可能的路线共有 $(n-1)!$ 种，尽管 $n$ 很小了，仍然无法枚举每一种情况。
用 $Dijkstra$ 跑 $n$ 遍求解不能保证求出的最小值经过了所有的城市。

方法一：
记忆化搜索

$dp[s][v]$ ，表示从 $v$ 出发访问剩余所有顶点的最小花费，每个元数的选取与否对应到 $s$ 的二进制位里
初始化： $dp[(1<<n)-1][0]=0$ ，使得最终结果都回到了起点 $0$ .
状态方程中的一维表示的一个集合，对于不是整数（不是单纯的一个数）的情况，很多时候很难确定一个合式的递推顺序，因此使用记忆化搜索就可以避免这个问题。

记忆化搜索真的妙，思路清晰，很好懂也很好写。

部分代码：

int n;
int d[maxn][maxn];

int dp[1<<maxn][maxn];//记忆化搜索使用的数组

//已访问过的节点集合s，当前位置位v
int rec(int s,int v) {
    if(dp[s][v]>=0)
        return dp[s][v];

    if(s==(1<<n)-1&&v==0)
    //已访问过所有节点并回到0号点 
        return dp[s][v]=0;

    int res=inf;
    for(int u=0;u<n;++u) {
        if(!(s>>u&1)) {
            //下一步移动到顶点u 
            res=min(res,rec(s|1<<u,u)+d[v][u]);
        }
    }
    return dp[s][v]=res;
} 
void solve() {
    memset(dp,-1,sizeof dp);
    printf("%d\n",rec(0,0));
}

但是在这个问题中，对于任意两个整数 $i、j$ ,如果他们对应的集合有 $s(i) \subseteq s(j)$ ，就有 $i\subseteq j$ ，因此还可以用循环来写：（ $u\notin s$ ）

dp[s][v]=min(dp[s][v],dp[s|1<<u][u]+d[v][u]);

称集合 $s|1<<u$ 为集合 $t$ ，那么集合 $t$ 的十进制数一定是大于集合 $s$ 的

部分代码：参照记忆化搜索

int dp[1<<maxn][maxn];//DP数组 
void solve() {
    for(int s=0;s< 1<<n;++s)
        fill(dp[s],dp[s]+n,inf);
    dp[(1<<n)-1][0]=0;

    //根据递推式依次计算
    for(int s=(1<<n)-2;s>=0;s--)
    for(int v=0;v<n;++v)
    for(int u=0;u<n;++u)
    if(!(s>>u&1))
        dp[s][v]=min(dp[s][v],dp[s|1<<u][u]+d[v][u]); 

    printf("%d\n",dp[0][0]);
}