算法图算法

哈密顿路径

字数统计: 3.6k字   |   阅读时长: 17分
, , ,

摘要: 本文介绍哈密顿路径的背景、算法、代码模板和例题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

哈密顿(1805-1865)

哈密顿是 19 世纪数学家、物理学家。哈密顿在数学方面主要研究代数，比如我们可能都知道线性代数里的哈密顿凯莱定理：

哈密顿凯莱定理：
设 $\mathbf{A}$ 是数域 $P$ 上的 $n$ 阶矩阵，$\mathbf{A}$ 的特征多项式为：

则：

哈密顿在数学上最重要的贡献是在 1843 年发现了四元数。把他与图论联系在一起的是他提出的一个趣味问题：从正十二面体（共有20个顶点）的一个顶点出发，沿着边行进，把 20 个顶点无遗漏地全部通过，每一顶点只许过一次而回到原处。问这种走法是否存在。

将这一问题略加转化，哈密顿于1857年发明了著名的周游世界游戏。游戏的道具由一个木制的正十二面体构成，正十二面体的每个棱角上标有一个当时非常有名的城市。游戏目的是环绕世界旅行，其要求是寻找一个环游路线，使得：沿正十二面体的棱，从一个“城市”出发，经过每个城市恰好一次，最后回到原出发点，并且经过的棱不许重复。

下图给出了这个游戏的一种正确走法：

对照一下欧拉与哈密顿研究的问题。欧拉要求在一个图中寻找满足“从一个顶点出发，沿边行进，无遗漏走遍所有的边，每一边只许经过一次回到出发点”的路线，这样的路线后来在图论中被称为欧拉回路。而具有欧拉回路的图称为欧拉图。哈密顿问题则要求在一个图中寻找满足“从一个顶点出发，沿边行进，无遗漏地通过全部顶点，每一顶点只许过一次而回到出发点”的路线，这样的路线后来在图论中被称为哈密顿圈。欧拉问题与哈密顿问题表面相似，实际完全不同，参考文章 图论4-欧拉图,哈密顿图。

欧拉七桥问题与哈密顿周游世界游戏埋下了图论诞生的种子，并在 20 世纪迅速发展，成为现在重要的数学分支。对欧拉问题，我们已经有了简单、漂亮的结果：一个连通图存在欧拉回路当且仅当它的所有顶点都是偶顶点。然而对哈密顿问题即“一个给定的连通图是否存在哈密顿回路”，至今仍然是图论中一个尚未解决的著名难题。

对于节点数较少的图，我们可以用状态压缩 DP 解决哈密顿路径相关的问题。本文我们通过一个模板题与三个例题来看一下哈密顿路径问题的算法与应用。

模板题: 91. 最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。
对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

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

数据范围
1<=n<=20
0<=a[i,j]<=1e7

输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18

算法: 状态压缩DP

1
2
3
4
5
6
7
8
9
10
11
状态定义
dp[s][v] := 当前在 v 点，已经过的点集合为 s，从 0 到达 v 的最短路径

初始化
dp[1][0] = 0, (当前在 0 点，已经过的点集合只有 0)

答案
dp[(1 << n) - 1][n - 1]

状态转移
dp[s][v] = min(dp[s ^ (1 << v)][u] + a[u][v]) for u in s

代码(C++)

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
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            cin >> a[i][j];
        }
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));
    dp[1][0] = 0;
    for(int s = 2; s < (1 << n); ++s)
    {
        for(int v = 0; v < n; ++v)
        {
            if((s >> v & 1) == 0)
                continue;
            for(int u = 0; u < n; ++u)
            {
                if(u == v)
                    continue;
                if((s >> u & 1) == 0)
                    continue;
                dp[s][v] = min(dp[s][v], dp[s ^ (1 << v)][u] + a[u][v]);
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1] << endl;;
}

847. 访问所有节点的最短路径

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

提示：

1
2
3
4
5
6
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] 不包含 i
如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
输入的图总是连通图

示例 1：
输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

