CH0103 最短Hamilton路径

Description

给定一张个点的带权无向图，点从标号，求起点 0 到终点 n-1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

Input

第一行一个整数。

接下来行每行个整数，其中第行第个整数表示点到的距离（一个不超过的正整数，记为）。

对于任意的，数据保证，并且。

Output

一个整数，表示最短 Hamilton 路径的长度。

Sample Input

Sample Output

说明：从 0 到 3 的 Hamilton 路径有两条，0-1-2-3 和 0-2-1-3。前者的长度为 2+2+1=5，后者的长度为 1+2+1=4

Limit

Time Limit	Memory Limit
C/C++/Rust/Pascal 1 秒，其他语言 2 秒	C/C++/Rust/Pascal 256 M，其他语言 512 M

Analysis

DFS(TLE)

最朴素的想法当然是 DFS 啦：

#include <iostream>

const int N = 25;
const int INF = 0x3f3f3f3f;

int ans = INF;
int n, g[N][N], st;

void dfs(int p, int dist) {
    if(st == (1 << n) - 1 && p == n - 1) {
        ans = ans > dist ? dist : ans;
        return ;
    }
    for(int t = 0; t < n; ++t) {
        if(st & (1 << t)) continue;
        st += 1 << t;
        dfs(t, dist + g[p][t]);
        st -= 1 << t;
    }
}

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            std::cin >> g[i][j];
    
    dfs(0, 1);
    
    std::cout << ans;
}

20! = 2432902008176640000，大概需要计算 24329020081s 才能得到答案吧

即使考虑剪枝优化，如 if(p == n - 1 && st != (1 << n) - 1) return ; 也不能很好地降低时间复杂度。

贪心 Kruskal(WA)

题目特别说了，并且起点和终点一定是和，那么这两个条件大概是突破口，一个可能的想法是考虑先取非、点，确认它们组成的最短路径，再将这个最短路径的两个端点分别连接到、。
对于找非、点组成的经过各点各一次的最短路径，一个想法是添加节点度信息的 Kruskal，若某节点的度已经等于，那么它不能再增加度了，对于得到的路径的两个端点，其度一定为：

#include <iostream>
#include <vector>
#include <algorithm>
#define x first
#define y second.first
#define z second.second
using PIII = std::pair<int, std::pair<int, int>>;

const int N = 25;

int n, w, d[N], p[N], g[N][N];
std::vector<PIII> edges;

int find(int i) {
    return p[i] == i ? i : p[i] = find(p[i]);
}

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> n;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            std::cin >> w;
            g[i][j] = w;
            if(i != j) edges.push_back({i,{j, w}});
        }
    }

    int m = n - 2;
    if(m == 0) {
        std::cout << g[1][n] << '\n';
        return 0;
    }
    if(m == 1) {
        std::cout << g[1][2] + g[2][n] << '\n';
        return 0;
    }

    for(int i = 1; i <= n; ++i) p[i] = i;

    std::sort(edges.begin(), edges.end(), [](const PIII& a, const PIII& b) {
        return a.z < b.z;
    });

    int ans = 0;

    for(auto& t : edges) {
        if(find(t.x) != find(t.y) && t.x != 1 && t.x != n && t.y != 1 && t.y != n && d[t.x] < 2 && d[t.y] < 2) {
            ans += t.z;
            p[find(t.x)] = find(t.y);
            ++d[t.x];
            ++d[t.y];
        }
    }

    int end[2], idx = 0;
    for(int i = 1; i <= n; ++i) {
        if(d[i] == 1) end[idx++] = i;
    }
    
    std::cout << ans + (std::min(g[1][end[0]] + g[n][end[1]], g[n][end[0]] + g[1][end[1]]));
}

如何证明这个思路是否正确？
Q1：Kruskal 在该无向图中真的能找到一条经过所有节点一次的最短路径吗？
Q2：对于一条包含所有节点的最短路径，除去节点、后剩下的节点组成的路径还是最短路径吗？

