【挑战程序设计竞赛】 TSP 状态压缩动态规划

发表于

描述
其中 S 为未访问的城市集合，v为当前所在城市，d[v][u]为由 v 城市到 u 城市之间的距离。利用二进制01来保存访问的状态。第一个返回条件很好理解，就是记忆搜索。对于第二个和第三个需要好好理解一下。 dp[11111][4] 的值为无穷大，它不会经过循环，而是直接赋值。不用担心第一次的分支 dp[00001][0]没有出口，这个值肯定不是最小的，很可能是无穷大。

notes: 1<<n 代表1左移 n 位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int rec(int S, int v) {
    if (dp[S][v] >= 0) {
        return dp[S][v];
    }
    if (S == (1 << n) - 1 && v == 0) {
        return 0;
    }
    int res = BIGNUM;
    for (int u = 0; u < n; u++) {
        if (!(S >> u & 1)) {
            res = min(res, rec(S | 1 << u, u) + d[v][u]);
        }
    }
    return dp[S][v] = res;
}
1
2
//利用这一条语句进行调用，即最终结果
rec(0, 0)