MENU

最短Hamilton路径

February 18, 2019 • Read: 417 • 算法


NP Hard问题,暴力时间复杂度$O(n*n!)$

这题正解其实是利用状压DP的方法来做,状态转移方程为

dp[i][j] = min{dp[i][j], dp[i - (1 << j)][k] + map[k][j]}

其中map数组为权值,map[k][j]是点k到点j的权值

dp[i][j]表示当前已经走过点的集合为i,移动到j。所以这个状态转移方程就是找一个中间点k,将已经走过点的集合i中去除掉j(表示j不在经过的点的集合中),然后再加上从k到j的权值

问题在于如何表达已经走过点的集合i,其实很简单,假如走过0,1,4这三个点,我们用二进制10011就可以表示,2,3没走过所以是0

那么走过点的集合i中去除掉点j也很容易表示i - (1 << j),比方说i是{0,1,4},j是1,那么i = 10011(1 << j) = 10i - (1 << j) = 10001

那么问题的答案就应该是dp[01....111][n-1],表示0~n-1都走过,且当前移动到n-1这个点

分析一下时间复杂度,n为20的时候,外层循环(1<<20),内层循环20,所以整体时间复杂度$O(20*2^{20})$,这比$O(n*n!)$快多了

import java.util.Scanner;

public class Main {
    static int[][] dp = new int[1 << 20][20];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = cin.nextInt();
        for (int i = 0; i < (1 << n); i++) 
            for (int j = 0; j < n; j++)
                dp[i][j] = Integer.MAX_VALUE >> 1;
        dp[1][0] = 0;
        for (int i = 0; i < (1 << n); i++) // 二进制枚举走过的点的集合
            for(int j = 0; j < n; j++)
                if ((i >> j & 1) == 1)
                    for (int k = 0; k < n; k++) 
                        if ((i - (1 << j) >> k & 1) == 1)
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + map[j][k]);
        System.out.println(dp[(1 << n) - 1][n - 1]);
    }
}
最后编辑于: September 16, 2019
Archives Tip
QR Code for this page
Tipping QR Code