如果你写过任何一个"暴力搜索"的程序——八皇后、走迷宫、解数独——你多半在某个瞬间撞上过同一堵墙：状态空间大得离谱，遍历根本跑不完。Sebastian Lague 这条 27 分钟的视频，把这个问题用全世界最熟悉的玩具——魔方——讲得透彻又漂亮。
魔方的难，不在于"转不动"，而在于组合爆炸：一个三阶魔方有约 4.3×10¹⁹ 种状态（读作"四千三百亿亿"），这个数字比地球年龄换算成的秒数还要大近 7 亿倍。可偏偏数学家已经证明，任意一个状态，最多 20 步就能复原——这就是著名的"上帝之数（God's Number）"。于是矛盾就出现了：答案明明就在 20 步之内，但你怎么把那 20 步从 4 千亿亿种可能性里"找"出来？
这条视频记录的，正是 Sebastian 用三种思路（观众在上一期评论区里给他支的招）一步步把自己的求解器从"能解"推向"逼近最优"的过程。它本质上是一堂用具体案例讲透组合搜索、启发式剪枝、问题约简的算法课。无论你做的是路径规划、调度、推荐系统的 beam search，还是大模型推理时的 decoding，视频里的核心思想都能迁移。下面我来拆解。
| 项目 | 内容 |
|---|---|
| 视频标题 | Coding Adventure: Improving my Rubik's Cube Solver |
| 频道 | Sebastian Lague |
| 订阅数 | 140 万 |
| 时长 | 27 分 28 秒 |
| 发布日期 | 2026 年 6 月 3 日（解读时发布约 10 天） |
| 播放量 | 约 16 万（系列上一期"Coding Adventure: Rubik's Cube"约 33 万） |
| 核心主题 | 用 CFOP、Domino Reduction、IDA* + 剪枝表改进魔方求解器，逼近最优解 |
| 源码 | github.com/SebLague/Rubiks-Cube |
一句话定位：这是"Coding Adventure"系列的最新一期——这个系列以极高制作水准（自研 3D 可视化、片尾 raytracing 渲染）著称，每期都用一个具体项目把某个算法或数学概念讲到让你"看见抽象"。
视频开篇的四个章节（Cross、F2L、OLL、PLL）其实就是人类速拧界统治级的方法 CFOP。它把复原拆成四个阶段：
顶尖速拧选手用 CFOP 能在 3 到 5 秒内复原一个魔方，平均步数大约 55 到 60 步。Sebastian 在这里做了一件有意思的事：让程序"像人一样"按 CFOP 的阶段去求解。
这段的真正价值，不在于"程序学会了拧魔方"，而在于它点破了一个关键认知——人类和计算机优化的目标根本不是同一个。人类追求的是速度：CFOP 的力量来自模式识别 + 肌肉记忆 + 几百条背下来的公式（OLL/PLL 共 57+21 个 case），它牺牲了步数，换来了"看一眼就能动手"。而计算机要追求的，是最少的步数。CFOP 的 55 步，距离上帝之数 20 步，差着一整个数量级。这个落差，就是后面所有算法要填的坑。
我的延伸：这种"目标错配"在工程里随处可见。你给团队定的 KPI 是"上线快"，他们就会堆 CFOP 式的捷径；你定的是"代码精简/最优解"，他们就得去做 IDA* 式的深度搜索。算法的选择，本质上是被优化目标决定的，不是被"哪个更高级"决定的。
真正硬核的部分从 Domino Reduction（多米诺约简） 这一章开始。这是整条视频最聪明的一步棋，也是 Kociemba 两阶段算法（two-phase algorithm）的灵魂。
所谓 Domino Reduction，是先把魔方约简到一个受限的子群（subgroup）G₁——在这个子群里，你只需要用 180° 的半转（U2、D2、L2、R2、F2、B2）就能继续操作，魔方此时表现得就像一个"多米诺骨牌"拼图。一旦进入这个"多米诺状态"，搜索空间会断崖式地缩小。
为什么要这么做？因为如果你直接对完整魔方做穷举搜索，4.3×10¹⁹ 个状态根本无解。但如果你把它拆成"先降到 G₁"+"在 G₁ 里求解"两个阶段，每个阶段的搜索深度都被压到了个位数到十几步，组合起来才变得可行。
这是一个极其通用的工程思想：遇到一个爆炸的大问题，不要硬刚，先找到一个变换把它降维成一个结构更规整的小问题。在通信网优化里（比如路由表的压缩、状态机合并）、在编译器里（把中间表示 lowering 到更窄的指令集）、在数据库里（先按索引过滤再做 join），你都能看到"先约简、再求解"的同款套路。
视频在 Resources 里直接挂了 kociemba.org/cube.htm，因为后面的 IDA* + 剪枝表路线，走的正是 Herbert Kociemba 提出的两阶段算法的思路：
Kociemba 算法的厉害之处在于：它不追求"绝对最优"，而是用一个可控的搜索，在毫秒级时间里给出 20 步左右的解。而真正的理论下限——上帝之数 = 20——是在 2010 年由 Tomas Rokicki、Herbert Kociemba、Morley Davidson 和 John Dethridge 借助 Google 的算力完成的证明：任何魔方状态，在半转度量（half-turn metric）下，最多 20 步必能复原。
这是整条视频隐含的"北极星"：无论你怎么优化，你都不可能比 20 步更少。20 就是物理极限。所有求解器的目标，都是在"求解时间"和"逼近 20"之间找平衡点。
约简之后，怎么真正"搜"出那串步数？答案是 IDA*（Iterative Deepening A*，迭代加深 A*）。视频专门用了两章（Iterative Deepening、IDA*）讲它，这是理解整条视频的算法核心。
先说为什么要迭代加深（Iterative Deepening）。找最短解，最朴素的办法是 BFS——一层层往外搜。但 BFS 要把所有访问过的状态都记下来，对魔方这种规模，内存会先爆炸。迭代加深的思路是：反复做深度受限的 DFS，第 1 轮只找深度 ≤1 的解，找不到就把上限调到 2，再找不到调到 3……每轮都从根节点重新开始。听起来很"浪费"（重复搜索了大量节点），但实际上因为搜索树的节点数是指数增长的，最底层那一轮的工作量占绝大多数，前面的重复根本可以忽略不计，而它换来的好处是：内存开销只有 O(深度)，几乎可以忽略。
再说 A* 的那颗"星"。纯 DFS/迭代加深是"瞎搜"，没有方向感。A* 引入了一个启发式函数 h(n)：对每个状态 n，估计它"还差多少步能复原"。搜索时优先走 g(n) + h(n)（已走步数 + 估计剩余步数）最小的路径。当 h(n) 是可采纳的（admissible，即永远不高估真实剩余步数）时，A* 能保证找到最优解。
IDA* 就是把这两者缝合：用迭代加深的框架（省内存），用 A* 的启发式剪枝（省时间）。当某个分支的 g + h 已经超过当前的深度上限，就直接砍掉，不再深挖。这就是"为什么程序能在合理时间里逼近 20 步"的引擎。
但光有 IDA* 还不够——启发式 h(n) 如果太弱，剪枝几乎不发生，搜索还是跑不完。于是视频的关键一章来了：Prune Tables（剪枝表）。
剪枝表的本质，是用空间换时间的极致：把魔方的状态拆成几个相互"独立"的坐标（coordinate），对每个坐标，预先算好"从任意取值到目标，至少需要多少步"，存成一张查找表。搜索时，把这几张表查出来的值取一个最大值，作为 IDA* 的启发式 h(n)。
魔方常用的几个坐标规模都不大，正好适合预计算：
把这些坐标的"最优剩余步数"用 BFS 从目标状态反向扫一遍就能填满一张表。搜索时，多张表取 max——因为每个坐标都是真实剩余步数的下界，max 之后仍是下界，依然 admissible，且剪枝力度大幅增强。这正是 Culberson & Schaeffer（1998）和 Richard Korf 把"模式数据库（pattern database）"发扬光大时确立的范式。
这一段给我的最大启发：所谓"性能优化"，很多时候不是把算法写得更花，而是把一部分计算提前算好、存起来。剪枝表就是"以 GB 级内存换毫秒级响应"的典型。你做缓存、做预聚合、做物化视图、做大模型的 KV-Cache，本质都是同一个招——把昂贵的搜索/计算，换成便宜的查表。
视频倒数第二章 Multi-Search，是在两阶段算法上做的高级优化，也是把求解器从"还不错"推向"逼近最优"的最后一把劲。
朴素的 Kociemba 两阶段有个毛病：Phase 1 只取第一个找到的解，可能不是全局最优组合。因为 Phase 1 的解越短，不代表"Phase 1 + Phase 2 总步数"越短——有时候 Phase 1 多走一步，反而把魔方送进一个 Phase 2 极短的子状态，总步数更优。
Multi-Search 的做法（也是工程界成熟的做法）是：不要只搜一条 Phase 1 路径，而是保留多条候选，对每条候选都跑一次 Phase 2，最后挑出"总步数最短"的那条。这本质上是把"贪心"升级成"带宽度的小型 beam search"。代价是计算量成倍上升，换来的是解的步数进一步逼近下限。
这是个很现实的工程权衡：最优解几乎总是更贵的。愿意花 10 倍算力，能把 22 步压到 20 步；想再往下，可能要 100 倍。视频用"最终结果对比"直观地呈现了这条收益递减曲线——这也是所有优化问题的宿命。
flowchart TD
A["目标：用尽可能少的步数复原魔方<br/>理论下限 = 上帝之数 20（2010 证明）"] --> B{"求解路线分叉"}
B -->|"人类路线：追求速度"| C["CFOP 人类速拧法<br/>Cross→F2L→OLL→PLL<br/>~55 步 / 3-5 秒<br/>靠模式识别+肌肉记忆"]
B -->|"机器路线：追求步数"| D["组合搜索 + 启发式剪枝"]
D --> E["① Domino Reduction<br/>约简到子群 G₁（多米诺状态）<br/>= Kociemba Phase 1"]
E --> F["② 在 G₁ 内继续搜索<br/>= Kociemba Phase 2（仅半转）"]
F --> G["③ IDA* 搜索引擎<br/>迭代加深（省内存）<br/>+ A* 启发式 h(n)（省时间）<br/>h 可采纳 ⇒ 保证最优"]
G --> H["④ Prune Tables 剪枝表<br/>角块朝向 3^7=2187<br/>棱块朝向 2^11=2048<br/>UD-slice C(12,4)=495<br/>多表取 max ⇒ 剪枝力大增"]
H --> I["⑤ Multi-Search<br/>保留多条 Phase 1 候选<br/>= 带 beam 的小型束搜索"]
I --> J["最终解：20~22 步<br/>逼近上帝之数"]
C -.->|"步数多但极快"| K["适用：实时、人机交互"]
J -.->|"步数少但算力贵"| L["适用：离线、追求最优"]
style A fill:#fef3c7,stroke:#d97706
style J fill:#dcfce7,stroke:#16a34a
style H fill:#dbeafe,stroke:#2563eb
style G fill:#e0e7ff,stroke:#4f46e5
1. 把"问题约简"变成肌肉记忆。 Domino Reduction 给出了一个万能模板：别正面硬刚指数爆炸的状态空间，先找一个变换把它降到一个结构更简单的子问题。你做状态压缩、做张量分解、做索引下推、做问题归约（reduce to known problem），都是这一招。下次遇到一个搜索/优化跑不动，先问自己："能不能先把问题变小？"
2. 学会用"可采纳的启发式"驱动搜索。 IDA* 的精髓是：只要你的启发式 h(n) 永远不高估真实成本，就能既剪枝、又保证最优。这个"admissible 启发式"的思想，可以直接搬到大模型 decoding（beam search 的打分）、路径规划（A*）、约束求解上。关键是找到一个"乐观但有用"的下界估计。
3. 把昂贵的搜索，换成便宜的查表。 Prune Tables 是"空间换时间"的教科书案例：花几 GB 内存预计算，把指数级搜索压成毫秒级。现实工程里——Redis 缓存、物化视图、向量索引、LLM 的 KV-Cache、Prompt Cache——全是同构的思路：能预算的，绝不运行时算。
4. 迭代加深：用"看似浪费"换"可扩展性"。 重复搜索上层节点听起来很蠢，但因为树是指数增长的，最底层占了绝大部分工作量，重复成本可忽略，却换来 O(深度) 的极小内存。当你被"内存放不下"卡住时，记得有这个反直觉的选项。
5. 接受"最优解几乎总是更贵"。 Multi-Search 揭示的收益递减曲线是所有优化的真相：花 10 倍算力换来几步的提升。工程上要清醒——先定义"够好"的阈值，别为了最后一丝最优耗尽预算。
6. （元启示）开放你的代码，让观众帮你进化。 视频开篇就明说：CFOP、Domino Reduction、剪枝表这三个关键改进，全是上一期评论区观众给的灵感。把项目开源（github.com/SebLague/Rubiks-Cube）、公开你的求解器，社区会把你自己想不到的优化路径送上门。这是 Sebastian 这条视频能持续进化的真正原因，也值得每个开发者借鉴。
它用一只魔方，把"组合搜索 → 问题约简 → 启发式剪枝 → 预计算查表"这条算法工程的完整武器链，讲成了一个让你看得见、摸得着、还想自己动手复刻的故事——而真正的彩蛋是：推动求解器进化的不是天才，是开源社区里那些热情的观众。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。