A1：在完全图上（即本题），度数不超过 2 且不成环的 Kruskal 贪心确实可以构造出一条路径，但不能保证这条路径最短。
例如，四个待连接节点的距离如下，满足三角不等式，且各条边权互不相同：

     A    B    C    D
A    0  681  598  589
B  681    0  949  973
C  598  949    0  707
D  589  973  707    0

贪心会依次选中 AD = 589、AC = 598。此时 A 的度已经为 2，边 AB = 681 被拒绝；CD = 707 会成环，也被拒绝。之后再选 BC = 949，得到路径 D-A-C-B，总长为 589 + 598 + 949 = 2136。

但路径 B-A-D-C 的总长只有 681 + 589 + 707 = 1977。因此，Kruskal 贪心虽然得到了一条合法路径，却没有得到最短路径。

A2：不一定。全局最优路径可能会选择一条中间部分本身不是最短，但更适合连接起点和终点的顺序。

例如，节点 0 和 4 是起点、终点，中间节点为 1、2、3：

     0   1   2   3   4
0    0  30  14   2  27
1   30   0  36  28  32
2   14  36   0  12  41
3    2  28  12   0  29
4   27  32  41  29   0

该矩阵满足三角不等式。中间节点的最短 Hamilton 路径是 1-3-2（或反向 2-3-1），长度为 28 + 12 = 40。但全局最短路径是：

0-3-2-1-4

总长为 2 + 12 + 36 + 32 = 82，其中间部分 3-2-1 的长度为 12 + 36 = 48，并不是中间节点的最短路径。若先选最短中间路径，再选择更合适的方向连接两端，最短也要 0-2-3-1-4，长度为 14 + 12 + 28 + 32 = 86，仍大于 82。

嗯，所以贪心 Kruskal 这个思路不对，再想想其他办法，不过看起来抓住题目的特殊信息确实可以带来一些思考。

DP(TLE)

在上一节，我们因为始末点固定而考虑了先得到中间节点的路径后再加上始末点，这是一个将规模位 n 的问题缩小为规模为 n - 2 的问题。很自然让人想到递推、DP。

从编号为的节点开始思考，它的下一个节点会是？或者说：对于已有的以编号为结尾的已确认最终将构成最短路径的并且起点为的路径，当前节点能否加入？

在 DFS 过程中我们使用了 st 来标记某节点是否已经被访问过。根据上面的思路，我们先考虑起点和终点对应的 st：

当时，
当时，
看来可以找到初始条件和最终结果，比如：

其中 e 是指以编号为 e 的节点做为最短路径的结尾节点；st 是指访问了的节点的状态

那么初始条件即，
DP 运行完后输出答案为

很完美对吧，初始条件和最后答案都很好输出，不过 st 数组需要开多大呢？
st 取值范围在 [0, (1 << n) - 1]，题目条件，即最大需要即左右的规模，而 e （数组的第一维）的取值在 [0, n]，那么 dp 数组的规模会是，即的规模，int 是 4Byte 即占用 83886000B 内存，即，题目限制为没有问题，不过需要注意的是，如果还是取 25 的话，数组将占用，程序将 MLE。

嗯，一切顺利，现在推导一下状态转移方程吧：
记表示从节点到节点的边权。对于当前节点, 前缀节点，对于当前节点有两种取法：

将该点加入路径
不将该点加入路径
那么定义为路径中包含前缀节点的状态，可列出如下状态转移方程：

令表示：从出发，恰好访问了中的节点，并以结尾的最短路径长度:

初始状态：
完整路径的状态：

$，$

其中「不将该点加入路径」即，不需要显示表示。

接下来进行时间复杂度的分析：
对于长度为 n 的目标路径，已知起始点，那么从路径上的第二个节点开始迭代，迭代到点，会迭代次即。对于每个虚拟节点，有种取法,所以这层循环为，对于这种取法，有前缀节点个，所以枚举前缀节点的时间复杂度为，最后，枚举的时间复杂度为，即 DP 的时间复杂度为，又，即 8388608000，是的规模，一定会 TLE 的（一般在即 1e8 的规模以下才能通过）：

