最短Hamilton路径 题解

题意分析

• 给你0~n-1标号的n个点，以及它们之间的距离。
• 现在起点一定要是0，终点一定要是n-1
• 求0到n-1不重不漏每个点恰好经过一次，最短的路程是多少？
  • Sample Input
  • 4
  • 0 2 1 3
  • 2 0 2 1
  • 1 2 0 1
  • 3 1 1 0
• 首先确定是求：从0到3的Hamilton路径
• 样例解释表明：这样的路径有两条，0-1-2-3和0-2-1-3。前者的长度为2+2+1=5，后者的长度为1+2+1=4

解题思路

第一想法：递归

• 时间复杂度为。我一开始想，这个题目无非是设置一个used数组，然后开始dfs，
• 对于每一个点，它能跳转到的点，无非是别的没跳转到过的点而已。没毛病吧？
• 显然这个方法是超时的，我没有上手实现这个代码。

正解：动态规划

• 时间复杂度为
• 这个方法对于蒟蒻来说实在是太难了
  • 其实在上一种方法上，我还想到了一个方法：就是开一个数组f[1<<20]，f数组下标代表“选定的集合”，然后用元素值来存选定这个集合，里面的最短路径是多少。
  • 一样使用dfs来更新，然后进行一些最优型剪枝……
  • 但是这样的方法，不难看出时间复杂度最大还是那么多，并不是什么正解。
• 在放学坐车的路上遇到了机房大佬，藉口手机没电（其实有）后和机房大佬开始聊天。我借机赶紧转移话题，趁机套他这一题的题解。
• “正解是动态规划。”
• 为什么要开2维数组？
  • ，
    • 第一维代表：
      • 由于我们确定最后的状态一定是"1111..."，所以这个f数组下标代表一个的集合，下标代表已走过的点是哪些点，而这个下标的元素值代表走这些点的最短路径。
      • 其实，这个和上面提到的那个方法的f数组，不论是下标还是元素值作用都相同。
      • 接下来看第二维是怎么妙用的。
    • 第二维代表：
      • 既然上一维已经经过了这些（集合i里面的）点，那么第二维代表的就是“最后一个到达的是哪个点？”
      • 假如集合i是1111，那么j=0代表最后一个到达的是点1，j=1代表是点2，……
• 怎么想Dp？
  • 、
  • 。
    • 第一重循环代表枚举集合。(00000...~11111...)
      • 无非就是在集合尽可能空的情况下，不断给i集合放入新的点，更新f数组答案
    • 第二重循环代表枚举上一个点走过的是哪个()
      • 枚举i集合里面的每个点，如果0~n-1的所有点里面，有i已经走过的，我们就跳转（跳转到第三重循环
      • ，进入第三重：k循环代表我们要跳转到的下一个点，那个被跳转到的点位置上必须是0。()
  • 状态转移方程：
  • 
    • 当前我们已经确定下一个要跳转去的点是k点，
    • 所以转移方程要用Fij（也就是集合i，最后一个点走的是j的最短总路程，加上j到k的路程，尝试更新答案（也就是f[{i}+k],[k]，为什么第二维是k？因为从j到k之后，最后一个经过的点就是k点了。））。
    • 这样，我们的答案（也就是，终点必须是n-1，就会是最小的了）

参考程序

#include<stdio.h>
#include<string.h>
int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}
int n,dist[21][21];
int f[1<<21][21];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&dist[i][j]);

    memset(f,0x3f3f3f3f,sizeof f);
    f[1][0]=0;
    //两个很特殊的对于dp数组的预处理
    //第一重枚举集合
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            //我们设上一个经过的点为j
            if((i>>j)&1)
                //该位置上有1，启动k，
                //用k来转移
                for(int k=0;k<n;k++)
                    if(~(i>>k)&1)
                        {
                            f[i+(1<<k)][k]=min(f[i+(1<<k)][k],f[i][j]+dist[j][k]);
                        }
    printf("%d",f[(1<<n)-1][n-1]);
    return 0;
    //第二重枚举集合i里面的每一个有1的点
}