【图论搜索专题】结合状态压缩的 BFS（含启发式搜索）
【图论搜索专题】结合状态压缩的 BFS（含启发式搜索）
题目描述
这是 LeetCode 上的「847. 访问所有节点的最短路径」，难度为「困难」。
Tag : 「图」、「图论 BFS」、「动态规划」、「状态压缩」
存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 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]
提示：
- n == graph.length
- 1 <= n <= 12
- 0 <= graph[i].length < n
- graph[i] 不包含 i
- 如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
- 输入的图总是连通图
基本分析
为了方便，令点的数量为 n ，边的数量为 m 。
这是一个等权无向图，题目要我们求从「一个点都没访问过」到「所有点都被访问」的最短路径。
同时 n 只有 12 ，容易想到使用「状态压缩」来代表「当前点的访问状态」：使用二进制表示长度为 32 的 int 的低 12 来代指点是否被访问过。
我们可以通过一个具体的样例，来感受下「状态压缩」是什么意思：
例如 (000...0101)_2 代表编号为 0 和编号为 2 的节点已经被访问过，而编号为 1 的节点尚未被访问。
然后再来看看使用「状态压缩」的话，一些基本的操作该如何进行：
假设变量 state 存放了「当前点的访问状态」，当我们需要检查编号为 x 的点是否被访问过时，可以使用位运算 a = (state >> x) & 1，来获取 state 中第 x 位的二进制表示，如果 a 为 1 代表编号为 x 的节点已被访问，如果为 0 则未被访问。
同理，当我们需要将标记编号为 x 的节点已经被访问的话，可以使用位运算 state | (1 << x) 来实现标记。
状态压缩 + BFS
因为是等权图，求从某个状态到另一状态的最短路，容易想到 BFS。
同时我们需要知道下一步能往哪些点进行移动，因此除了记录当前的点访问状态 state 以外，还需要记录最后一步是在哪个点 u ，因此我们需要使用二元组进行记录 (state, u) ，同时使用dist 来记录到达 (state, u) 使用的步长是多少。
❝一些细节：由于点的数量较少，使用「邻接表」或者「邻接矩阵」来存图都可以。对于本题，由于已经给出了 graph 数组，因此可以直接充当「邻接表」来使用，而无须做额外的存图操作。 ❞
代码：
class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// 初始化所有的 (state, u) 距离为正无穷
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) Arrays.fill(dist[i], INF);
// 因为可以从任意起点出发，先将起始的起点状态入队，并设起点距离为 0
Deque<int[]> d = new ArrayDeque<>(); // state, u
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
d.addLast(new int[]{1 << i, i});
}
// BFS 过程，如果从点 u 能够到达点 i，则更新距离并进行入队
while (!d.isEmpty()) {
int[] poll = d.pollFirst();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : graph[u]) {
if (dist[state | (1 << i)][i] == INF) {
dist[state | (1 << i)][i] = step + 1;
d.addLast(new int[]{state | (1 << i), i});
}
}
}
return -1; // never
}
}
- 时间复杂度：点（状态）数量为 n * 2^n ，边的数量为 n^2 * 2^n ，
BFS复杂度上界为点数加边数，整体复杂度为O(n^2 * 2^n) - 空间复杂度：O(n * 2^n)
Floyd + 状压 DP
其实在上述方法中，我们已经使用了与 DP 状态定义分析很像的思路了。甚至我们的元祖设计 (state, u) 也很像状态定义的两个维度。
那么为什么我们不使用 f[state][u] 为从「没有点被访问过」到「访问过的点状态为 state 」，并最后一步落在点 u 的状态定义，然后跑一遍 DP 来做呢？
是因为如果从「常规的 DP 转移思路」出发，状态之间不存在拓扑序（有环），这就导致了我们在计算某个 f[state][u] 时，它所依赖的状态并不确保已经被计算/更新完成，所以我们无法使用常规的 DP 手段来求解。
❝这里说的常规 DP 手段是指：枚举所有与 u 相连的节点 v ，用 f[state'][v] 来更新 f[state][u] 的转移方式。❞
常规的 DP 转移方式状态间不存在拓扑序，我们需要换一个思路进行转移。
对于某个 state 而言，我们可以枚举其最后一个点 i 是哪一个，充当其达到 state 的最后一步，然后再枚举下一个点 j 是哪一个，充当移动的下一步（当然前提是满足 state 的第 i 位为 1 ，而第 j 位为 0 ）。
求解任意两点最短路径，可以使用 Floyd 算法，复杂度为 O(n^3) 。
代码：
class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// Floyd 求两点的最短路径
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
for (int i = 0; i < n; i++) {
for (int j : graph[i]) dist[i][j] = 1;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// DP 过程，如果从 i 能够到 j 的话，使用 i 到 j 的最短距离（步长）来转移
int[][] f = new int[mask][n];
// 起始时，让所有状态的最短距离（步长）为正无穷
for (int i = 0; i < mask; i++) Arrays.fill(f[i], INF);
// 由于可以将任意点作为起点出发，可以将这些起点的最短距离（步长）设置为 0
for (int i = 0; i < n; i++) f[1 << i][i] = 0;
// 枚举所有的 state
for (int state = 0; state < mask; state++) {
// 枚举 state 中已经被访问过的点
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 0) continue;
// 枚举 state 中尚未被访问过的点
for (int j = 0; j < n; j++) {
if (((state >> j) & 1) == 1) continue;
f[state | (1 << j)][j] = Math.min(f[state | (1 << j)][j], f[state][i] + dist[i][j]);
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) ans = Math.min(ans, f[mask - 1][i]);
return ans;
}
}
- 时间复杂度：Floyd 复杂度为 O(n^3) ；DP 共有 n * 2^n 个状态需要被转移，每次转移复杂度为 O(n) ，总的复杂度为 O(n^2 * 2^n) 。整体复杂度为O(\max(n^3, n^2 * 2^n))
- 空间复杂度：O(n * 2^n)
AStar
显然，从 state 到 state' 的「理论最小修改成本」为两者二进制表示中不同位数的个数。
同时，当且仅当在 state 中 1 的位置与state' 中 0 存在边，才有可能取到这个「理论最小修改成本」。
因此直接使用当前状态 state 与最终目标状态 1 << n 两者二进制表示中不同位数的个数作为启发预估值是合适的。
代码：
class Solution {
int INF = 0x3f3f3f3f;
int n;
int f(int state) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 0) ans++;
}
return ans;
}
public int shortestPathLength(int[][] g) {
n = g.length;
int mask = 1 << n;
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]); // state, u, val
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
q.add(new int[]{1<< i, i, f(i << 1)});
}
while (!q.isEmpty()) {
int[] poll = q.poll();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : g[u]) {
int nState = state | (1 << i);
if (dist[nState][i] > step + 1) {
dist[nState][i] = step + 1;
q.add(new int[]{nState, i, step + 1 + f(nState)});
}
}
}
return -1; // never
}
}
最后
这是我们「刷穿 LeetCode」系列文章的第 No.847 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