#include <iostream>
#include <cstring>

const int N = 21;

int n, g[N][N];
int dp[N][1 << N];

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            std::cin >> g[i][j];

    std::memset(dp, 0x3f, sizeof dp);

    dp[0][1 << 0] = 0;
    for(int c = 0; c < n - 1; ++c) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                for(int st = 0; st < 1 << n; ++st) {
                    if(!(st & (1 << i)) && (st & (1 << j))) {
                        dp[i][st + (1 << i)] = std::min(dp[i][st + (1 << i)], dp[j][st] + g[j][i]);
                    }
                }
            }
        }
    }

    std::cout << dp[n - 1][(1 << n) - 1];
}

Solve

上一节的代码里，枚举和节点的循环是不可能被优化掉的（就像处理字符串的算法的最优时间复杂度一定是一样，数据本身一定会被遍历一遍）。而我们的 c 循环（在虚拟的最短 Hamilton 链路上进行虚拟节点遍历），c 没有记录在 DP 状态里，它只是让某一轮较晚才更新出的状态，之后还有机会继续扩展。但是，st 本身就代表了已经过的节点，若 st 中有个，那么当前一定在判断第个虚拟节点是否是，换句话说， c 循环是不必要的，因为 st 已经包含了这个信息。

那么，如何去掉 c 循环呢？

每次合法转移都会让 st 数值严格增大。因为不在 st 中，它对应的位原本为，加入后有：

所以把 st 按数值从小到大枚举，就是按状态转移的拓扑序处理：任意一个状态的前驱 st 状态都比它小，轮到该状态时，前驱已经处理完；从它扩展出的新状态则留在后面处理。这样一遍扫描就能完成所有转移，不需要再用 c 重复推进。

因此状态转移方程为：

令表示边的权值，表示从出发、恰好访问集合 st 中的节点并以结尾的最短路径长度：

初始状态：
对于、：

答案：

之前的循环规模是；按上述顺序，每个 st 只处理一次，枚举结尾节点和待加入节点，时间复杂度降为，空间复杂度仍为：

#include <iostream>
#include <cstring>

const int N = 21;

int n, g[N][N];
int dp[N][1 << N];

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            std::cin >> g[i][j];

    std::memset(dp, 0x3f, sizeof dp);

    dp[0][1 << 0] = 0;

    for(int st = 0; st < 1 << n; ++st) {
        for(int j = 0; j < n; ++j) {
            if(st & 1 << j) {
                for(int i = 0; i < n; ++i) {
                    if(!(st & (1 << i))) {
                        dp[i][st | (1 << i)] = std::min(dp[i][st | (1 << i)], dp[j][st] + g[j][i]);
                    }
                }
            }
        }
    }

    std::cout << dp[n - 1][(1 << n) - 1];
}

Template

template <class T>
T hamilton(int n, const T g[][N]) {
    const T INF = std::numeric_limits<T>::max() / 4;
    const int limit = 1 << n;

    std::vector<std::vector<T>> dp(n, std::vector<T>(limit, INF));
    dp[0][1] = T{};

    for (int st = 0; st < limit; ++st) {
        if (!(st & 1)) continue;

        for (int j = 0; j < n; ++j) {
            if (!(st & (1 << j))) continue;
            if (dp[j][st] == INF) continue;

            for (int i = 0; i < n; ++i) {
                if (st & (1 << i)) continue;

                const int next = st | (1 << i);
                dp[i][next] =
                    std::min(dp[i][next], dp[j][st] + g[j][i]);
            }
        }
    }

    return dp[n - 1][limit - 1];
}

时间复杂度：；空间复杂度：

Ref

Nowcoder 最短Hamilton路径
 Acwing 最短Hamilton路径

Loading...