示例 2：
输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]

算法：求最短哈密顿路

Floyd + 状态压缩DP：

1
2
3
4
5
6
7
Floyd 求出 d[i][j]

dp[s][i] := 经过了 s 中的点，当前位置在 i 的最短路
枚举 s 中的点 i，枚举不在 s 中的点 j：
dp[s|(1 << j)][j] = min(dp[s][i] + d[i][j])

答案：使得 dp[(1 << n) - 1][i] 最小

代码(C++)

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
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int N = graph.size();
        vector<vector<int> > d(N, vector<int>(N, INT_MAX / 2));
        for(int i = 0; i < N; ++i)
            for(int j: graph[i])
            {
                d[i][j] = 1;
                d[j][i] = 1;
            }
        for(int k = 0; k < N; ++k)
            for(int i = 0; i < N; ++i)
                for(int j = 0; j < N; ++j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        int all_state = (1 << N) - 1;
        vector<vector<int> > dp(all_state + 1, vector<int>(N, INT_MAX / 2));
        for(int i = 0; i < N; ++i)
            dp[(1 << i)][i] = 0;
        for(int state = 0; state < (1 << N); ++state)
        {
            for(int j = 0; j < N; ++j)
            {
                if(state & (1 << j)) continue;
                for(int i = 0; i < N; ++i)
                {
                    if(!(state & (1 << i))) continue;
                    // i 在 state 中，j 不在 state 中
                    dp[state|(1 << j)][j] = min(dp[state|(1 << j)][j], dp[state][i] + d[i][j]);
                }
            }
        }

        int result = INT_MAX;
        for(int i = 0; i < N; ++i)
            result = min(result, dp[(1 << N) - 1][i]);

        return result;
    }

};

943. 最短超级串

给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。

我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。

示例 1：
输入：words = [“alex”,”loves”,”leetcode”]
输出：”alexlovesleetcode”
解释：”alex”，”loves”，”leetcode” 的所有排列都会被接受。

示例 2：
输入：words = [“catg”,”ctaagt”,”gcta”,”ttca”,”atgcatc”]
输出：”gctaagttcatgcatc”

提示：

1
2
3
4
1 <= words.length <= 12
1 <= words[i].length <= 20
words[i] 由小写英文字母组成
words 中的所有字符串 互不相同

算法：状态压缩DP + DP过程记录路径

最终字符串 = 起点串 + 中间串 + 终点串 -> 哈密顿路问题。

先预处理出 adj[i][j] := A[i]A[j]的最短长度。

1
2
3
4
dp[state][i] := 已选 state 中的串，当前在 i，的重复部分长度

枚举不在 state 中的 j, adj[i][j] 为重复部分
dp[state | (1 << j)][j] = max(dp[state[i]] + adj[i][j])

在动态规划中保存路径，在记录 dp[state | (1 << j)][j] = dp[state][i] + adj[i][j]; 的同时记录 path[state | (1 << j)][j] = i;。

代码 (C++)

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        // n [1, 12]
        int n = A.size();
        vector<vector<int> > adj(n, vector<int>(n, 0)); // A[i] 后缀和 A[j] 前缀的重合长度
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
            {
                if(i == j)
                    continue;
                adj[i][j] = _process(A[i], A[j]);
            }
        vector<vector<int> > dp((1 << n), vector<int>(n, 0));
        vector<vector<int> > path((1 << n), vector<int>(n, -1));
        for(int state = 0; state < (1 << n); ++state)
        {
            // dp[state|(1<<j)][j] = max{dp[state][i] + adj[i][j]}
            // 已选 state, 当前在 j 的最长 overlap
            for(int j = 0; j < n; ++j)
            {
                if((1 << j) & state) continue;
                for(int i = 0; i < n; ++i)
                {
                    if(!(state & (1 << i))) continue;
                    if(dp[state | (1 << j)][j] <= dp[state][i] + adj[i][j])
                    {
                        dp[state | (1 << j)][j] = dp[state][i] + adj[i][j];
                        path[state | (1 << j)][j] = i;
                    }
                }
            }
        }
        int max_overlap = 0;
        int tail_idx = 0;
        for(int i = 0; i < n; ++i)
        {
            if(max_overlap < dp[(1 << n) - 1][i])
            {
                max_overlap = dp[(1 << n) - 1][i];
                tail_idx = i;
            }
        }
        vector<int> result_idxs;
        int idx = tail_idx;
        int s = (1 << n) - 1;
        while(idx != -1)
        {
            result_idxs.push_back(idx);
            int new_idx = path[s][idx];
            s &= (~(1 << idx));
            idx = new_idx;
        }
        reverse(result_idxs.begin(), result_idxs.end());

        int prev_idx = result_idxs[0];
        string result = A[prev_idx];
        for(int i = 1; i < n; ++i)
        {
            int cur_idx = result_idxs[i];
            int overlap = adj[prev_idx][cur_idx];
            result += A[cur_idx].substr(overlap);
            prev_idx = cur_idx;
        }
        return result;

    }

