动态规划 DP 应用 HamiltonPath 及 TSP

|

Hamilton Path 及 TSP 都属于 NP 完全问题，目前理论上尚无多项式算法，穷举法的时间复杂度是 O(N!)，通过运用动态规划 DP，可以缩短至 O(2^N * N^2)。

输入：无向图 G = (V, E)，点集 V = {0, 1, … , n-1}，起始点 0

最优子结构：考虑路径上的最后一条边

dp[s,j] = min ( dp[s-{j},i] + adj[i,j] )

dp[s+{j},j] = min ( dp[s,i] + adj[i,j] )

i、j：点。

s：点集合。

dist[s,j]：经过 S 中所有点一次且最后一点是 j 的路径长度。

adj[i,j]：adjacency matrix。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N = 5;    // 点的数目
int dp[1 << N][N];
int adj[N][N] = { { 0, 1, 10, 1, 10 }, { 1, 0, 10, 10, 1 }, { 10, 10, 0, 1, 1 }, { 1, 10, 1, 0, 10 },
				{ 10, 1, 1, 10, 0 } };
int answer;


void TSP(int s, int i, int s_size)
{
    if (s_size == N)
    {
        // 最后再加上一条回到原点的边，形成环状回路
        if (dp[s][i] + adj[i][0] < answer)
            answer = dp[s][i] + adj[i][0];
        return;
    }
 
    for (int j = 1; j < N; ++j) // 只走第0点以外的点
        if (!(s & (1 << j)))
        {
            // ss = s + {j};
            int ss = s | (1 << j);
            if (!dp[ss][j] || dp[s][i] + adj[i][j] < dp[ss][j])
            {
                dp[ss][j] = dp[s][i] + adj[i][j];
                TSP(ss, j, s_size + 1);
            }
        }
}


int main (int argc, char const *argv[])
{
	answer = 1e9;
	memset(dp, 0, sizeof(dp));
	TSP(0, 0, 1);   // 从第0点出发
	printf("%d\n", answer);
	return 0;
}

非递归 Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;

public class ShortestHamiltonianCycle {

    public static int getShortestHamiltonianCycle(int[][] dist) {
        int n = dist.length;
        int[][] dp = new int[1 << n][n];
        for (int[] d : dp)
            Arrays.fill(d, Integer.MAX_VALUE / 2);
        dp[1][0] = 0;
        for (int mask = 1; mask < 1 << n; mask += 2) {
            for (int i = 1; i < n; i++) {
                if ((mask & 1 << i) != 0) {
                    for (int j = 0; j < n; j++) {
                        if ((mask & 1 << j) != 0) {
                            dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                        }
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[(1 << n) - 1][i] + dist[i][0]);
        }

        // reconstruct path
        int cur = (1 << n) - 1;
        int[] order = new int[n];
        int last = 0;
        for (int i = n - 1; i >= 1; i--) {
            int bj = -1;
            for (int j = 1; j < n; j++) {
                if ((cur & 1 << j) != 0 && (bj == -1 || dp[cur][bj] + dist[bj][last] > dp[cur][j] + dist[j][last])) {
                    bj = j;
                }
            }
            order[i] = bj;
            cur ^= 1 << bj;
            last = bj;
        }
        System.out.println(Arrays.toString(order));
        return res;
    }

    // Usage example
    public static void main(String[] args) {
        int[][] dist = { { 0, 1, 10, 1, 10 }, { 1, 0, 10, 10, 1 }, { 10, 10, 0, 1, 1 }, { 1, 10, 1, 0, 10 },
                { 10, 1, 1, 10, 0 } };
        System.out.println(5 == getShortestHamiltonianCycle(dist));
    }
}

参考
http://codeforces.com/blog/entry/337

http://acm.nudt.edu.cn/~twcourse/DynamicProgramming.html

http://www.csie.ntnu.edu.tw/~u91029/AlgorithmDesign2.html