【图论搜索专题】灵活运用多种搜索方式进行求解（含启发式搜索）
【图论搜索专题】灵活运用多种搜索方式进行求解（含启发式搜索）
题目描述
这是 LeetCode 上的「752. 打开转盘锁」，难度为「中等」。
Tag : 「双向 BFS」、「启发式搜索」、「AStar 算法」、「IDAStar 算法」
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 仅由若干位数字组成
基本分析
首先，我建议你先做 127. 单词接龙，然后再回过头将本题作为「练习题」。
127. 单词接龙 定位困难，而本题定位中等。主要体现在数据范围上，思维难度上 127. 单词接龙 并不比本题难，大胆做。
回到本题，根据题意，可以确定这是一个「最短路/最小步数」问题。
此类问题，通常我们会使用「BFS」求解，但朴素的 BFS 通常会带来搜索空间爆炸问题。
因此我们可以使用与 127. 单词接龙 类似的思路进行求解。
双向 BFS
我们知道，递归树的展开形式是一棵多阶树。
使用朴素 BFS 进行求解时，队列中最多会存在“两层”的搜索节点。
因此搜索空间的上界取决于 目标节点所在的搜索层次的深度所对应的宽度。
下图展示了朴素 BFS 可能面临的搜索空间爆炸问题：
在朴素的 BFS 实现中，空间的瓶颈主要取决于搜索空间中的最大宽度。
那么有没有办法让我们不使用这么宽的搜索空间，同时又能保证搜索到目标结果呢？
「双向 BFS」 可以很好的解决这个问题：
同时从两个方向开始搜索，一旦搜索到相同的值，意味着找到了一条联通起点和终点的最短路径。
对于「有解」、「有一定数据范围」同时「层级节点数量以倍数或者指数级别增长」的情况，「双向 BFS」的搜索空间通常只有「朴素 BFS」的空间消耗的几百分之一，甚至几千分之一。
「双向 BFS」的基本实现思路如下：
- 创建「两个队列」分别用于两个方向的搜索；
- 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
- 为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
- 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
「双向 BFS」基本思路对应的伪代码大致如下：
d1、d2 为两个方向的队列
m1、m2 为两个方向的哈希表，记录每个节点距离起点的
// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else {
update(d2, m2, m1);
}
}
// update 为从队列 d 中取出一个元素进行「一次完整扩展」的逻辑
void update(Deque d, Map cur, Map other) {}
回到本题，我们看看如何使用「双向 BFS」进行求解。
估计不少同学是第一次接触「双向 BFS」，因此这次我写了大量注释。
建议大家带着对「双向 BFS」的基本理解去阅读。
代码：
class Solution {
String t, s;
Set<String> set = new HashSet<>();
public int openLock(String[] _ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : _ds) set.add(d);
if (set.contains(s)) return -1;
int ans = bfs();
return ans;
}
int bfs() {
// d1 代表从起点 s 开始搜索（正向）
// d2 代表从结尾 t 开始搜索（反向）
Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
/*
* m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来
* e.g
* m1 = {"1000":1} 代表 "1000" 由 s="0000" 替换 1 次字符而来
* m2 = {"9999":3} 代表 "9999" 由 t="9996" 替换 3 次字符而来
*/
Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
d1.addLast(s);
m1.put(s, 0);
d2.addLast(t);
m2.put(t, 0);
/*
* 只有两个队列都不空，才有必要继续往下搜索
* 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
* e.g.
* 例如，如果 d1 为空了，说明从 s 搜索到底都搜索不到 t，反向搜索也没必要进行了
*/
while (!d1.isEmpty() && !d2.isEmpty()) {
int t = -1;
if (d1.size() <= d2.size()) {
t = update(d1, m1, m2);
} else {
t = update(d2, m2, m1);
}
if (t != -1) return t;
}
return -1;
}
int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
String poll = deque.pollFirst();
char[] pcs = poll.toCharArray();
int step = cur.get(poll);
// 枚举替换哪个字符
for (int i = 0; i < 4; i++) {
// 能「正向转」也能「反向转」，这里直接枚举偏移量 [-1,1] 然后跳过 0
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
// 求得替换字符串 str
int origin = pcs[i] - '0';
int next = (origin + j) % 10;
if (next == -1) next = 9;
char[] clone = pcs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
if (cur.containsKey(str)) continue;
// 如果在「另一方向」找到过，说明找到了最短路，否则加入队列
if (other.containsKey(str)) {
return step + 1 + other.get(str);
} else {
deque.addLast(str);
cur.put(str, step + 1);
}
}
}
return -1;
}
}
AStar 算法
可以直接根据本题规则来设计 A* 的「启发式函数」。
比如对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：不同字符的转换成本之和。
需要注意的是：由于我们衡量某个字符 str 的估值是以目标字符串 target 为基准，因此我们只能确保 target 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。
这一点十分关键，在代码层面上体现在 map.get(str).step > poll.step + 1 的判断上。
注意：本题用 A* 过了，但通常我们需要先「确保有解」，A* 的启发搜索才会发挥真正价值。而本题，除非 t 本身在 deadends 中，其余情况我们无法很好提前判断「是否有解」。对于无解的情况 A* 效果不如「双向 BFS」。
代码：
class Solution {
class Node {
String str;
int val, step;
/**
* str : 对应字符串
* val : 估值（与目标字符串 target 的最小转换成本）
* step: 对应字符串是经过多少步转换而来
*/
Node(String _str, int _val, int _step) {
str = _str;
val = _val;
step = _step;
}
}
int f(String str) {
int ans = 0;
for (int i = 0; i < 4; i++) {
int cur = str.charAt(i) - '0', target = t.charAt(i) - '0';
int a = Math.min(cur, target), b = Math.max(cur, target);
// 在「正向转」和「反向转」之间取 min
int min = Math.min(b - a, a + 10 - b);
ans += min;
}
return ans;
}
String s, t;
Set<String> set = new HashSet<>();
public int openLock(String[] ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : ds) set.add(d);
if (set.contains(s)) return -1;
PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
Map<String, Node> map = new HashMap<>();
Node root = new Node(s, f(s), 0);
q.add(root);
map.put(s, root);
while (!q.isEmpty()) {
Node poll = q.poll();
char[] pcs = poll.str.toCharArray();
int step = poll.step;
if (poll.str.equals(t)) return step;
for (int i = 0; i < 4; i++) {
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
int cur = pcs[i] - '0';
int next = (cur + j) % 10;
if (next == -1) next = 9;
char[] clone = pcs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
// 如果 str 还没搜索过，或者 str 的「最短距离」被更新，则入队
if (!map.containsKey(str) || map.get(str).step > step + 1) {
Node node = new Node(str, step + 1 + f(str), step + 1);
map.put(str, node);
q.add(node);
}
}
}
}
return -1;
}
}
IDA* 算法
同样我们可以使用基于 DFS 的启发式 IDA* 算法：
- 仍然使用
f()作为估值函数 - 利用旋转次数有限：总旋转次数不会超过某个阈值 \max 。
- 利用「迭代加深」的思路找到最短距离理想情况下，由于存在正向旋转和反向旋转，每一位转轮从任意数字开始到达任意数字，消耗次数不会超过 5 次，因此理想情况下可以设定 \max = 5 * 4 。但考虑
deadends的存在，我们需要将 \max 定义得更加保守一些：\max = 10 * 4 。
但这样的阈值设定，加上 IDA* 算法每次会重复遍历「距离小于与目标节点距离」的所有节点，会有很大的 TLE 风险。
因此我们需要使用动态阈值：不再使用固定的阈值，而是利用 target 计算出「最大的转移成本」作为我们的「最深数量级」。
PS. 上述的阈值分析是科学做法。对于本题可以利用数据弱，直接使用 \max = 5 * 4 也可以通过，并且效果不错。但必须清楚 \max = 5 * 4 可能是一个错误的阈值，本题起点为 0000，考虑将所有正向转换的状态都放入 deadends 中，target 为 2222。这时候我们可以只限定 0000 先变为 9999 再往回变为 2222 的通路不在 deadends 中。这时候使用 \max = 5 * 4 就不对，但本题数据弱，可以通过。
代码：
class Solution {
String s, t;
String cur;
Set<String> set = new HashSet<>();
Map<String, Integer> map = new HashMap<>();
public int openLock(String[] ds, String _t) {
s = "0000";
t = _t;
if (s.equals(t)) return 0;
for (String d : ds) set.add(d);
if (set.contains(s)) return -1;
int depth = 0, max = getMax();
cur = s;
map.put(cur, 0);
while (depth <= max && !dfs(0, depth)) {
map.clear();
cur = s;
map.put(cur, 0);
depth++;
}
return depth > max ? -1 : depth;
}
int getMax() {
int ans = 0;
for (int i = 0; i < 4; i++) {
int origin = s.charAt(i) - '0', next = t.charAt(i) - '0';
int a = Math.min(origin, next), b = Math.max(origin, next);
int max = Math.max(b - a, a + 10 - b);
ans += max;
}
return ans;
}
int f() {
int ans = 0;
for (int i = 0; i < 4; i++) {
int origin = cur.charAt(i) - '0', next = t.charAt(i) - '0';
int a = Math.min(origin, next), b = Math.max(origin, next);
int min = Math.min(b - a, a + 10 - b);
ans += min;
}
return ans;
}
boolean dfs(int u, int max) {
if (u + f() > max) return false;
if (f() == 0) return true;
String backup = cur;
char[] cs = cur.toCharArray();
for (int i = 0; i < 4; i++) {
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
int origin = cs[i] - '0';
int next = (origin + j) % 10;
if (next == -1) next = 9;
char[] clone = cs.clone();
clone[i] = (char)(next + '0');
String str = String.valueOf(clone);
if (set.contains(str)) continue;
if (!map.containsKey(str) || map.get(str) > u + 1) {
cur = str;
map.put(str, u + 1);
if (dfs(u + 1, max)) return true;
cur = backup;
}
}
}
return false;
}
}
最后
这是我们「刷穿 LeetCode」系列文章的第 No.752 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
