教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以「刷穿 LeetCode」系列第 752 题《打开转盘锁》为核心系统讲解「最短路/最小步数」类问题的三种经典求解方案双向 BFS、A* 算法与IDA* 算法。通过本题的完整代码与逐行注释读者可以掌握搜索空间爆炸的成因与对策、启发式函数的设计方法以及迭代加深与动态阈值剪枝的组合技巧并将其迁移到仓库中 127. 单词接龙、433. 最小基因变化、773. 滑动谜题等同类题目上。本题题解位于 LeetCode/751-760/752. 打开转盘锁中等.md并同时被收录于 Index/图论 双向 BFS.md 与 Index/启发式搜索.md 两个 Tag 索引中属于「双向 BFS」与「启发式搜索」两大专题的交叉例题。题目描述与问题建模你有一个带有四个圆形拨轮的转盘锁每个拨轮都有 10 个数字0到9。每个拨轮可以自由旋转例如把9变为00变为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 500deadends[i].length 4target.length 4target不在deadends之中target和deadends[i]仅由若干位数字组成从建模角度看本题是一个典型的「最短路 / 最小步数」问题状态空间0000到9999共10^4 10000个状态节点转移关系每个状态固定有 8 个邻居4 个拨轮 × 正向/反向两种旋转障碍物deadends中的状态不可进入目标从s 0000到t target的最少旋转次数不可达返回-1。基本分析朴素 BFS 的搜索空间爆炸问题此类「最小步数」问题通常我们会使用BFS广度优先搜索求解但朴素的 BFS 往往会带来搜索空间爆炸的问题。我们知道递归树的展开形式是一棵多阶树。使用朴素 BFS 进行求解时队列中最多会同时存在两层的搜索节点因此搜索空间的上界取决于目标节点所在的搜索层次深度所对应的宽度。以本题为例起点0000的 8 个邻居在第一层全部入队第二层每个节点又各自扩展出 8 个邻居去重后仍有大量新增随着层数加深队列宽度以指数级别增长。在朴素的 BFS 实现中空间的瓶颈主要取决于搜索空间中的最大宽度。层数越深宽度爆炸越严重这就是朴素 BFS 在大状态空间下不可行的根本原因。仓库中的 127. 单词接龙 题解对这一点有更直观的量化对于一个长度为 10 的beginWord替换一次字符可以产生10 × 25个新单词第一层就产生 250 个单词第二层超过 6×10⁴ 个……「随着层数的加深这个数字的增速越快」。本题题解同样指出127. 单词接龙定位困难而本题定位中等主要体现在数据范围上思维难度上 127 并不比本题难因此官方推荐的练习路线是先做 127. 单词接龙再回过头把本题作为练习题。既然朴素 BFS 空间扛不住那么有没有办法让我们不使用这么宽的搜索空间同时又能保证搜索到目标结果呢答案是「双向 BFS」以及更进一步的「A* / IDA* 启发式搜索」。解法一双向 BFS原理从两个方向同时逼近「双向 BFS」可以很好地解决搜索空间爆炸问题同时从两个方向开始搜索一旦搜索到相同的值意味着找到了一条联通起点和终点的最短路径。它的核心收益在于空间消耗的指数级下降若单向 BFS 的搜索深度为d、每层宽度基数为b总搜索节点量级约为b^d而双向 BFS 让两个方向各搜索约d/2层总量级约为2 × b^(d/2)。对于「有解」「有一定数据范围」同时「层级节点数量以倍数或者指数级别增长」的情况双向 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) {}完整 Java 实现带详细注释原题解为便于第一次接触「双向 BFS」的读者理解给出了带大量注释的实现class Solution { String t, s; SetString 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 开始搜索反向 DequeString d1 new ArrayDeque(), d2 new ArrayDeque(); /* * m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来 * e.g. * m1 {1000:1} 代表 1000 由 s0000 旋转 1 次而来 * m2 {9999:3} 代表 9999 由 t9996 旋转 3 次而来 */ MapString, 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(DequeString deque, MapString, Integer cur, MapString, Integer other) { int m deque.size(); while (m-- 0) { 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; } }关键实现细节拆解按层扩展update开头先记录int m deque.size()随后while (m-- 0)只扩展当前层的全部节点。这一步保证了两方向搜索的层数对齐是step 1 other.get(str)能正确拼出最短总步数的前提——相遇时正向走了step 1步反向已经走了other.get(str)步。相遇判定即答案当某个方向扩展出的新状态str出现在另一方向的哈希表other中时直接返回step 1 other.get(str)无需再继续扩展。旋转的枚举写法用j ∈ {-1, 0, 1}枚举「正向转一格 / 反向转一格」if (j 0) continue跳过原地不动。注意 Java 中(origin j) % 10在origin 0, j -1时结果为-1因此需要if (next -1) next 9手动回绕到9。死锁与去重set.contains(str)跳过deadends中的死亡数字cur.containsKey(str)防止当前方向重复扩展同一状态。两个方向各用独立的哈希表m1/m2记录步数避免互相污染。与 127. 单词接龙的双向 BFS 对照本题代码与仓库中 127. 单词接龙 的双向 BFS 实现同构同样是双队列d1/d2 双哈希表m1/m2同样在循环里比较d1.size() d2.size()选择扩展方向同样在update中发现other.containsKey(sub)时返回cur.get(poll) 1 other.get(sub)。两者差异只在于邻居生成规则127 题枚举替换原字符串的每个位置i再枚举 26 个小写字母j并校验新单词必须存在于wordSet752 题枚举 4 个拨轮位置i再枚举偏移量j -1 / 1并校验新状态不能命中deadends。把这两份代码并排阅读即可抽象出「双向 BFS」的通用模板面向具体问题的部分只有邻居生成与合法性校验框架部分双队列、双哈希表、小队列优先、相遇返回完全一致。该模板同样适用于 Index/图论 双向 BFS.md 索引中收录的 433. 最小基因变化、815. 公交路线、934. 最短的桥、1345. 跳跃游戏 IV、2059. 转化数字的最小运算数 等题目。解法二AStar 算法启发式函数的设计可以直接根据本题规则来设计 A* 的「启发式函数」。对于两个状态a和b可直接计算出「理论最小转换次数」不同字符的转换成本之和。由于每个拨轮可以从两个方向旋转某个位置上的数字从cur变到target的最小旋转次数是「正向距离」与「反向距离」的较小者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; }其中b - a是正向旋转的距离a 10 - b是绕过一圈即反向的距离。该启发式不会高估实际剩余代价每步只能旋转一个拨轮一格f是剩余步数的下界满足 A* 算法「可采纳admissible」的前提因此首次从优先队列中弹出target时得到的步数仍是最优解。一个必须注意的关键点由于我们衡量某个字符str的估值是以目标字符串target为基准因此我们只能确保target出队时为「距离最短」而不能确保中间节点出队时「距离最短」。因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队还要结合当前节点的「最小距离」是否被更新而决定是否入队。这一点十分关键在代码层面上体现在map.get(str).step poll.step 1的判断上——只有新路径的步数严格更少才更新该状态并重新入队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; SetString 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; PriorityQueueNode q new PriorityQueue((a,b)-a.val-b.val); MapString, 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; } }注意Node中val实际保存的是step 1 f(str)即f g h已走步数 启发式估值优先队列按val升序弹出从而始终优先扩展「当前已走步数 剩余预估步数」最小的状态。适用前提与局限本题用 A* 可以通过但通常我们需要先「确保有解」A* 的启发搜索才会发挥真正价值。而本题中除非t本身在deadends中其余情况我们无法很好提前判断「是否有解」。对于无解的情况A* 效果不如「双向 BFS」。原因在于A* 在无解时仍需遍历完整个可达状态空间而双向 BFS 一旦某个方向的队列被搜空即可提前判定无解并终止。因此实战选型时本题更推荐以双向 BFS 作为主解法A* 作为启发式思路的进阶学习。解法三IDAStar 算法从迭代加深到 IDA*同样可以使用基于DFS的启发式 IDA* 算法仍然使用f()作为估值函数利用旋转次数有限总旋转次数不会超过某个阈值max利用「迭代加深」的思路找到最短距离——不断增大深度上限max并重复 DFS首次搜索成功时的深度即为最短步数。理想情况下由于存在正向旋转和反向旋转每一位转轮从任意数字开始到达任意数字消耗次数不会超过 5 次因为绕 10 个刻度从两侧逼近最多半圈因此理想情况下可以设定max 5 * 4 20。但考虑deadends的存在可能需要绕远路避开死亡数字需要将max定义得更加保守一些max 10 * 4 40。静态阈值的问题TLE 风险但这样的阈值设定加上 IDA* 算法每次会重复遍历「距离小于目标节点距离」的所有节点会有很大的 TLE 风险。固定大阈值意味着每次失败的 DFS 都要在较深的层次上做大量重复搜索。动态阈值按 target 计算最大转移成本因此我们需要使用动态阈值不再使用固定的阈值而是利用target计算出「最大的转移成本」作为我们的「最深数量级」。getMax()逐位计算从起点到target的最大旋转成本正向距离与反向距离取max即最坏情况下需要的步数累加后作为本次搜索的深度上限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; }完整实现如下class Solution { String s, t; String cur; SetString set new HashSet(); MapString, 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; } }核心剪枝逻辑if (u f() max) return false—— 当前已走步数u加上剩余启发式估值f()一旦超过深度上限max就立即剪枝if (f() 0) return true—— 启发式估值为 0 说明已到达target。每次迭代加深失败后都要map.clear()并重置cur s为下一轮更深搜索重建状态。关于阈值设定的一处提醒上述的阈值分析是科学做法。对于本题可以利用数据弱直接使用max 5 * 4 20也可以通过并且效果不错。但必须清楚max 5 * 4可能是一个错误的阈值。例如本题起点为0000考虑将所有正向转换的状态都放入deadends中、target为2222这时候可以构造出只限定「0000先变为9999再往回变为2222」的通路不在deadends中的反例——该通路单轮旋转次数超过 5使用max 20就会得出错误答案。因此动态阈值getMax()才是理论正确的做法这正体现了保守阈值 动态计算的必要性。三种算法对比与选型建议维度双向 BFSA* 算法IDA* 算法搜索框架双队列按层交替扩展优先队列按g h弹出迭代加深 DFS 启发式剪枝空间消耗两个方向各约b^(d/2)需维护优先队列与映射表仅 DFS 递归栈空间最省最短步数保证相遇即返回必然最优h可采纳时保证最优从 0 逐层加深首次成功即最优无解处理某方向队列搜空即返回 -1需遍历全部可达状态效率低深度超过阈值仍未成功即返回 -1本题适用性首选推荐指数最高可通过但无解时退化可通过配合动态阈值有 TLE 风险选型结论本题在「有解」「数据范围可控」「层级节点指数增长」的特性下双向 BFS 是空间与时间最均衡的解法A* 与 IDA* 的价值更多在于掌握「启发式函数设计」「可采纳性」「迭代加深」等进阶搜索思想可迁移到 Index/启发式搜索.md 索引中收录的 473. 火柴拼正方形、488. 祖玛游戏、675. 为高尔夫比赛砍树、773. 滑动谜题、847. 访问所有节点的最短路径、854. 相似度为 K 的字符串、1879. 两个数组最小的异或值之和、2045. 到达目的地的第二短时间 等题目。配套学习路径与仓库使用指引本仓库LogicStack-LeetCode是「宫水三叶的刷题日记」系列文章的题解集合共分三层结构便于按需检索LeetCode/按题号区间分目录存放全部题解每篇题解包含题目描述、示例、数据范围与多解法完整代码如本题位于 LeetCode/751-760/Index/按算法 Tag 分类的题目索引表本题同时收录于 Index/图论 双向 BFS.md 与 Index/启发式搜索.md方便按专题刷题PDF/按专题整理的合集 PDF如「图论BFS」「回溯算法」「状态机 DP」等适合离线阅读。推荐的练习顺序先精读 127. 单词接龙 的双向 BFS 部分再把本题作为练习吃透后可在 Index/图论 双向 BFS.md 中选择 433、815、934、1345、2059 等题目巩固模板。如需在本地克隆仓库可执行git clone https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode总结本题《打开转盘锁》是「最短路 / 最小步数」问题的绝佳载体10^4个状态、每状态 8 个邻居、存在障碍物恰好能完整展示朴素 BFS 的搜索空间爆炸困境以及双向 BFS、A*、IDA* 三种进阶搜索方案的优化路径。本系列文章自 2021/01/01 开始按题号逐篇更新除讲解解题思路外还尽可能给出最简洁的代码与通解模板读者可结合仓库内对应题解与 Tag 索引持续跟进学习。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 刷穿 LeetCode 系列单词接龙127—— 双向 BFS 与 A* 启发式搜索实战解析LogicStack LeetCode 刷穿 LeetCode 系列单词接龙127—— 双向 BFS 与 A 启发式搜索实战解析 本文是「LogicSta教程文档打开转盘锁Open the LockBFS 最短路径全解标准 BFS、逐层 BFS 与双向 BFS 的实现与优化打开转盘锁Open the LockBFS 最短路径全解标准 BFS、逐层 BFS 与双向 BFS 的实现与优化 本篇技术指南围绕 LeetCode 75示例工程教程LogicStack-LeetCode 题解 | 1129. 颜色交替的最短路径双色有向图上的 BFS 最短路LogicStack LeetCode 题解 | 1129. 颜色交替的最短路径双色有向图上的 BFS 最短路 导读 本篇基于仓库 LeetCode/1221教程文档上一篇Rust 编译器 CI Docker 测试指南用 citool 与 run.sh 在本地复现 rustc 构建任务下一篇Bazel 在 Ubuntu 上的安装指南APT 仓库、Bazelisk、二进制安装器与 Docker 全方案详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/10 9:02:22 · 阅读 1.2k 打开转盘锁最短路径搜索实战：双向 BFS、A* 与 IDA* 三解法全解（LogicStack-LeetCode 刷穿系列 No.752）
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以「刷穿 LeetCode」系列第 752 题《打开转盘锁》为核心系统讲解「最短路/最小步数」类问题的三种经典求解方案双向 BFS、A* 算法与IDA* 算法。通过本题的完整代码与逐行注释读者可以掌握搜索空间爆炸的成因与对策、启发式函数的设计方法以及迭代加深与动态阈值剪枝的组合技巧并将其迁移到仓库中 127. 单词接龙、433. 最小基因变化、773. 滑动谜题等同类题目上。本题题解位于 LeetCode/751-760/752. 打开转盘锁中等.md并同时被收录于 Index/图论 双向 BFS.md 与 Index/启发式搜索.md 两个 Tag 索引中属于「双向 BFS」与「启发式搜索」两大专题的交叉例题。题目描述与问题建模你有一个带有四个圆形拨轮的转盘锁每个拨轮都有 10 个数字0到9。每个拨轮可以自由旋转例如把9变为00变为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 500deadends[i].length 4target.length 4target不在deadends之中target和deadends[i]仅由若干位数字组成从建模角度看本题是一个典型的「最短路 / 最小步数」问题状态空间0000到9999共10^4 10000个状态节点转移关系每个状态固定有 8 个邻居4 个拨轮 × 正向/反向两种旋转障碍物deadends中的状态不可进入目标从s 0000到t target的最少旋转次数不可达返回-1。基本分析朴素 BFS 的搜索空间爆炸问题此类「最小步数」问题通常我们会使用BFS广度优先搜索求解但朴素的 BFS 往往会带来搜索空间爆炸的问题。我们知道递归树的展开形式是一棵多阶树。使用朴素 BFS 进行求解时队列中最多会同时存在两层的搜索节点因此搜索空间的上界取决于目标节点所在的搜索层次深度所对应的宽度。以本题为例起点0000的 8 个邻居在第一层全部入队第二层每个节点又各自扩展出 8 个邻居去重后仍有大量新增随着层数加深队列宽度以指数级别增长。在朴素的 BFS 实现中空间的瓶颈主要取决于搜索空间中的最大宽度。层数越深宽度爆炸越严重这就是朴素 BFS 在大状态空间下不可行的根本原因。仓库中的 127. 单词接龙 题解对这一点有更直观的量化对于一个长度为 10 的beginWord替换一次字符可以产生10 × 25个新单词第一层就产生 250 个单词第二层超过 6×10⁴ 个……「随着层数的加深这个数字的增速越快」。本题题解同样指出127. 单词接龙定位困难而本题定位中等主要体现在数据范围上思维难度上 127 并不比本题难因此官方推荐的练习路线是先做 127. 单词接龙再回过头把本题作为练习题。既然朴素 BFS 空间扛不住那么有没有办法让我们不使用这么宽的搜索空间同时又能保证搜索到目标结果呢答案是「双向 BFS」以及更进一步的「A* / IDA* 启发式搜索」。解法一双向 BFS原理从两个方向同时逼近「双向 BFS」可以很好地解决搜索空间爆炸问题同时从两个方向开始搜索一旦搜索到相同的值意味着找到了一条联通起点和终点的最短路径。它的核心收益在于空间消耗的指数级下降若单向 BFS 的搜索深度为d、每层宽度基数为b总搜索节点量级约为b^d而双向 BFS 让两个方向各搜索约d/2层总量级约为2 × b^(d/2)。对于「有解」「有一定数据范围」同时「层级节点数量以倍数或者指数级别增长」的情况双向 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) {}完整 Java 实现带详细注释原题解为便于第一次接触「双向 BFS」的读者理解给出了带大量注释的实现class Solution { String t, s; SetString 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 开始搜索反向 DequeString d1 new ArrayDeque(), d2 new ArrayDeque(); /* * m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来 * e.g. * m1 {1000:1} 代表 1000 由 s0000 旋转 1 次而来 * m2 {9999:3} 代表 9999 由 t9996 旋转 3 次而来 */ MapString, 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(DequeString deque, MapString, Integer cur, MapString, Integer other) { int m deque.size(); while (m-- 0) { 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; } }关键实现细节拆解按层扩展update开头先记录int m deque.size()随后while (m-- 0)只扩展当前层的全部节点。这一步保证了两方向搜索的层数对齐是step 1 other.get(str)能正确拼出最短总步数的前提——相遇时正向走了step 1步反向已经走了other.get(str)步。相遇判定即答案当某个方向扩展出的新状态str出现在另一方向的哈希表other中时直接返回step 1 other.get(str)无需再继续扩展。旋转的枚举写法用j ∈ {-1, 0, 1}枚举「正向转一格 / 反向转一格」if (j 0) continue跳过原地不动。注意 Java 中(origin j) % 10在origin 0, j -1时结果为-1因此需要if (next -1) next 9手动回绕到9。死锁与去重set.contains(str)跳过deadends中的死亡数字cur.containsKey(str)防止当前方向重复扩展同一状态。两个方向各用独立的哈希表m1/m2记录步数避免互相污染。与 127. 单词接龙的双向 BFS 对照本题代码与仓库中 127. 单词接龙 的双向 BFS 实现同构同样是双队列d1/d2 双哈希表m1/m2同样在循环里比较d1.size() d2.size()选择扩展方向同样在update中发现other.containsKey(sub)时返回cur.get(poll) 1 other.get(sub)。两者差异只在于邻居生成规则127 题枚举替换原字符串的每个位置i再枚举 26 个小写字母j并校验新单词必须存在于wordSet752 题枚举 4 个拨轮位置i再枚举偏移量j -1 / 1并校验新状态不能命中deadends。把这两份代码并排阅读即可抽象出「双向 BFS」的通用模板面向具体问题的部分只有邻居生成与合法性校验框架部分双队列、双哈希表、小队列优先、相遇返回完全一致。该模板同样适用于 Index/图论 双向 BFS.md 索引中收录的 433. 最小基因变化、815. 公交路线、934. 最短的桥、1345. 跳跃游戏 IV、2059. 转化数字的最小运算数 等题目。解法二AStar 算法启发式函数的设计可以直接根据本题规则来设计 A* 的「启发式函数」。对于两个状态a和b可直接计算出「理论最小转换次数」不同字符的转换成本之和。由于每个拨轮可以从两个方向旋转某个位置上的数字从cur变到target的最小旋转次数是「正向距离」与「反向距离」的较小者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; }其中b - a是正向旋转的距离a 10 - b是绕过一圈即反向的距离。该启发式不会高估实际剩余代价每步只能旋转一个拨轮一格f是剩余步数的下界满足 A* 算法「可采纳admissible」的前提因此首次从优先队列中弹出target时得到的步数仍是最优解。一个必须注意的关键点由于我们衡量某个字符str的估值是以目标字符串target为基准因此我们只能确保target出队时为「距离最短」而不能确保中间节点出队时「距离最短」。因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队还要结合当前节点的「最小距离」是否被更新而决定是否入队。这一点十分关键在代码层面上体现在map.get(str).step poll.step 1的判断上——只有新路径的步数严格更少才更新该状态并重新入队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; SetString 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; PriorityQueueNode q new PriorityQueue((a,b)-a.val-b.val); MapString, 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; } }注意Node中val实际保存的是step 1 f(str)即f g h已走步数 启发式估值优先队列按val升序弹出从而始终优先扩展「当前已走步数 剩余预估步数」最小的状态。适用前提与局限本题用 A* 可以通过但通常我们需要先「确保有解」A* 的启发搜索才会发挥真正价值。而本题中除非t本身在deadends中其余情况我们无法很好提前判断「是否有解」。对于无解的情况A* 效果不如「双向 BFS」。原因在于A* 在无解时仍需遍历完整个可达状态空间而双向 BFS 一旦某个方向的队列被搜空即可提前判定无解并终止。因此实战选型时本题更推荐以双向 BFS 作为主解法A* 作为启发式思路的进阶学习。解法三IDAStar 算法从迭代加深到 IDA*同样可以使用基于DFS的启发式 IDA* 算法仍然使用f()作为估值函数利用旋转次数有限总旋转次数不会超过某个阈值max利用「迭代加深」的思路找到最短距离——不断增大深度上限max并重复 DFS首次搜索成功时的深度即为最短步数。理想情况下由于存在正向旋转和反向旋转每一位转轮从任意数字开始到达任意数字消耗次数不会超过 5 次因为绕 10 个刻度从两侧逼近最多半圈因此理想情况下可以设定max 5 * 4 20。但考虑deadends的存在可能需要绕远路避开死亡数字需要将max定义得更加保守一些max 10 * 4 40。静态阈值的问题TLE 风险但这样的阈值设定加上 IDA* 算法每次会重复遍历「距离小于目标节点距离」的所有节点会有很大的 TLE 风险。固定大阈值意味着每次失败的 DFS 都要在较深的层次上做大量重复搜索。动态阈值按 target 计算最大转移成本因此我们需要使用动态阈值不再使用固定的阈值而是利用target计算出「最大的转移成本」作为我们的「最深数量级」。getMax()逐位计算从起点到target的最大旋转成本正向距离与反向距离取max即最坏情况下需要的步数累加后作为本次搜索的深度上限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; }完整实现如下class Solution { String s, t; String cur; SetString set new HashSet(); MapString, 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; } }核心剪枝逻辑if (u f() max) return false—— 当前已走步数u加上剩余启发式估值f()一旦超过深度上限max就立即剪枝if (f() 0) return true—— 启发式估值为 0 说明已到达target。每次迭代加深失败后都要map.clear()并重置cur s为下一轮更深搜索重建状态。关于阈值设定的一处提醒上述的阈值分析是科学做法。对于本题可以利用数据弱直接使用max 5 * 4 20也可以通过并且效果不错。但必须清楚max 5 * 4可能是一个错误的阈值。例如本题起点为0000考虑将所有正向转换的状态都放入deadends中、target为2222这时候可以构造出只限定「0000先变为9999再往回变为2222」的通路不在deadends中的反例——该通路单轮旋转次数超过 5使用max 20就会得出错误答案。因此动态阈值getMax()才是理论正确的做法这正体现了保守阈值 动态计算的必要性。三种算法对比与选型建议维度双向 BFSA* 算法IDA* 算法搜索框架双队列按层交替扩展优先队列按g h弹出迭代加深 DFS 启发式剪枝空间消耗两个方向各约b^(d/2)需维护优先队列与映射表仅 DFS 递归栈空间最省最短步数保证相遇即返回必然最优h可采纳时保证最优从 0 逐层加深首次成功即最优无解处理某方向队列搜空即返回 -1需遍历全部可达状态效率低深度超过阈值仍未成功即返回 -1本题适用性首选推荐指数最高可通过但无解时退化可通过配合动态阈值有 TLE 风险选型结论本题在「有解」「数据范围可控」「层级节点指数增长」的特性下双向 BFS 是空间与时间最均衡的解法A* 与 IDA* 的价值更多在于掌握「启发式函数设计」「可采纳性」「迭代加深」等进阶搜索思想可迁移到 Index/启发式搜索.md 索引中收录的 473. 火柴拼正方形、488. 祖玛游戏、675. 为高尔夫比赛砍树、773. 滑动谜题、847. 访问所有节点的最短路径、854. 相似度为 K 的字符串、1879. 两个数组最小的异或值之和、2045. 到达目的地的第二短时间 等题目。配套学习路径与仓库使用指引本仓库LogicStack-LeetCode是「宫水三叶的刷题日记」系列文章的题解集合共分三层结构便于按需检索LeetCode/按题号区间分目录存放全部题解每篇题解包含题目描述、示例、数据范围与多解法完整代码如本题位于 LeetCode/751-760/Index/按算法 Tag 分类的题目索引表本题同时收录于 Index/图论 双向 BFS.md 与 Index/启发式搜索.md方便按专题刷题PDF/按专题整理的合集 PDF如「图论BFS」「回溯算法」「状态机 DP」等适合离线阅读。推荐的练习顺序先精读 127. 单词接龙 的双向 BFS 部分再把本题作为练习吃透后可在 Index/图论 双向 BFS.md 中选择 433、815、934、1345、2059 等题目巩固模板。如需在本地克隆仓库可执行git clone https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode总结本题《打开转盘锁》是「最短路 / 最小步数」问题的绝佳载体10^4个状态、每状态 8 个邻居、存在障碍物恰好能完整展示朴素 BFS 的搜索空间爆炸困境以及双向 BFS、A*、IDA* 三种进阶搜索方案的优化路径。本系列文章自 2021/01/01 开始按题号逐篇更新除讲解解题思路外还尽可能给出最简洁的代码与通解模板读者可结合仓库内对应题解与 Tag 索引持续跟进学习。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 刷穿 LeetCode 系列单词接龙127—— 双向 BFS 与 A* 启发式搜索实战解析LogicStack LeetCode 刷穿 LeetCode 系列单词接龙127—— 双向 BFS 与 A 启发式搜索实战解析 本文是「LogicSta教程文档打开转盘锁Open the LockBFS 最短路径全解标准 BFS、逐层 BFS 与双向 BFS 的实现与优化打开转盘锁Open the LockBFS 最短路径全解标准 BFS、逐层 BFS 与双向 BFS 的实现与优化 本篇技术指南围绕 LeetCode 75示例工程教程LogicStack-LeetCode 题解 | 1129. 颜色交替的最短路径双色有向图上的 BFS 最短路LogicStack LeetCode 题解 | 1129. 颜色交替的最短路径双色有向图上的 BFS 最短路 导读 本篇基于仓库 LeetCode/1221教程文档上一篇Rust 编译器 CI Docker 测试指南用 citool 与 run.sh 在本地复现 rustc 构建任务下一篇Bazel 在 Ubuntu 上的安装指南APT 仓库、Bazelisk、二进制安装器与 Docker 全方案详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考