private:
    int _process(const string& s1, const string& s2)
    {
        int n1 = s1.size();
        int n2 = s2.size();
        int result = 0;
        for(int len = 1; len <= min(n1, n2); ++len)
        {
            // if(s2.substr(0, len) == s1.substr(n1 - len, len))
            //     result = len;
            int i2 = 0, i1 = n1 - len;
            while(i2 < len)
            {
                if(s1[i1] != s2[i2])
                    break;
                ++i1;
                ++i2;
            }
            if(i2 == len)
                result = len;
        }
        return result;
    }
};

980. 不同路径 III

在二维网格 grid 上，有 4 种类型的方格：

  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格，且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

提示：

1
1 <= grid.length * grid[0].length <= 20

示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：

  1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
  2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径：

  1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
  2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
  3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
  4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

示例 3：
输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

算法：状态压缩DP+记忆化

类似旅行商问题(每个点只能经过一次)，但不用回到起点。

1
2
dp[end_i][end_j][end_state]
dp[i][j][state] := 位于 i, j，已经经过过 state，的到达 end 的路径数目

代码(C++)

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int start_i = -1, start_j = -1;
        int end_i = -1, end_j = -1;
        int end_state = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] == 1)
                {
                    start_i = i;
                    start_j = j;
                }
                if(grid[i][j] == 2)
                {
                    end_i = i;
                    end_j = j;
                }
                if(grid[i][j] == 0)
                    end_state |= (1 << (_ij2idx(i, j, m)));
            }
        // dp[end_i][end_j][end_state]
        // dp[i][j][state] := 位于 i, j，已经经过过 state，的到达 end 的路径数目
        vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(end_state + 1, -2)));
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        visited[end_i][end_j] = true;
        solve(grid, end_i, end_j, end_state, dp, visited);
        return dp[end_i][end_j][end_state];
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int _ij2idx(int i, int j, int m)
    {
        return i * m + j;
    }

    void solve(const vector<vector<int> >& grid, int i, int j, int state, vector<vector<vector<int> > >& dp, vector<vector<bool>>& visited)
    {
        int n = grid.size(), m = grid[0].size();
        if(dp[i][j][state] != -2)
            return;

        if(grid[i][j] == 1 && state == 0)
        {
            dp[i][j][state] = 1;
            return;
        }
        if(grid[i][j] == 1 || (grid[i][j] == 0 && state == 0))
        {
            dp[i][j][state] = 0;
            return;
        }

        dp[i][j][state] = 0;
        int prev_state = state;
        if(grid[i][j] == 0)
            prev_state &= (~(1 << (_ij2idx(i, j, m))));
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d], y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(grid[x][y] == -1) continue;
            if(visited[x][y]) continue;
            visited[x][y] = true;
            solve(grid, x, y, prev_state, dp, visited);
            if(dp[x][y][prev_state] != -1)
                dp[i][j][state] += dp[x][y][prev_state];
            visited[x][y] = false;
        }
    }
};
Share