动态规划|最短Hamilton路径

2022年12月22日11:23:10

“n个点，从0开始，到n结束，求涵盖所有点的最短路径”
有n个点，有n!条路径可以选择，不过题目中要求是0开始，n-1点结束，因此一共是(n-2)!条路径，在(n-2)！条路径中选择一条最短的路径即为答案，但是时间复杂度太高了。

使用动态规划来减少重复。

设w[][]为图的邻接表，用以表示点与点之间的权值；

f[j]为终点为j时的所有路线的集合（起点先不关注），而终点为j时，前面点的数量还是没有确定的，需要进行确定才可以进一步减少集合的范围。此时引入一个路径状态state[]，即终点为j时，前面走了几个点，走了哪些点，这样的话，f[j]的集合就划分的比较小了，可以思考如何转移状态了。
举个具体的路径看看如何转移：有这么一条路径，我称之为f[j]，这条路径走到了点j，状态为state[]{1,3,6,7,j}，说明此时j前面走过1,3,6,7这四个点，而这四个点的顺序并未定下来，这四个点每个点可以作为j前一步的点（设为k）。也就j前有这么四种情况：（x,x,x指的是除k外的另3个数）
x,x,x,1,j
x,x,x,3,j
x,x,x,6,j
x,x,x,7,j
因此只要知道哪个k的路径最短，即
x,x,x,1
x,x,x,3
x,x,x,6
x,x,x,7
那么f[k]+w[k][j]就是最短的f[j]。

这里的f[k]是指在状态state[]{x,x,x,k}时的f[k]
那么状态转移方程如下：
f[j] = f[k] + w[k][j]

其中：
j的路径状态state{1,3,6,7,j};
k的路径状态state{x,x,x,k}

这样看来是有点麻烦，状态表示还需要用二维数组去存储，不如把状态压缩一下，使用二进制位表示状态。即如果第x个点在路径上，则在二进制位上，第x个位置为1。

eg.state{1,3,6,7}表示为1100101，十进制是101
然后使用二维数组f[i][j]表示，就可以表示为f[101][7]，101是状态，7是最后一个点。

这样上面的转移方程就可以写成
f[i][j] = f[i-(1<<j)][k] + w[k][j];
其中i-(1<<j)是指把i这个数上面二进制位中的第j位的1减掉，把路径状态变成k的；就好比把state{1,3,6,7,j}中的j去掉，成为点7的路径状态了，即state{1,3,6,7}。

由于f[i][j]依赖于f[i-(1<<j)][k]，而i-(1<<j)≤i，因此需要先对i进行遍历。

f[i][j]中不止有一个k，因此需要循环所有的k进行比较，求得最少值，落到代码实现上面时，f[i][j]的初始值应该为一个非常大的值才好，这样求min时方便把初始值覆盖掉。
好了，马上要结束了，现在关注一下初始化的问题，由于题目中要求从点0开始，而不能是任意点开始，因此把f[1][0]设为0，其他的初始值为MAX_VALUE就可了。

Java 代码

import java.util.*;

/**
 * @desc 使用acwing（oj）用的模板
 */
public class Main {

    //定义容器、常数、读入
    int[][] w;
    int[][] f = new int[1<<21][21];
    Scanner jin = new Scanner(System.in);

    //oj要用的main方法
    public static void main(String[] args) {new Main().run();}//在oj中调用题解方法

    void run() {
        
        //读入题目数据
        int n = jin.nextInt();
        w = new int[n+1][n+1];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                w[i][j] = jin.nextInt();
            }
        }
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < n; j++){
                f[i][j] = Integer.MAX_VALUE>>1;
            }
        }        

        //调用解题方法
        int res = dp(n);
        //输出题解答案
        System.out.println(res);
    }



    int dp(int n) {
        f[1][0] = 0;
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < n; j++){
                if ((i >> j & 1) == 1){//点j必须在路径里面才可以
                    for(int k = 0; k < n; k++){
                        if(((i - (1 << j)) >> k & 1) == 1){//寻找一个k点，k必须存在于i中
                            f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        }
                    }
                }
            }
        }

        return f[(1<<n)-1][n-1];
    }
}