JAVA实现 (详细分析+注释)
普通的YSDP, 普通的状态压缩
时间复杂度
时间复杂度: O(2^n * n)
空间复杂度: O(2^n * n)
时间复杂度分析的不够准确,仅供参考.
JAVA 代码
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] a = new int[n][n];
String[] nums = null;
for (int r = 0; r < n; ++r) {
nums = br.readLine().split(" ");
for (int c = 0; c < n; ++c)
a[r][c] = Integer.parseInt(nums[c]);
}
br.close();
System.out.println(shortestHamiltonDistance(a));
}
/* 输入矩阵表示的带权无向图,返回最小Hamilton路径
时间:O(2^n * n)
空间:O(2^n * n)
*/
private static int shortestHamiltonDistance(int[][] mat) {
int n = mat.length;
int[][] dp = new int[1 << n][n];
//初始化,求MIN,将边界初始为+INF
//用一个比较大的数即可,否则用MAX_VALUE求和后整型溢出变成负数,再取MIN后会出错
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; //从点0走到点0,经过路径为(1)b
//DP
for (int i = 0; i < (1 << n); ++i) //遍历每行
for (int j = 0; j < n; ++j) //遍历每列
if ((i >> j & 1) == 1) //从点0走到点j,路径i必须包含点j
for (int k = 0; k < n; ++k) //枚举路径上所有可能的、走到节点j之前的一个节点
//从点0走到点k的路径 = 路径i除去点j(i - (1 << j))
//且必须包含点k(... >> k & 1)的路径
if (((i - (1 << j)) >> k & 1) == 1)
dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + mat[k][j]);
return dp[(1 << n) - 1][n - 1]; //返回从点0走到点n-1,所有路径的最小值
}
}