游戏里的算法七讲
寻路、动态规划到博弈 AI 的七篇合集
游戏是算法最耐心的考官：一帧 16 毫秒的预算、一个会反击的对手、一个随成功不断收紧的空间，都是教科书给不了的真实约束。本文由站内七篇算法长文合并而成，七讲依次是：寻路怎么选型、贪吃蛇 AI 怎么在自造的墙里保命、递归凭什么可信、动态规划与并查集怎么分工、序怎么建立与维持、搜索的骨架长什么样、博弈 AI 的三件武器各管什么。七讲共享同一条底色：算法的选型跟着场景的约束走。
寻路：最优性、预算与可读性
寻路是游戏里最日常的算法，也是最容易被学了 A* 就一招鲜的思维绑架的领域。教科书写成一条进化的直线，仿佛 A* 永远是终点；真实的游戏工程里三者出场率都不低，选谁取决于场景的三种约束：要不要最优解、预算多少微秒、目标是一个还是一群。本站恰好有三个 widget 把这三种约束各演一遍：迷宫里的求解器要的是最短路，吃豆人的幽灵要的是看起来聪明，塔防则直接把路径修死，让寻路问题整个消失。配合下面嵌入的蚂蚁寻路演示，可以逐帧看清搜索的每一步。
三代算法，一本账
先把三位主角的分工钉死。网格地图天然是一个图：格子是节点，相邻通道是边。
在边权全相等的前提下（走一步就是一步），三代算法的递进关系如下。
BFS（广度优先）：从起点逐层外扩，第一次碰到终点时的层数就是最短步数。它是最短路的特例专用解，只在边权全等时保证最优。胜在代码十行、无参数、绝对稳定。
Dijkstra：BFS 的带权推广，优先队列每次弹出累计代价最小的节点。非负边权下保证最优。缺点是不分方向地全面铺开，终点就在东边，它照样往西淹半张地图。
A*：Dijkstra 加一个直觉。给每个节点估一个离终点还剩多远的下界 ，优先队列改按 排序（ 是已走代价）。只要 不高估真实剩余距离（可采纳性），第一次弹出终点时的路径仍然保证最短。
优先队列这一层还藏着一个工程暗坑。
Dijkstra/A* 每轮要”更新某个已在队列中的节点的代价”（发现更短的 ），教科书写法是 decrease-key 操作，要求索引式堆。而工程实现更常用懒惰删除：旧条目不删，直接塞入新条目，弹出时发现是过期的就丢弃。
后者代码短、常数小，代价是队列里堆着冗余条目。网格寻路里几乎总是选后者。这个选择与算法正确性无关，纯粹是堆的两种使用姿势的成本权衡。但写错了（弹出时没验过期）就会返回鬼路径，是寻路 bug 的另一大来源。
A* 的省力原理一句话就能说透：启发式把优先队列变成了朝着目标方向的 Dijkstra。被 拉高的远离目标的节点沉底，扩展前沿像锥形一样怼向终点。
但注意这个保证有边界： 不高估，最优性才成立。
曼哈顿距离（）对四方向移动是最著名的可采纳启发式。因为每一步最多让曼哈顿距离减 1，真实剩余步数不可能小于它。
换成八方向移动，得用切比雪夫距离或带对角权重的八方向距离。换成能沿直线冲刺的移动模型，欧几里得距离才不上界。
启发式选错模型，A* 会在不知不觉间开始返回次优路径。而且通常没人发现。
网格模型还有一个只在八方向下现形的暗坑：穿角。
两个斜放的墙格之间那条对角缝，四方向模型里根本不存在，八方向的单位却能斜着挤过去。贴墙潜行、穿缝逃逸之类的诡异路径都源于此。
处理办法是给对角移动加合法性检查：两个相邻的正交格必须至少有一个可通行（更严格的版本是两个都要通）。
这类规则全在网格模型自身的几何里。这也是为什么寻路的 bug 十有八九不在算法层，在图怎么建这一层。
| 算法 | 保证最优 | 前提 | 扩展形态 |
|---|---|---|---|
| BFS | 是 | 边权全等 | 无差别环状泛洪 |
| Dijkstra | 是 | 边权非负 | 无差别加权泛洪 |
| A* | 是 | 不高估 | 朝目标的锥形推进 |
迷宫
迷宫是个天然的闭环，它自己既出题又解题。
生成一张迷宫最常用的递归回溯：从起点出发，随机挑一个没访问过的邻居凿穿中间的墙，走过去。四周都访问过了就回退到上一个岔口。
这是一次随机化的 DFS，走完全图后得到的东西有精确的图论身份：一棵生成树。
树上加一个完美迷宫的名字，意味着两个性质：任意两点之间恰有一条通路，且迷宫里不存在任何环路。
这两个性质直接决定了解题端的算法表现。
其一，既然任意两点路径唯一，那么最短路就是”那条唯一的路”。BFS、A*、甚至不考虑最优性的 DFS，最终交出的路径必然同一条。差别全在找到它的过程。
DFS 顺着单胡同深入，回退时成片反悔，访问面积小但路径扭曲。BFS 从起点环状泛洪，访问面积常常过半张图。A* 则在两者之间，被启发式牵着朝终点锥形推进。
本站迷宫的求解器把这三种算法做成了可切换的选项，并按访问顺序逐格动画回放。同一个迷宫跑三遍，扩展面积的差异一目了然。
其二，唯一路径对玩家体验是个贬义词。死路多的迷宫考验的是记路。
所以很多生成器会生成之后随机再拆掉若干面内部墙，人为制造环路。每拆一面墙，生成树就多一条边，多一个环，玩家（和追击者）的选择空间随之变大。
这个”生成完美迷宫 + 打环”的两段式，是迷宫类内容生成的标准配方。
生成算法不止一种
随机生成树不止一种随机法，而且不同的随机法生成出的迷宫气质完全不同。
递归回溯是随机化的深度优先，生成树是一条深深浅浅的长藤。走廊长、死胡同深，玩起来一走到底才发现是死路的比例高。
随机 Prim 是随机化的广度扩张，生成树矮胖。岔路密、死胡同浅，玩起来选择多但每个错误都不致命。
分治法把地图切成小块各自生成再打通，结构规整但人味最重。
三种迷宫用生成树的语言说，就是同一条骨架上不同的生长偏置。没有哪种绝对更好，选哪种取决于把迷宫交给谁。解谜玩家要深死路带来的挫败感，追逐游戏（下一节的主角）要环路带来的逃生意愿。
生成算法的选择，是在为下游玩法挑一棵形状合适的树。
墙模型的小工程账
表示法。迷宫格子常见两种存法。每格存一个四元布尔（上右下左有无墙），或者用奇偶网格（把墙也编成格子）。
前者直觉、改墙方便。后者让”凿墙”变成”改一个字符”，代码短。
本站迷宫用的是前者，因为求解动画需要按面绘制墙线，四面墙的布尔量直接对应四条线段。吃豆人用的是后者，因为它的迷宫只是移动合法性的查询表。
同一个算法，表示法跟着下游需求走。
吃豆人幽灵
吃豆人的幽灵常被当作游戏 AI的最初记忆。但拆开本站吃豆人的实现，会看到一个非常诚实的答案：幽灵根本不算最短路。
每只幽灵每隔一拍才动一步（刻意比玩家慢），移动选择是五五开的两手。一半概率在可行方向里随机挑一个，另一半概率挑使与玩家的曼哈顿距离最小的方向。一个一步贪心，连两步 lookahead 都没有。
为什么这么糙？因为实时追击场景对寻路的三条真实约束，全都反对精确算法。
预算。一帧 16 毫秒里要画图、要物理、要四只幽灵各自决策，留给每只的预算以微秒计。曼哈顿贪心是零成本查询，A* 是一笔开销。省下来的算力花在别处更值。
运动连续性。寻路算法输出的是一条路径，而幽灵有当前朝向，多数吃豆人规则里禁止原地掉头。路径再完美，揉进朝向约束后要打折重排。一步贪心天然与朝向兼容。
可读性。这最反直觉也最重要：对手太聪明，游戏就死了。四只幽灵若都用完美 A* 从四个方向包抄，玩家在第二个路口就会被合围，一局三十秒结束。随机扰动让幽灵偶尔走进死胡同，玩家才有骗过它的爽感。难度设计就是给 AI 注入恰到好处的缺陷。
环路的生成法在这里也露出第二重用意。若迷宫是完美迷宫（无环），四向通道稀少，一只只会贪心的幽灵照样能把玩家堵死在单胡同里。是生成器拆墙造的环，救了玩家的命。
算法层面的游戏平衡，很多时候是地图生成层的一句话。
多目标共享一次计算
假如哪天要给每只幽灵都上最短路，也不该一只一只跑 A*。
追击问题的真正结构是：所有幽灵的目标是同一个点。
从玩家所在格跑一次 BFS（或 Dijkstra），把到玩家的距离场写满整张地图。之后任何位置的任何单位查表就能知道下一步往哪走离玩家更近。一次计算，全场共享。
这套流场寻路（flow field）是塔防和 RTS 处理大规模单位的标准答案。它把每个单位寻路的视角翻转成每个格子记录流向。
幽灵们即便不实现它，理解这个翻转也是值得的。优化多目标寻路的第一刀，永远砍在目标其实只有一个上。
A* 可视化
抽象说完，去最短路径可视化里把账对一遍。
25×25 的网格、约两成的随机障碍，起点在左上、终点在右下。点击任意格子可以现场翻转墙壁，然后看算法以动画展开。先铺开淡色的已访问区域，最后亮出黄色的回溯路径。
这个工具是照着 A* 的内部结构画的。每个节点的 、、 都真实计算，开放列表每轮取 最小者。
实现的工程细节有一处看点。开放列表直接用数组排序而不是二叉堆。对几百个节点的网格，排序的开销可以忽略，堆是给上万节点的地图准备的。数据结构升级的时机跟着问题规模走，这是比会用堆更重要的判断。
在可视化里做三个实验，胜过读三段文字。
堵路实验：在已生成的对角通路上横着画一堵墙，重新搜索。访问区域会明显变大，因为启发式对绕行无能为力， 只看得见直线距离。这直观解释了为什么障碍越多、结构越绕的地图，A* 相对 Dijkstra 的优势越小。
起点终点对调：从右下搜左上，动画形态几乎一样。曼哈顿距离对坐标翻转对称。但换成非对称启发式（比如带方向惩罚的 ）就不成立了，这是调试启发式时的常见翻车点。
全开视野对比：把障碍全清掉再跑一次，A* 几乎直线抵达、访问面积趋近于零。启发式在无障碍地图上精度完美。A* 的开销本质上花在地图与启发式假设的偏差上：地图越像启发式的想象，搜索越便宜。
加权 A*
在实时场景里还有一个介于 A* 与纯贪心之间的旋钮：给 乘一个大于 1 的系数。
里 越大，启发式的话语权越重，搜索越像直奔目标的贪心，扩展面积越小。代价是最优性保证退化。
但退化得有底线：-加权 A* 保证返回的路径长度不超过最优的 倍。
这笔交易在工程上极常用。 意味着”最多多走一倍，但访问的格子可能少一个量级”，对不在乎那几步绕行的游戏 AI 是稳赚的买卖。
它也把三代算法串成了一条连续的滑杆。 是 Dijkstra（ 不起作用）， 是 A*， 是纯贪心最佳优先搜索。最优性与速度之间是一个可以拧的旋钮。
塔防
塔防是三种场景里的异类：敌人根本没有寻路。
路径是设计者预先写好的一串转折点（waypoints），敌人被生出来后沿这条折线按参数化位置推进。第几段、段内走了几成，两帧之间线性插值，转角处直接转向。塔不允许建在路径格上，于是整张图退化成一条固定的走廊。
这是偷懒吗？恰恰相反，这是三个场景里最清醒的一个。
塔防的核心循环是建塔改变战场。如果每次建塔都触发全场敌人重算最短路，代价先不论，玩法会立刻失控。敌人绕进死胡同、出现无法预测的路径穿过炮火交叉区，平衡性无从谈起。
把路径钉死，设计者把寻路问题从运行时搬到了设计时。所有博弈都发生在哪段路放多少塔的静态分析里。运行时剩下的唯一”搜索”是索敌：每座塔在射程圆内找最近的目标。一个几步循环的局部查询，连图都不用建。
固定路径还有一笔容易被忽略的算法红利：敌人可以整体参数化。
整条折线提前算好每段的长度与累计里程，任何时刻任何敌人的位置只是一个标量已走里程到坐标的映射。移动、排序（谁跑在最前）、命中判定（子弹与哪个里程相交）全部退化成对一维里程的算术。
索敌的”最近”也常做一层细化：挑射程内里程最大（走得最靠前）的敌人打，而不是几何距离最近的。前者的每一发都花在最可能漏网的目标上。
同一套固定路径，让选目标这件本该昂贵的事变成了读一个数。
反过来的设计也真实存在：允许敌人无视既定路线、但每建一座塔都实时重算全场景的最短路。玩家目标从打塔防变成用塔逼敌人走进火海。这就把最短路算法本身变成了博弈对象。
两种设计没有高下，但后者清楚地演示了一件事：寻路算法的选型问题，往往伪装成玩法设计问题。路径要不要动态、谁来改图、改图频率多少。这三个回答定了，BFS/Dijkstra/A* 的选择几乎是自动的。
三档场景各自的选择是：迷宫求解离线、单目标、要最优，图小预算无限，选 A* 为锥形推进的美感，选 BFS 为十行代码；实时追击在线、高频、要可读，一步贪心加随机扰动，多单位追同一目标用流场摊销；塔防路径静态、玩法优先，让路径成为常量，运行时只做参数化移动与局部索敌。工程里的选型由三个维度决定：最优性要求、时间预算、图的变动频率——先把这三个坐标定下来，算法是自动浮出来的。三档之外还有一条隐形原则贯穿始终：寻路的正确性责任在图的建模，不在搜索的算法——穿角规则、过期队列条目、启发式与移动模型错配，这篇点过的翻车点全部发生在图或队列那一层。检验一个实现是否把这三件事想清楚了，可以直接问它目标变了谁在重算。答案若是”所有单位”，它该有流场；若是”没人，因为图不变”，它是塔防；若是”每个单位自己”，那最好确认一下预算真的够。
贪吃蛇 AI 怎么在自造的墙里活下去
寻路处理的图是死的；贪吃蛇的障碍却是活的，而且是自己一手造出来的——蛇每吃一个食物就长一节，开局四通八达，残局寸步难行。围绕怎么在自造的墙里活下去，蛇 AI 分成两个泾渭分明的流派：追食物的贪心派与哈密顿回路派，前者的每一次移动都是决策，后者的绝大多数移动只是执行。本站贪吃蛇是亲手验证这两种思路的场地，光轮对决（Tron）则是同一套空间直觉的对抗版。
贪吃蛇为什么是个 AI 试金石
先说清楚评价标准。
贪吃蛇 AI 的成绩用两个数衡量：平均长度（或平均得分）和存活率（跑一万局不死几次）。
麻烦在于这两个量天然打架。活得久的策略必然保守，保守就不吃远处的食物，长度上不去。贪吃长度上去了，死亡次数跟着涨。
所以哪个 AI 更好没有唯一的答案，结论总是相对于某个指标而言。这让贪吃蛇成了极佳的教学样本：它逼你先声明目标，再谈算法。
它还有两个让其他游戏羡慕的工程优点。
其一，对局可以无限加速。渲染完全可以关掉，只跑逻辑帧，一万局在一台笔记本上是分钟级的事。评价体系因此可以做得极其严格，这在实时对抗游戏里很难做到。
其二，状态可以完美复现。随机源只有食物刷新点，固定随机种子就得到完全可复现的对局，任何一次死亡都能逐帧回放归因。
评价便宜、归因容易，这两个条件凑齐，贪吃蛇就成了策略迭代的理想跑道。你能清楚地看到每一次改动在死因分布上留下的痕迹。
结构上，贪吃蛇有三个性质决定了它的策略空间。
障碍是动态的。身体每步都在变形，尾巴离开、头进入。静态地图上的最短路算法不能直接照搬，因为这格能不能走的答案每帧都在变。
目标永续存在。食物吃完会再刷，游戏没有终局条件（死除外）。所以 AI 在优化一个无限过程，而不是一步到位的搜索。
状态爆炸但结构简单。完整状态是蛇身序列 + 食物位置，精确求解（比如动态规划）在状态数面前不可行。实用的 AI 都在局部判断 + 全局保险的混合结构里做取舍。
还有个环境变量常被忽略：棋盘尺寸本身就在改写策略的有效性。
小棋盘上（比如 10×10），蛇身很快占掉可观比例，“空间”比”距离”更早成为瓶颈，安全检查的收益早早显现。大棋盘上（30×30），贪心可以横行很久才遇到自围问题，哈密顿派的用时会慢到难以接受。
同一个算法换个棋盘，强弱排序就可能翻转。这其实是所有游戏 AI 的通用现象：算法的强弱取决于与环境合不合拍。
追食物的短视贪心
第一版 AI 十行就能写完。每一步，朝食物方向走，如果那个方向撞墙或撞身体，就换一个不撞的方向。
它能玩，也会以三种非常固定的方式死掉。
先给这版 AI 记一笔公道账。它已经具备了安全性下限。“不撞”检查让它绝不做 immediate suicide，这使它和纯朝食物方向走的零阶策略拉开了本质差距。
真正的算法阶梯从零阶到一阶的这一步，比一阶到二阶（加安全检查）还要大。三种死法全部属于多步之后才爆雷的结构性问题，而不是当场撞死的战术失误。
这个观察直接指出了改良方向：需要往前看不止一步的机制。
死法一：自围。
贪心永远选离食物更近的方向，毫不关心走完之后自己剩下多大的活动空间。
典型剧本是蛇贴着自己的身体绕圈追食，一圈套一圈，突然发现头的前方是墙、身后是自己的三节身体。它每一步都局部最优，组合起来把自己锁死了。
死法二：陷阱食物。
食物刷在一个 U 形口袋的底部，贪心一头扎进去吃完，然后发现唯一的出口被自己刚变长的身体堵住了。
食物位置是随机的，所以这类陷阱必然出现，区别只是蛇多长时遇到。
死法三：断路。
直线距离最近的方向上，路被自己的身体拦腰切断，贪心绕行的方案又恰好撞进另一段身体。
身体越长，曼哈顿距离与实际可达距离的偏差越大。贪心 AI 的智商随体长衰减。
改良
对付这三种死法的改良是同一个思想：每步行动前，先确认走完之后还活着。
具体分两层。
第一层是追尾检查。
吃完这步之后，蛇还能不能追上自己的尾巴？
能追到尾巴，几乎等价于还有一条兜圈子的活路。尾巴是确定会移动让位的格子（只要不吃到食物），它是动态障碍里唯一的准安全区。这个检查把死法一的大部分提前拦下。
实现上就是把追尾巴当成一次最短路搜索。目标格是尾巴尖，障碍是身体（尾巴尖本身视为可进入），搜得到就放行。
有个细节要注意：安全检查要连着”吃”与”不吃”两条分支都查。朝食物走一步若安全，走。若不安全，宁可原地绕圈等尾巴腾出空间也不吃。
蛇不怕饿，怕的是撑死。这个优先级定对了，贪心 AI 的死亡率立刻腰斩。
第二层是空间计数。
从蛇头做一次洪泛填充（flood fill），数一下走完这步后可达的空格数，和蛇的长度比。
可达空间小于身长，就意味着身体在可用空间里戳死了自己的一部分。这步再近也不能走。
两层检查都需要做几次小搜索，但网格只有几百格，洪泛是微秒级的。安全是用搜索换的。
第三条路
两个流派之外还有一条折中的工程路线：不做二元的安全判定，把多个指标加权求和。
每个候选方向算几个分。到食物的距离（负贡献）、走完后可达空间（正贡献）、离墙的富裕度、尾巴可达性。线性组合出总分，挑最高的走。
它比纯贪心多了全局视野，比哈密顿派灵活，实现也就几十行。
代价是权重需要调，而调权重是出了名的玄学。食物权重高一分就冲进死路，空间权重高一分就永远绕圈不吃。
实践中它常作为中等难度档位存在。比裸贪心体面，比完整的安全搜索便宜，恰好填满两个流派之间的空档。
短视贪心的极端形态可以在光轮对决（Tron）里看到原型：双方骑着光轮画墙，撞上任何轨迹即死。
它的 AI 每步只过滤掉立刻会撞的方向，剩下随缘直行、偶尔转弯。一层都不多看。
和它对局你能轻松赢，正好说明一层过滤在对抗性场景里多么不够。对手会利用你短视留下的空间陷阱。
这也是检验贪心改良的天然考场。把追尾检查和空间计数搬过去，立刻就变成一个体面的对手。真要较真，还可以加上”比较双方走完这步后的可达空间”这一条对抗性打分，那已经摸到本章末 Tron 策略的门了。
哈密顿回路的绝对安全
第二派思路干脆换掉了问题：与其每步决策，不如先在网格上构造一条经过所有格子的回路，让蛇永远沿着回路走。
这条回路就是图论里的哈密顿回路：经过每个顶点恰好一次的圈。
蛇头沿着回路前进，身后的格子必然按回路顺序逐一腾空，前方永远畅通。数学上保证永不撞墙、永不咬身，食物只是顺路的事。
在偶数边的矩形网格上，哈密顿回路很好构造。最朴素的是蛇形：第一行从左到右、第二行从右到左，如此折返到最后两列时用一条竖走廊接回起点，把所有行串成一个圈。
构造完，AI 的决策退化为零：每步沿回路挪一格。
代价也一目了然：慢。
食物刷在回路的下游一百格处，这条蛇就老老实实绕一百格才吃到。蛇形回路的节奏下，填满一个 20×20 的棋盘要几百上千步，全程观感像老牛拉磨。
安全性的极限是用效率换的。这就是两个流派的根本权衡：贪心的期望长度高、方差也高（会死）；哈密顿的存活率是 100%、期望用时惨不忍睹。
跑一万局，贪心 AI 可能平均长度四五十、偶发暴毙。哈密顿 AI 每局都满盘，但没有一局是快的。
回路 + 短路
实用的顶级贪吃蛇 AI 几乎都是两派的混血：平时沿回路走，但允许抄近路。
规则精巧而简单。给回路上的格子编号 0 到 n−1，蛇头当前在编号 h，尾巴在编号 t。某步若能沿回路外的一步跳到编号更大的格子，且跳过去的编号不超过尾巴的编号，这个近路就可以抄。
因为回路序保证了跳过的那些格子此刻都还是空的（它们在头尾之间的未来区段）。
近路让蛇在保持绝对安全框架的同时把平均用时砍掉一个量级。危险局面（空间紧张）时收紧抄近路的条件，退回纯回路模式，安全性立刻恢复。
这套框架保底、机会加速的结构，比纯粹的任何一派都强。它也是许多工程决策的通用形状：用一个不变量保证下界，在不变量的裕量里做贪心。
哈密顿回路是那个不变量。只要不离开它，死亡在逻辑上就被排除了。抄近路的所有自由度都被限制在不变量允许的范围里。
回路怎么画
哈密顿回路的构造本身要单独说一段，因为它有个新手必踩的坑。
蛇形折返谁都会画。第一行从左到右，第二行从右到左。难的是怎么把这条蛇的两端接回一起而不破坏每格一次。
对高度为偶数的网格，标准画法是留出最后一列做专用走廊。前面所有行在前 n−1 列里蛇形折返，走到左下角后沿最后一列一路向上，恰好把走廊格子串完、接回右上角的起点。
两个约束要同时满足。总格数为偶（回路长度必须是偶数，否则首尾相接时颜色错位，也就是网格图二染色在卡你）。走廊列单独预留（混进蛇形区就会自交）。
高度为奇数的网格更讲究，要靠在底部或侧面另接一条双格走廊来补救。
这个小构造是好例子：图论里哈密顿回路存在是一回事，画得出一条来是另一回事。后者才是工程。
两派怎么比
既然两个指标天然打架，比较策略就必须把考试设计好，否则哪个 AI 更强会沦为观感之争。
考试的三要素：跑批（几百上千局，食物随机性才能被平均掉）、分位数（报中位数长度而不是平均，死亡是重尾事件，几局超长存活能把均值拉得完全失真）、死因分类（撞墙、咬身、空间锁死、对战相撞分开统计，死因分布比总死亡率信息量大得多，它告诉你改良应该往哪个死法下手）。
跑完这套考试，两派的画像通常是这样的。哈密顿派中位数长度逼近满盘、死亡数为零、用时长得吓人。安全贪心平均用时短一个量级、长尾里偶尔暴毙。
先定义考场，再谈名次。这句对所有游戏 AI 都成立，对贪吃蛇只是格外刺眼，因为它的两个指标直接互斥。
借 A* 的眼睛看蛇盘
两个流派都用得上 A*，只是用法不同。
贪心派的改良版里，A* 负责算”绕开身体的真最短路”。把身体当障碍、食物当终点，比曼哈顿贪心少死很多次。哈密顿派的短路判断里，也需要可达性搜索兜底。
身体这个障碍有个独特的动态性质可以钻空子：蛇身每步都会腾出一格（尾巴离场）。所以严格来说障碍带时间维度，第 k 步之后的”那节身体”可能已经不在了。
简化实现常把尾巴格子视为可通行，或按”到达该格时它是否已让位”做时间展开。想做精确版，就是把每个格子按时间分层，复杂度乘上一个时间轴。这也是许多”动态障碍寻路”问题的通用建模。
基础搜索的扩展过程不熟悉的话，去最短路径可视化里画几堵墙跑几遍，比在蛇盘上直接调试舒服得多。25×25 的静态网格没有实时压力，每一步扩展都看得清清楚楚。
本站贪吃蛇还提供检验策略的环境变量。
经典模式适合观察贪心策略的死法分布。跑久了会发现死亡剧本高度重复。
竞速模式里速度随进食不断加快，短视决策的容错被进一步压缩，安全检查的价值被放大。
双蛇对战模式则把食物竞争和头对头相撞加进来。纯粹的贪心会为了抢食一头撞进对方蛇身，这时”空间计数”就从保险变成了攻击手段。故意把身体横在对方与食物之间，是用同一套算法反向设陷阱。
从贪吃蛇到 Tron
最后把镜头拉到光轮对决（Tron），它是贪吃蛇思想实验的纯净版。去掉食物与生长，只留下”画墙、别死、困死对手”。
在这个纯对抗版里，两个流派合流成一个核心判断：谁的可达空间大，谁赢。
开局双方空间对等，每一步的着法价值都可以用”走完后我方可达格数 − 对方可达格数”来打分。一旦一方把自己封进一个小隔间，败局就是倒计时。
这招叫领地比较，是 Tron AI 的标准起手式。其内核正是贪吃蛇改良版里那个洪泛计数，只是从”保命的保险”升格为”进攻的武器”。
实战里还有两个递进细节。
其一，领地比较只在双方区域还连通时成立。一旦墙把双方彻底隔开，比赛就变成两场互不干扰的”生存时长竞赛”，此时目标从压制对方切换为最大化自己的存活步数。
其二，优势方要把复杂度送给对手。故意走出让棋盘碎裂的着法，逼对方在残盘上先犯错。
领先时制造混乱、落后时求简化，这条对抗局的老规矩在纯空间游戏里执行得最赤裸。
两种 AI、一场对决，最终都落在同一个问题上：在一个不断收紧的约束空间里，激进的收益和保守的保障各值多少分。想检验自己对这两种策略的判断力，最快的办法是把本站这两块棋盘各挂机一小时：看贪心蛇的死法分布，看光轮 AI 的直行率。在这类游戏里，决定胜负的资源始终是空间。
汉诺塔：信任跳、下界与格雷码
从对抗退回地基。几乎所有算法课的第一道递归例题都是汉诺塔，这个安排看似俗套，实则精挑细选：递归解法只有三行，三行里藏着递归思维的全部关卡——怎么把问题缩小、什么时候敢停、凭什么信任那个”先假设子问题已解决”的跳跃。一块 汉诺塔 的三根柱子，能把递归这门手艺从信仰变成可以验算的工程。
递归三问
写递归之前先过三个问题，这是一切递归设计的固定清单。
终止条件是什么？子问题如何比原问题更小？子问题的解如何拼装成原问题的解？
三问答不出来，递归就是玄学；答出来了，代码只是翻译。
汉诺塔的三问答案严丝合缝。
任务定义：把 n 个盘从源柱移到目标柱，借助缓冲柱，大盘永压小盘。
终止：n = 1，直接移。
缩小：n 盘的问题被拆成”先把上面 n−1 个盘挪开”。n−1 盘的汉诺塔，同一个问题更小的实例。
拼装：三步走。
function hanoi(n, from, to, via): if n == 1: 移动 1 号盘 from → to; return hanoi(n-1, from, via, to) # 把上面 n-1 个盘让到缓冲柱 移动 n 号盘 from → to # 最大的盘此刻畅通 hanoi(n-1, via, to, from) # 再把 n-1 个盘从缓冲柱压上来注意第二步的底气：当 n−1 个盘全部堆在缓冲柱时，最大的盘可以合法移向任意柱。
整道题的钥匙就藏在这个观察里。“大盘永远畅通”的前提是”比它小的全部盘都未必在目标柱上”。
递归三问在此处各自落位：终止是平凡的移动，缩小是”处理上面 n−1 个”，拼装是”让出、落底、再压上”。
初学者的两个经典 bug 也恰好对准三问，提前点出来。
其一，把”移 n 号盘”塞进了子问题。写成先移最大的盘再递归，全然不管大盘上面还压着 n−1 个。这是”缩小”一问没答对：递归调用的前提（大盘裸露）在调用时并不成立。
其二，参数顺序传反。hanoi(n-1, from, via, to) 与 hanoi(n-1, via, to, from) 的四个位置极易抄错。源柱、目标、缓冲三者一旦错位，程序照跑不误，只是移动全部非法。
两个 bug 的共性相同：递归的参数是纯语义的，位置换来换去，语义错一点全盘皆错。写递归时把参数名的含义写在注释里，是比任何调试技巧都便宜的保险。
信任跳
三行代码写完，真正的难关才开始：你敢不敢不看它内部就相信它对。
人学递归最大的障碍是本能地想”展开追踪”。hanoi(3) 先进 hanoi(2)，hanoi(2) 又进 hanoi(1)。三层就开始糊，五层必然迷路。
而递归思维的全部要领就是拒绝展开。写 hanoi(n) 时，假设 hanoi(n−1) 已经是一个”你喊它就正确完成任务”的黑箱。你只负责安排它的调用时机与参数，以及它返回后你接着做什么。
这个”信任跳”不是心理安慰，它有严格的对应物：数学归纳法。
要证递归解正确，只需证两件事。n = 1 时正确（基例）。若 n−1 时正确，则 n 时正确（归纳步）。
第二条里”若 n−1 时正确”正是那个信任跳的形式化身。
归纳法之所以合法，是因为基例 + 传递性自动覆盖所有 n。递归之所以正确，是因为终止条件 + 调用自洽自动覆盖所有深度。
递归是归纳法的可执行版。这句话的反向读法更实用：任何你能对之做归纳证明的结构，几乎都能写成递归。反过来，一个让你无法完成归纳步的递归，多半真的有 bug。
信任跳还有个常被忽略的副产品：它决定了你和调试器的关系。
递归代码出 bug 时，单步展开到第三层就开始违背信任原则。正确的调试姿势是先查两样东西：终止条件会不会漏（无穷递归）、子问题的参数是否真的在缩小且语义不变（缩小失当）。
绝大多数递归 bug 出在这两处，而不是某一次具体的展开。
如果非要看运行过程不可，有个比单步追踪高效得多的土办法：按深度缩进打印。每层递归进入时打印两个空格缩进的一行日志，输出立刻呈现整棵调用树的形状，问题出现在哪一层的哪个分支一目了然。
这招在任何语言的任何递归上都通用，成本是两行代码。
2^n − 1
数步数是自然的下一步。
设 T(n) 为移动 n 盘的最少步数，递归解给出方程：
两次移 n−1 盘、一次移最大盘。逐项展开（或两边减 1 换元 ）立得 。
到这里通常就画句号了，但真正要再问一句的是：这是”我们的解法要这么多步”，还是”这个问题必须要这么多步”？
两者天差地别。前者只是某个算法的账单，后者才是问题的下界。
下界的证明恰好又是一次归纳，方向反过来。
要把最大的 n 号盘从源柱移到目标柱，那一刻它上面的 n−1 个盘必须全部堆在缓冲柱。若还有任何一个压在 n 号上，n 号不能动。若 n−1 个盘散在源柱与目标柱，目标柱顶也不是空的。
而把 n−1 个盘集中到缓冲柱，按归纳假设至少要 步。移完 n 号盘之后，那 n−1 个盘还得从缓冲柱全部压到目标柱，又至少 步。加上移 n 号本身的一步：
下界与上界在 处合拢。递归解就是最优解，一步不多。
这类”递归式的解同时是下界”的合拢是算法分析里最漂亮的结局。因为整条证明没有用到任何算法内部结构，只用了”大盘移动的前提”这一条规则本身。
把传说里的数字算清：64 个盘的 ，就算每秒移一盘也要五千多亿年。“移完世界毁灭”的印度传说，是在用天文数字演示指数的暴力。
规则的松动立刻检验这套分析法的成色。
给汉诺塔加第四根柱子，同样的下界推导直接失效。n−2 个盘可以分流到两根缓冲柱，“必须全部堆在一根柱上”的前提不再成立。
四柱汉诺塔的最优步数由 Frame–Stewart 算法给出。先挪 个盘到一根缓冲柱（用四柱规则递归）、再把剩下 n−k 个盘在三柱限制下压到目标柱、最后把那 k 个盘四柱归位，k 取让总数最小的值。
它的增长被压到约 。指数的指数被开了一次方，四柱情形的最优性后来被严格证明。
三柱与四柱之间这一对比，把”下界跟着约束走”演示得干干净净：证明不是套在算法上的模板，是读在规则里的推论。
还有一个少有人提的强化结论。汉诺塔不仅步数最优值确定，从任意合法局面出发，最优解法还是唯一的。
每个合法状态到目标的最短路上，任意时刻至多只有一个”不浪费步数”的合法移动可选。
证明的骨架与下界同源。任一局面下，把”最小盘”与”其余盘”分开看，非最小盘的合法移动至多一个（两个盘顶之间只有”小压大”一个方向可行，且三个柱顶里合法的去处唯一）。而最小盘的移动若偏离格雷码节奏，下一步必然要付出一步”摆回来”的返工。两轮里任何偏离都至少亏一步，最优轨道因此没有岔路。
这个唯一性把汉诺塔变成了一个完美的教学道具：学生走错任何一步，都确定地偏离了最优轨道，没有殊途同归来掩盖理解偏差。
不递归也能解
递归解之外，汉诺塔存在一套完全迭代的解法，规则短到可以背下来。
最小盘（1 号）每两步动一次，方向由 n 的奇偶决定。n 为奇数时永远朝目标柱方向轮转，n 为偶数时反向。
其余每一步，唯一合法的非最小盘移动就是正确移动。不涉及最小盘的合法移动在任何局面下至多一个（两个盘顶之间若都合法会互相打架，实际只有小的压大的这一个方向合法）。
循环执行”移最小盘 → 移唯一合法的那步”，直到结束，全程零递归零栈。
为什么”唯一合法”如此笃定？
任一时刻至多三根柱顶露着盘，涉及非最小盘的候选移动最多三对。其中”大压小”方向的一律非法。剩下的合法去向里又有一半会把最小盘压住或刚被最小盘离开。逐条排除后恰好剩一个。
这个”每步唯一”的性质也给了汉诺塔一个有趣的副产品：它是极少数闭着眼睛也不会走错的谜题。只要遵守两条规则，想犯错误都难，难度全在坚持走完 步的耐心上。
本站 汉诺塔 的自动演示正是按这类移动规律预生成整条移动序列再逐帧回放的。配合速度调节可以盯着最小盘的钟摆节奏看。它每两步换一次柱，永远不休息，这个规律性用肉眼就能确认。
这套迭代规律不是巧合，背后有严格的双射：汉诺塔的每一步对应 n 位格雷码的每一步加一。
格雷码（相邻两个码字恰有一位不同）的生成规则是”第 i 位每 步翻转一次”。最小盘（1 号）每两步动一次、2 号每四步动一次、3 号每八步动一次，与格雷码逐位翻转的节奏严格同构。
拿三盘的完整七步对一下表：移动序列是 1、2、1、3、1、2、1。第 k 步动几号盘，等于把 k 写成二进制后最低位的 1 在第几位。k=1（001）动 1 号，k=2（010）动 2 号，k=3（011）动 1 号，k=4（100）动 3 号，直到 k=7（111）动 1 号收官。
更进一步，任意时刻”哪个盘在哪个柱”可以直接从当前步数的二进制表示读出，反之亦然。
汉诺塔于是多了一重身份：它是格雷码的物理模型，就像二进制计数器的机械版本。
为什么存在零递归解法？递归解的调用树是确定的，拍平到一条时间轴上自然呈现周期结构。“递归表象”之下是”计数过程”的实体。
递归的成本核算
信任之外还得算钱。
递归的运行时成本在两个账本上：时间（调用次数）与空间（调用栈深度）。
汉诺塔的调用次数恰好也是 ，与移动次数一一对应。栈深度倒是只有 n。每层递归返回后栈帧就释放，最深的时刻是”从 hanoi(n) 一路进到 hanoi(1)“，n 个帧。
对比一下两种递归的形态。像阶乘那种”算完就返回、后面没事了”的线性递归可以靠尾调用优化把栈压到 O(1)。汉诺塔是”两次调用夹一次移动”的树形递归，中间那次移动挡在两次调用之间，尾调用优化无从下手。
想消栈就只能手工把调用树改成显式数据结构（队列或栈），而那样写出来的代码就是上一节那套迭代规律的手工版。
这解释了一个工程现象：为什么汉诺塔的迭代解不是递归转循环的机械产物，而是一条独立发现的规律。树形递归没有免费的拍平，拍平的代价是你得先看穿格雷码。
栈深度这个账本还回答一个常见疑问：汉诺塔递归会不会栈溢出？
n=64 也就是 64 层栈帧。深度从来不是问题， 次移动的时间才是。
分清”深度”与”次数”两个量纲，是评估一切递归算法的第一步。
递归三问的迁移
汉诺塔的三问模板立刻搬到别处验一遍成色。
树的遍历：终止是空树；缩小是”问题从树缩到左右子树”；拼装是”根的位置决定前序/中序/后序”。三问答完，六种遍历的代码自动长出来。
快速排序：终止是长度 ≤ 1；缩小是”按基准切成两半”；拼装是”左半 + 基准 + 右半”原地即合。注意它的”拼装”发生在递归之后（先处理再分治返回前合拢），而汉诺塔的移动夹在两次调用中间。这个先后差就是”分治后处理”与”分治中处理”的形状差。
谢尔宾斯基三角形之类的分形：终止是缩放极限；缩小是”取三份缩小的自己”；拼装是几何平移。
三个例子与汉诺塔共享同一条元规则：递归函数只对自己这一层负责，层与层之间的关系全部压在参数里。
参数语义一旦含糊（“这 n−1 个盘现在到底在哪个柱”），信任跳就跳不动了。汉诺塔的三参数签名 (n, from, to, via) 之所以是经典教材写法，正因为每个参数都是纯位置语义，没有一比特隐藏状态。
递归与 DP
汉诺塔讲透了递归，却恰好站在 DP 的门外。这个反例比十个正面例子更能讲清 DP 是什么。
动态规划生效需要两个条件。最优子结构：大问题的最优解由子问题最优解拼成。重叠子问题：递归展开时同样的子问题反复出现，缓存才有收益。
汉诺塔只有前者没有后者。hanoi(n−1, from, via, to) 在整棵调用树里只出现一次，没有任何重复子问题，记忆化一行都省不了。
它的时间复杂度 不是实现低效，是解的长度本身就是 。输出就有指数长，任何算法都逃不掉。
这种”复杂度被输出长度钉死”的问题，与上一张 DP 表能折叠的问题（比如下文 动态规划与并查集 一章里区间 DP、连通类 DP 的重复子问题）划出了清晰的界线。
同理，追问”汉诺塔能不能用 DP 加速”也就有了准确答案。不能加速解法本身，但”从任意局面到目标还差几步”这类查询倒是能预处理。把 个局面的步数表算出来后查表 O(1)，代价是指数空间。
用空间换时间的合同条款里，指数空间往往就是违约区。
两者的亲缘则在转换技巧上：自顶向下的递归与自底向上的填表是同一计算的两种遍历顺序。
DP 能把指数折叠成多项式，靠的不是”从递归变成循环”，而是重叠子问题让缓存命中。
判别一个递归能不能 DP，动手检查的方法极简。把递归调用的参数全部写下来，数一数有没有重复。有，去 DP 算法可视化 里找对应的表结构（背包、LCS、LIS、找零、区间、数位、状压、记忆化，八种常见的填表形态基本覆盖了入门到进阶的 DP 谱系）。没有，像汉诺塔一样，安心让递归裸奔，它已经是最优。
还能从状态空间的角度再核对一遍这笔账。
汉诺塔的全部合法局面共有 个（每盘独立选柱），而最优解只走 步。访问的状态数远小于状态总数。
递归解沿着格雷码轨道一次不回头的走法，意味着它天生长在”从起点数起第 k 步”这个一维参数上，而不是”局面”这个 维空间里。
DP 需要的恰恰是以”局面（子问题参数）“为节点的重叠结构。汉诺塔的调用树每个节点只出现一次，“以局面为键的缓存”无从谈起。
把”问题空间多大”与”解的路径多长”分开计量，是读任何递归算法复杂度的起手式。
汉诺塔这一讲留下三条结论：递归的信心来自归纳法，成本用下界清算，出路看子问题是否重逢。三根柱子、三条规则，把这门手艺能走的路（线性、指数、树形分解）与该让位的时候（重叠子问题出现时）都摆在了台面上。下一次写递归卡住时，先把问题摆成三问：终止在哪、怎么缩小、怎么拼装——三问落地，代码往往已经写完一半。
动态规划与并查集：一张表与一片森林
递归的出路看子问题是否重逢。重逢了，就有了动态规划（DP）——一种非常”懒”的思想：算过的别再算，大问题拆成已经算过的小问题，把”时间里的重复计算”折进一张静态的表。而结构本身随操作演化、集合不断合并的问题，“填表”无从谈起，要交给并查集（Union-Find）——用几十行代码撑起最小生成树、动态连通性一大片问题，把”不断合并的关系”挂上一片会生长的森林。本章把两个工具各自讲到能用，最后看它们在同一类问题里怎么协作。
上半场：动态规划
两个前提
一个问题能用 DP，必须满足两个条件，缺一不可：
- 重叠子问题：递归展开后，同一个子问题被反复碰到。这是”缓存有收益”的前提；
- 最优子结构：大问题的最优解由小问题的最优解拼成。这是”缓存最优值就够了”的前提。只需要记每个子问题的答案，不需要记得到答案的每条路。
反例能帮助理解：最长简单路径问题不满足最优子结构（两段最优路径拼起来可能成环、反而不是合法路径），所以”最长路”没有朴素 DP，最短路有。
条件是否满足，和问题的”长相”无关，和它的数学结构有关。
斐波那契的三级进化
第一级：朴素递归，。
fib(n) = fib(n-1) + fib(n-2) 直接展开，fib(n-2) 被算两次、fib(n-3) 三次……同一子问题爆炸式重复。
画出递归树，重叠一目了然。
第二级：记忆化，O(n)。
算过的存进哈希表，碰到就直接查。
改动三行代码，指数变线性。这就是”重叠子问题”兑现的价值。
自顶向下的写法保留递归直觉，适合先写出来验证。
第三级：制表 + 空间压缩，O(n) 时间 O(1) 空间。
自底向上把递归倒过来填表。再观察到 fib(n) 只依赖前两项，整张表可以砍成两个变量。
DP 的最终形态常常是”一张被滚动压缩的表”。这个压缩技巧在背包里是标配。
三级进化对应 DP 的完整心法：先写暴力递归 → 发现重叠 → 加缓存 → 倒过来填表 → 压掉不必要的维度。
每一步都机械，没有灵感的位置。
0-1 背包
n 件物品各有重量 w 与价值 v，容量 W 的背包，每件拿或不拿，求最大价值。
DP 的难点从不在代码，在状态定义。它必须同时回答”什么信息足够决定未来”。
背包的正解：
dp[i][c] = 只考虑前 i 件物品、容量还剩 c 时的最大价值。
有了定义，转移方程是”第 i 件拿不拿”的二选一取较大者：
第一项是不拿（与上一行相同），第二项是拿（腾出 wᵢ 的空间，换进 vᵢ 的价值）。
整个问题变成一张 n×W 的表，从上到下、从右到左填，右下角即答案。
滚动数组是这里的空间魔法：第 i 行只依赖第 i−1 行，二维表压成一维。
但内层循环必须倒着跑（从 c = W 到 wᵢ），否则 dp[c − wᵢ] 已经是”本行拿过”的值，等于允许一件物品被拿两次（那变成了完全背包。顺序一反，题目就换了，这个细节是背包系列最经典的坑）。
在动态规划演示里把背包跑一遍，盯着每个格子看它的值”从哪两个格子来”，转移方程就从公式变成了动作。
最长上升子序列
LIS（最长严格上升子序列）是”一维 DP”的最佳教材，因为它有两种复杂度悬殊的解法，恰好划出 DP 的能力边界。
O(n²) 的标准 DP：dp[i] = 以第 i 个元素结尾的最长上升子序列长度，转移 dp[i] = max(dp[j] + 1)，遍历所有 j < i 且 a[j] < a[i] 的位置。
状态定义里”以 i 结尾”这个限定是关键。它保证子问题有确定的接口，才能拼出大问题。
O(n log n) 的贪心 + 二分：维护一个数组 tails，tails[k] = “长度为 k+1 的上升子序列中，结尾元素的最小值”。
逐个扫描元素，用二分找到它该替换或追加的位置。
tails 数组始终有序，所以二分合法。
关键在于：tails 不是 DP 表。
dp[i] 的含义是”以 i 结尾的最优解”，tails[k] 的含义是”所有长度为 k+1 的方案里最小的结尾”。后者混入了全局信息，丢弃了”具体是哪条子序列”的路径。
这个对比划出的界线值得记住：DP 表的每个格子必须自足地回答子问题。
一旦某个更快的算法用了”全局混入”的中间量，它就已经不是 DP 了。更快，但更难扩展（比如要打印方案或允许修改区间时，O(n²) 版本反而好改造）。
零钱兑换
完全背包有个著名细节。
问题一：求”凑出金额 n 的最少硬币数”，一维表 dp[c] = min(dp[c − coin] + 1)，硬币外层、金额内层，顺序无所谓。因为 min 运算对交换律免疫。
问题二：求”凑出金额 n 的组合数”（1+2 和 2+1 算同一种），循环顺序突然变得要命。
硬币放外层得到组合数，金额放外层得到的是排列数。
原因在填表顺序里：硬币外层时，每种硬币的引入时刻是”分层”的，1+2 只会在处理 2 的时候被数到一次。金额外层时，每一步都可能用任何硬币，1+2 和 2+1 会被当成两条不同路径各数一次。
外层循环决定状态扩展的自由度，这就是题意的形状。
这是背包问题里最精巧的一课，也是”照抄模板不看顺序”会翻车的地方。
顺着 0-1 背包把整个家族盘一遍，四个变体差别只在”每件物品能拿几次”：
| 变体 | 每件物品 | 一维优化后的内层循环 |
|---|---|---|
| 0-1 背包 | 至多 1 次 | 倒序（防止本行值被重复使用） |
| 完全背包 | 无限次 | 正序（同一物品可叠加） |
| 多重背包 | 限 cᵢ 次 | 拆成二进制组后按 0-1 处理 |
| 分组背包 | 每组选一件 | 组外层 + 物品内层取 max |
同一张一维表，内层循环的方向和分层方式把四个问题分开。
这也是为什么理解”循环顺序即题意”比背四个模板划算。
区间 DP 一瞥
前面所有的表都以”前 i 个/第 i 行”为阶段。
还有一族问题的阶段是区间长度：小区间的答案拼出大区间的答案。
典型是最长回文子串：dp[l][r] 表示 s[l..r] 是否回文，转移只看两端字符是否相等、且内部子串是否回文。按区间长度从小到大填表。
石子合并、“吹气球”类问题同属此族。
区间 DP 的状态数是 O(n²)、转移 O(n)，虽然比线性 DP 贵一维，但骨架不变。
表 + 转移 + 填表顺序三件套原样适用，只是”阶段”换了个量法。
状态机 DP
有一类问题的状态不是”进度”，而是所处的模式。
经典例子是买卖股票的最佳时机（带冷冻期）：每天你要么持股、要么空仓，昨天卖了今天不能买。
把”持股 / 空闲”设成两个状态，表的两行就是两种模式，转移规则把交易规则直接翻译成代码：
持有[t] = max(持有[t-1], # 昨天就拿着 空闲[t-1] - 价格) # 今天买入空闲[t] = max(空闲[t-1], # 昨天就空着 持有[t-1] + 价格) # 今天卖出冷冻期只是给”卖出 → 买入”的边加一条延迟（卖出后先进”冷冻”状态一天）。
这类 DP 的要点是把约束翻译进转移而不是翻译进判断。
约束进转移，每个格子天然合法。约束留到运行时判断，代码就会长出一堆 if。
判断”是不是状态机 DP”的信号词是”处于 XX 状态时不能/只能 XX”。有它，先想状态机。
两张特殊形状的表
表的维度不总是”前 i 个”。
树形 DP把表挂在树的节点上：dp[节点][选/不选]，转移沿子树自底向上。
经典的最小点覆盖、最大独立集都是”每个节点二选一、父子互相约束”的模板，填表顺序就是后序遍历。
树没有”线性阶段”，但有”子树已算完”这个等价物，无后效性照样成立。
状态压缩 DP把”用过的东西”编码进下标：旅行商问题里 dp[访问过的城市集合][当前城市]，集合用一个整数的二进制位表示，n 个城市就是 2ⁿ 个集合。
它把”指数状态”从递归的调用栈搬进了显式的表，复杂度仍是指数（O(2ⁿ·n²)），但 n ≤ 20 量级时完全可算。
这也是为什么状压 DP 的题目永远把规模卡在 20 上下。
看到”n 很小 + 选与不选的组合”两个信号同时出现，就该往状压想。
调试三件套
DP 代码”逻辑对但答案错”时，按固定顺序排查：
- 打印小规模全表。n=4、W=10 这种规模手算得出全表，与程序输出逐格对比，第一处偏差的行列号会直接指出转移方程的错项；
- 暴力对拍。写一个纯递归暴力（不记忆化），在随机小输入上和 DP 比对。不一致的输入就是最小复现用例；
- 边界三连：空输入（0 件物品）、零容量、全部元素相同。转移方程的
i−1、c−w越界错和”恰好装满/不必装满”的初始化错（合法的”不可达”应初始化成 +∞ 而不是 0），九成藏在这三处。
自顶向下还是自底向上
两种写法等价，取舍很实际：
- 记忆化（自顶向下）：好写、只算需要的状态。状态空间里有一大块永远碰不到时（稀疏状态），它白赚。缺点是递归栈开销与爆栈风险。Python 里
functools.lru_cache一个装饰器就是现成的记忆化，适合先把正确性跑通； - 制表（自底向上）：无递归、空间可压缩、便于优化常数。缺点是会把用不到的状态也算掉。
面试手写推荐记忆化起步（正确性先落地），生产代码推荐制表（性能与内存可控）。
判断清单：这题能不能 DP
- 问的是最值/计数/可行性，而不是具体方案本身（方案可以最后回溯，但目标得是聚合量）；
- 写下状态后，未来与路径无关（无后效性）。给定 dp[i][c]，下一步的决策不需要知道 c 是怎么来的；
- 状态总数有限且不爆炸。DP 不创造复杂度，它只把指数的重复压成多项式的唯一计算；
- 转移能覆盖所有决策。每种选择都能从已有状态推出来。
四条都过，DP 基本成立。
卡在第 2 条时，通常要给状态加一维”携带必要的历史信息”。
维度上升、合法性恢复，是状态设计的常规手术。
换一个阶段
DP 表有个隐含前提：状态空间在动手之前就定死了。
可有一类问题的结构本身随操作演化。边一条条加进来、集合一个个合并、分组随事件漂移。
“填一张表”对它无从谈起。表是给”静态的问题”准备的，动态的关系需要能随操作增量维护的结构。
并查集就是这个结构，而且它恰好也有一个”从朴素到近乎常数”的三级进化，和 DP 的心法遥相呼应。
下半场：并查集
并查集（Union-Find / Disjoint Set Union）撑起 Kruskal 最小生成树、动态连通性、传递闭包一大片问题。
它的全部秘密藏在两个优化里：按秩合并和路径压缩。
想看着树怎么长的，本站的并查集可视化可以逐步操作。
问题与朴素实现
并查集维护”不相交集合”，支持两个操作：
find(x)：x 属于哪个集合（返回代表元）；union(x, y)：把 x 和 y 所在集合合并。
朴素实现给每个集合立一棵树：每个节点存父指针，find 沿父指针爬到根，union 把一棵树的根挂到另一棵树的根下面。
问题出在”挂”的方向随缘。如果总是把大树挂到小树下，链式合并后树会退化成一条长链，find 变成 O(n) 的爬楼：
1 → 2 → 3 → 4 → 5 （每次 find 都要从 1 走到 5）两个优化分别攻击这条链的两个属性：高度和路径。
优化一：按秩合并
挂树时不再随缘，而是矮树挂到高树下（用 rank 记录树高的上界；用集合大小代替 rank 的”按大小合并”效果类似）。
为什么树高是 O(log n)？
归纳一下：一棵 rank 为 r 的树至少包含 个节点。因为只有两棵 rank 严格小于 r 的树合并才会产生 rank r+1 的新根。
节点数至少指数于树高，反过来树高就是 O(log n)。
这一步把 find 从 O(n) 压到 O(log n)。
只做按秩合并的并查集已经能应付绝大多数场景了。但还有一半的红利没拿。
补充两个选择层面的细节。
其一，按秩和按大小二选一即可，渐近复杂度相同。按大小合并实现更直白（union 时比较集合元素个数，胜者为根，size 累加）。按秩合并不依赖”知道集合大小”的场景（比如元素带权、集合大小需要单独维护时，rank 语义更干净）。
工程里两者都常见，别纠结。
其二，一个看似矛盾的事实：这两个优化互斥地换了性质。加上路径压缩后，树的实际形态会被熨平，rank 里记录的高度信息从此失真，按秩合并退化成”按历史秩合并”。
它依然正确（证明里 rank 只需要是”上界”就够了），但这也解释了为什么可撤销并查集必须放弃路径压缩：撤销依赖”合并历史可回放”，路径压缩破坏了树的历史形态。
竞赛里的可撤销版本只保留按秩/按大小合并，单次操作 O(log n)，用栈记录每次合并的改动，回滚时逆序还原。
比”带压缩却撤不掉”的正确版本有用得多。
优化二：路径压缩
路径压缩攻击的是”重复爬楼”：既然 find(x) 反正要走到根，走完之后把沿途每个节点的父指针直接改指向根。
第二次再 find 这些节点，一步到顶：
压缩前： 1 → 2 → 3 → 4 → 5压缩后： 1 → 5 2 → 5 3 → 5 4 → 5单看一次操作，压缩只是顺手的动作。妙处在于它和按秩合并配合起来的摊还效果。
两者合用时，每次操作的摊还复杂度是 O(α(n))。α 是反阿克曼函数。
实战里最常见的写法甚至不是完整压缩，而是路径减半。只把当前节点跳到祖父，一行完成，渐近复杂度不变：
find(x): while parent[x] != x: parent[x] = parent[parent[x]] # 路径减半：跳到祖父 x = parent[x] return x配上按秩合并的 union，整个数据结构十几行、没有递归、没有爆栈风险。
工程上”当常数用”的底气就来自这份简单。
α(n) 是个什么怪物
阿克曼函数 A(m,n) 增长快到不能用初等函数描述，反函数 α(n) 则增长慢到离谱。
对 n ≤ （一个远超宇宙原子数的数字），α(n) ≤ 4。
所以实践中 α(n) 是不超过 4 的常数，并查集单次操作就当成 O(1) 用。
严格证明（Tarjan 1975 起，最终界为 α(n)）很长，但直觉可以一句话概括：路径压缩让”爬过长链”的代价只付一次，之后所有经过者都直达根。
按秩合并保证长链本来就难出现。
两个优化一个压高度、一个压路径，合在一起后树的形态会被操作历史不断熨平，任何节点到根的距离都小得可以忽略。
只压缩不按秩、只按秩不压缩，都到不了 α(n)。
前者最坏仍是 O(log n) 摊还，后者是 O(log n) 最坏。
红利只在合用时给足。
走一遍完整流程
以逐步合并 1-2、2-3、3-4、3-5 为例（按秩合并 + 查找时压缩）：
- union(1,2)：两棵单节点树，随便挂，1 为根，rank(1)=1；
- union(2,3)：find(2) 找到根 1；find(3) 是 3 自己；3 挂到 1 下；
- union(3,4)：find(3)=1，find(4)=4，4 挂到 1 下；
- union(3,5)：同样 5 挂到 1 下；
- find(5)：路径 5→1，两步；没有长链可压。
看得出按秩合并下树天然扁平，路径压缩在”链”出现时才发力。
比如所有元素串行 union 到同一个根上之后，一次 find 就把整条链拉平。
这两种场景都可以在可视化页面里手动复现。
Kruskal 完整走一遍，因为它最能说明并查集在算法里的位置。
n 个点 m 条边，按边权从小到大扫：每条边先 find 两端。同根则这条边会成环，跳过。不同根则 union，把这条边收进生成树。收满 n−1 条边即完成。
全程并查集只回答一个问题：“这两个点现在连通吗？”
没有它，Kruskal 每收一条边都得重新跑一遍全图连通性检查，复杂度直接爆炸。
“按序扫描 + O(α) 连通查询”这个组合，就是把贪心（按边权排序）变成可行算法的全部工程支撑。
用在哪
- Kruskal 最小生成树：按边权从小到大试边，并查集 O(α) 判端点是否已连通。并查集是这个算法成立的前提；
- 无向图判环：逐条加边，端点已同根的边就是环。Kruskal 判环用法本身；
- 动态连通性：不断加边、随时查询两点是否连通；
- 等价类合并：变量等价、集合划分、朋友圈之类的问题建模；
- 动态规划 + 合并：区间/连通类 DP 里用并查集跳过已合并的区间端点，把 O(n²) 压到近线性。见下文”会师”一节；
- 离线最近公共祖先（Tarjan 离线 LCA）：对树做 DFS，每离开一个节点就把它的子树”并”进自己。查询 (u, v) 的 LCA 时，v 所在集合的根恰好就是答案。DFS 的递归顺序 + 并查集的合并能力，把一个向上爬的问题变成”查根”的问题，是两者协作的经典范式。
带权并查集值得从清单里拉出来单独展开，因为它的建模思路最巧。
父指针上再挂一个”到父节点的权值”（年龄差、颜色差、分子分母比值都行），find 压缩路径时把沿途权值累加，union 时按”两个已知关系推第三个”把新权值解出来。
经典用法如”a 比 b 大 3、b 比 c 大 5，问 a 和 c 的关系”。把大小关系存成数值差，任何两点的相对值一次 find 就能算出。
它把并查集从”是否同类”升级成”同类之中相对关系是什么”，比例建模（a/b = 3 之类”除法求值”问题）换个权值语义照用。
工程实现上的两条零碎经验：用数组不用对象。parent/rank 用两个扁平数组、下标即元素编号，比对象图省内存且对缓存友好。
元素是任意字符串时先离线离散化成编号，让并查集只处理整数。这是”并查集只懂数组下标”带来的唯一适配成本。
两个顺手的附加信息也值得记下：分量大小。按大小合并时 root 处的 size 数组直接就是分量元素个数，统计”最大的朋友圈多大”零成本。
分量编号：扫一遍所有元素，root 首次出现的顺序就是分量编号，网格图着色、连通块标号类需求直接拿去用。
最后是一条边界认知：并查集只支持合并、不支持拆分。
“撤销某次合并”可以走可撤销版本，“删除某条边后重新回答连通性”则超出它的能力范围，那要换离线算法或更重的动态树结构。遇到这类需求先确认真的不能用”离线重排询问顺序”来绕。
Kruskal 的对手
最小生成树有两个旗鼓相当的算法，对比着看最能看清并查集的角色。
Kruskal 是”边视角”：全部边排序，逐条尝试，用并查集防止成环。它回答的问题是”这两个点是否已连通”。
Prim 是”点视角”：从任意一个点开始生长树，用小顶堆维护”树内到树外的横切边”，每次弹出最短的横切边、把新点收进来。它回答的问题是”离这棵树最近的下一个点是谁”。
Prim 根本不需要判环：树每次只长一个点，结构上不可能成环。
分工会自然浮现：稀疏图（E ≈ V）两者都好。稠密图（E ≈ V²）Prim 的堆操作 O(E log V) 与朴素实现 O(V²) 都占优，而 Kruskal 光排序就是 O(E log E)。被稠密图的边数放大。
所以”排序 + 并查集”的组合在稠密图上吃亏，这是并查集能力的边界之一：它擅长判定连通，不擅长配合”全局排序”吃下海量边。
岛屿计数
网格岛屿问题（‘1’ 是陆地，数连通块）是观察两种工具差异的最小样本。
DFS 洪泛：每个未访问的陆地格子发起一次 DFS，把整个岛染色标访。时间 O(格子数)，代码五行为。
并查集：扫一遍格子，每个陆地格子与”上方、左方”的陆地格子 union，最后数不同根的个数。同样 O(格数 × α)，但多一趟收尾。
静态网格上 DFS 通常更省事。
并查集的价值在动态：陆地格子一块一块地”涨出来”（每次加一格问当前岛数），DFS 每次都要重扫全图，并查集只做一次 union、O(α) 出答案。
这印证了并查集的定位：它不是求连通分量的最快静态工具，它的正确位置是连通性在时间中演化这类问题。
选型时先问一句：连通关系会不会增量变化？会，才轮到并查集。
会师：DP 遇上并查集
两个工具的交点在区间/连通类 DP：填表时经常发现”一段区间的所有端点其实已经等价、可以整体跳过”。
“等价且可整体跳过”正是并查集的本职。
把”已合并的区间”记进并查集，填表遇到已合并的区间就顺着根跳到下一个未处理位置，内层循环从”逐格扫”变成”逐块跳”，O(n²) 压到近线性。
本章开头的演示展示的正是这类协作：看填表顺序怎么被合并操作加速。
Tarjan 离线 LCA 是同一模式的另一例：DFS 负责遍历顺序，并查集负责”子树已访问”的合并记账。
选择的心法由此清晰：问题是静态的、状态空间可预先圈定 → 上 DP 表；关系在操作中演化、只需要同不同类的答案 → 上并查集；两者同时出现 → 让并查集当 DP 的加速器。
小结
| 工具 | 核心动作 | 复杂度进化 |
|---|---|---|
| 动态规划 | 填表：子问题答案存格子里 | 指数递归 → 线性（缓存）→ 常数空间（滚动压缩） |
| 并查集 | 合并：find 查根、union 挂树 | 最坏 O(n) → O(log n)（按秩）→ O(α(n))（+路径压缩） |
DP 这一讲的核心是缓存与状态设计——斐波那契给骨架，背包给灵魂，“表是几维、每个格子从哪几个格子来”是万能起手式。并查集这一讲的核心是增量维护——两个简单优化单独看都只是常数级的小聪明，合在一起却把复杂度推到理论极限。下次遇到新题，先分清它要的是”一张表”还是”一片森林”；两者同时需要的时候，你已经知道它们怎么握手。
序的建立与维持：排序与红黑树
并查集回答同不同类，排序回答”谁大谁小”。“排序算法是每个程序员的必修第一课”，但排序只负责一次性把序建立起来；数据要持续增删、随时查询”第 k 小 / 比它大的最小是谁”时，责任就从算法转移到数据结构。本章上半场讲排序——三大门派、一条下界、若干名坑；下半场讲红黑树——怎么在任意插入序列下持续维持”矮胖的序”。两个舞台共享同一个主角：序。
上半场：排序
排序算法被讲烂了。名字能背一串，直觉未必建立。
换个组织方式：不逐个介绍，而是分成三大门派，每个门派都是对上一代痛点的回应。
门派一：插入系
思路：左边一段保持有序，逐个把新元素插进去。
- 插入排序：从左往右扫，把当前元素在有序前缀里挪到该在的位置。最坏 O(n²)，但有一个被低估的美德：自适应性。输入越接近有序，它越接近 O(n)。近有序数据（日志追加、几乎有序的流）上它是最快的比较排序之一，而且常数极小、稳定、原地；
- 希尔排序：插入排序的远程版。先按大步长做插入（远距离元素先大致归位），步长逐轮减半，最后一轮等价于普通插入排序，但此时数组已近有序。用”预排序”喂饱插入排序的自适应性。
插入系的宿命是元素只能一步步挪（每次移动消一个逆序对），n² 是这门派的天花板。
门派二：分治系
n² 的根源是”每次只消除一个逆序”。
分治系直接换思路：把数组拆成两半分别排好，再合并。
- 归并排序：拆到最小、两两合并（两个有序数组合并是线性的）。无论输入长什么样，稳定 O(n log n)。这是它的招牌，代价是 O(n) 的辅助空间和”对缓存不友好”的合并扫描。它还带来两个副产品：稳定性（相等元素保序）和天然的外排序能力（磁盘数据分块归并）；
- 快速排序：不合并、先分区。选一个基准，小的甩左边大的甩右边，递归两侧。分区是原地的，省掉辅助数组，缓存局部性极好，实践中常数最小。但分区质量看基准运气：总选到极值就退化成 O(n²)。随机选基准（或三数取中）把期望拉回 O(n log n)，最坏概率低到工程上可忽略；
- 内省排序（Introsort）：快排开头、递归过深时切堆排兜底、小块切插入排序收尾。C++ 标准库的 std::sort 就是这个三合一，把三大门派的优势缝在一起；
- Timsort：现代语言标准库的另一个答案。Python 的
sorted和 V8 的Array.prototype.sort都是它。思路是反着的：不强制拆数组，而是找出数据里天然有序的段（run），短段用插入排序补齐，再把 run 归并起来。近有序的真实数据（几乎总是如此）上大量 run 本来就长，排序快得接近 O(n)。它是归并系的骨架、插入系的自适应，混血混到了点子上。
稳定性为什么值钱：多关键字排序靠它。
先按部门排一遍，再用稳定排序按姓名排，部门顺序在同名内部自动保留。
不稳定的快排做这件事会把第一遍的结果搅乱，只能打包成复合键一次排。
门派三：选择系
思路：每一轮从无序区选出最值放到端上。
- 选择排序：朴素实现，永远是 O(n²) 且不自适应，实战少用。但它是最稳如泰山的教学模型；
- 堆排序：把挑最值升级成用堆挑。建堆 O(n)，每次取最值 O(log n)，总 O(n log n)、原地、辅助空间 O(1)。代价是跳跃式访问对缓存极不友好，实测常常输给快排，于是退居”兜底”角色（Introsort 的保险丝）。
一条下界
为什么绕来绕去都是 O(n log n)，没人更快？
决策树论证一页纸。
把比较排序看作一棵二叉决策树。每次比较是一个分叉，叶子上是最终的排列结论。
n 个元素有 n! 种可能排列，每种都必须对应树里至少一个叶子（否则两种排列无法区分，必有一种排错）。
二叉树要长出 n! 个叶子，高度至少 log₂(n!)。
用斯特林公式展开：
任何只靠比较的排序，最坏情况都逃不脱这条下界。
快排、归并、堆排恰好都贴着它，所以它们已经是最优的比较排序。
绕过下界
下界的前提是”比较”。每个比较只输出是/否，信息量 1 bit。
计数排序直接不用比较：值域 [0, k] 时，数一遍每个值出现几次，按序展开，O(n + k)。
基数排序再进一步：多位数从低位到高位逐位做稳定计数排序，O(d·(n + k))。
它们能突破 n log n，因为用”值域知识”换掉了比较的通用性。
知道元素长什么样，就不必问元素谁大谁小。
代价也明显：只适用于整数/可映射整数的数据，且值域过大时空间失效。
通用与专用，永远是这一对矛盾。
这条路上其实还有第三种走法：桶排序。
把值域均匀切成 k 个桶，元素按值扔进对应桶，桶内各自排序（常用插入排序）后按序拼接。
当输入近似均匀分布时，每桶期望只有常数个元素，整体期望 O(n)。
它与两个兄弟的关系摆在一起看：计数排序是”每格一个值的极端桶”（桶内免排序），基数排序是”按位反复分桶”，桶排序是”按值分段、桶内交给比较排序”。
三种非比较排序共享同一个思想：用分布知识换掉比较。只是把”知识”用在了值域的不同粒度上。
分布严重不均匀时桶排序退化（所有元素挤进一个桶），这也是”非比较排序都要看数据长相”的又一例。
一张完整速查表
把三大门派加非比较系的属性摊开：
| 算法 | 平均 | 最坏 | 额外空间 | 稳定 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳 |
| 希尔排序 | 取决于步长 | 取决于步长 | O(1) | 不稳 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳 |
| 快速排序 | O(n log n) | O(n²) | O(log n)（递归栈） | 不稳 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳 |
| 基数排序 | O(d·(n + k)) | O(d·(n + k)) | O(n + k) | 稳 |
两个格子里藏着微妙之处：希尔排序的复杂度写”取决于步长”，因为不同步长序列的最坏界不同（原始步长最坏 O(n²)，更精细的序列能压得更低）。
快排最坏 O(n²) 指确定选基准的版本，随机化后最坏情形概率上可忽略，期望就是 O(n log n)。
稳定性一列直接决定了多关键字排序能不能做（见前文），常被当成无关紧要的注脚，实际是选型的硬约束之一。
“不稳”的具体成因也值得看一眼，因为它解释了为什么不稳定难以修复：快排的分区做长距离交换（把远处的元素甩到基准另一侧），相等元素的前后顺序在交换瞬间就被打乱，事后无法恢复。
堆排则是出堆时”堆顶和堆尾交换”，同样是大跨度挪动。
归并的合并只在相邻有序段之间进行、插入只挪动一格。小跨度动作天然保序。
所以”给快排打稳定性补丁”的标准做法不是修快排，而是给每个元素附上下标、把比较键扩成（值, 下标）。用额外信息换稳定性，代价是空间和常数。
内存装不下怎么办
前面全部假设数据在内存里。
数据大到装不下时，归并的门派优势变成了唯一解：外部归并排序。
三步：把文件切成内存装得下的块，逐块读入排序写回（块内随便用快排）。然后用 k 路归并把排序好的块合并：每次从 k 个块的头元素里挑最小的写出（用一个小顶堆维护”当前 k 个头”，每次取最小 O(log k)）。重复直到合并完。
总 I/O 次数与”块数 = N/M”（M 为内存大小）成正比，加大 k 能减少归并轮数。
这就是磁盘时代”多路归并”里那个”多路”的由来。
这也是前文说归并天然的外排序能力的完整含义：它是唯一一个顺序扫描就能合并的排序，而磁盘最擅长的恰是顺序读。
逆操作：洗牌也有正确姿势
排序的反问题是洗牌，而且它有一个”多数人的写法是错的”的名场面。
朴素思路”每张牌和一张随机选的牌交换”不均匀：它产生 nⁿ 条等概率交换路径，而均匀洗牌要求 n! 条排列各占 1/n!。
nⁿ 不整除 n! 的余数让某些排列系统性偏多。
正确的是 Fisher–Yates：第 i 轮只从剩余未处理的牌里随机选一张换到位置 i。恰好产生 n! 条等概率路径，每张排列概率精确相等，O(n) 一遍完成。
反向思维也常用：给每个元素配一个随机键、按键排序（sort-by-random-key）。省事，但要小心键相撞（并列时排序稳定性会引入偏差）和浮点键的精度。
洗牌的正确性证明和排序的下界证明共享同一个计数直觉：数清楚每条路径对应多少个结果，偏不偏一目了然。
比较器的坑
所有比较排序对比较器都有一条隐含契约：严格弱序（strict weak ordering）。
a 与 b 不能”互不小于”，且”小于”必须可传递。
工程里最常见的两种违约：把 a < b 写成 a <= b（相等的元素互相”小于”，破坏不可比性）。比较器依赖了排序过程中会变化的量（比如用带副作用的 getter 或未取整的浮点做键，NaN 与任何值比较都是 false，直接破坏传递性）。
违约的后果不是”结果稍微不对”，而是未定义行为。
库实现的快排/内省排序假设比较器守法，分区指针会越过彼此，典型症状是越界写内存、程序崩溃。
C++ 世界里”比较器写错导致 segfault”是流传几十年的经典事故，而且崩溃点随机、难复现。
三条守则可以避开全部已知坑：比较器只用 < 不用 <=。比较键在排序前先算好、存下来。浮点键先处理 NaN（或换成”精确键 + 浮点展示”）。
相反方向的一个优化：比较本身很贵时（超长字符串、复合键），别让排序反复调用比较器。
先给每个元素算一次键（或配上下标），对轻量的键排序，最后按索引重排原元素。
把”比较的次数”压到下界的同时，把”每次比较的成本”也压下来，两本账分开算。
在排序可视化里把几个算法放在同一份数据上跑，重点看两件事：近有序数据上插入排序的”几乎不动”，和快排分区的”大规模跳跃”。
对比过一次，选型表就长在直觉里了。
序建好之后
排序解决的是手头这一批：一次算完，从此不变。
可真实系统里数据是活的。新记录不断插入、过期条目不断删除，而业务随时要问”比这个值大的最小元素是谁”。
排好的数组插一个元素要挪动后半段，O(n) 一步。增删一频繁，“排一次序”的策略就破产了。
这时需要的是每次操作之后仍然有序的结构。
二叉搜索树把”有序”从一次性动作变成持续性质：左子树 < 根 < 右子树，查找、插入、删除都是 O(log n)。
前提是树不退化。
下半场的主角红黑树，就是”怎么保证它永不退化”的标准答案。
下半场：红黑树
红黑树大概是数据结构课里劝退率最高的内容：插入要染色、删除要讨论八种情况、性质背了忘忘了背。
但它的设计动机其实异常朴素：给二叉搜索树上一条”高度保险”。
不背口诀，从问题出发把它重新推一遍。
问题：BST 会退化
二叉搜索树（BST）的查找成本等于树高。
理想情况下 n 个节点高度 log n，但 BST 的形态取决于插入顺序。按序插入 1,2,3,…,n，它就退化成一条链，查找 O(n)。
需要一种机制，让树在任意插入序列下都保持矮胖。
主流方案有两族：强制完美平衡（AVL，任意节点左右子树高度差 ≤ 1），或者只保证”大致平衡”（红黑树）。
红黑树的选择是后者。它能松到什么程度、又能严到什么程度，全写在五条性质里。
五条性质与它们的分工
红黑树给每个节点标红或黑，要求：
- 每个节点非红即黑；
- 根是黑；
- 叶子（NIL 空指针）算黑；
- 红节点的孩子必是黑（不存在连续两个红）；
- 从任一节点到其所有后代叶子的路径上，黑节点数目相同（黑高相等）。
五条里真正干活的是 4 和 5。
从它们能推出核心定理：
红黑树的高度 ≤ 2·log₂(n+1)。
证明一行就能说清：性质 4 禁止连续红，意味着任何路径上红节点数 ≤ 黑节点数。
性质 5 说所有路径黑高相同，而黑高为 bh 的树至少有 个节点（满二叉树的下界）。
两边一夹：最短路径全黑（长 bh），最长路径黑红相间（长 2bh），最长不超过最短的两倍。
树是”大致”矮胖的。
看清楚了这个证明，就明白红黑树的设计哲学：不追求完美平衡，只追求”最长路径不超过最短路径两倍”。
这个松一档的约束换来的是后面要讲的低维护成本。
还有一个把谜底彻底揭穿的视角：把每个红节点吸进它的黑父节点里（红边合并、节点变成多键），红黑树就变成一棵 2-3-4 B 树。
2 节点、3 节点、4 节点恰好对应黑节点带零个、一个、两个红孩子。
红黑染色不是玄学，是把多路 B 树的平衡性用二叉形式编码的记号：性质 4 和 5 合起来，正是”B 树所有叶子等深”在二叉世界的翻译。
从这个视角看，插入时的”染色上移”就是 B 树的节点分裂，旋转只是分裂在二叉表示里需要的机械动作。
很多”为什么规则长这样”的疑问，到这里一并化解。
旋转
维持性质靠两种局部手术。
染色是免费的。
旋转是真正的结构变更。它把”父-子”关系绕轴翻转，让一边高度降一、另一边升一，而 BST 的中序序不变。
这正是旋转的精髓：它是唯一能调整树高又不动”排序性质”的操作，且成本 O(1)、只涉及三个指针。
手推一遍左旋，指针操作就三步。
以 x 为轴左旋（右孩子 y 上浮）：
x y / \ / \ a y → x c / \ / \ b c a b中序遍历两边都是 a、x、b、y、c。序不变是旋转合法性的全部依据。
指针操作：① x 的右指针改指 b（把 y 的左子树过继给 x）；② y 的左指针改指 x；③ x 原来的父节点改认 y。
三个指针写完，x 的高度降一、y 的高度升一，其余世界纹丝不动。
右旋完全对称。
在可视化页面上手动转几次，体会”序不变、高互换”。
所有平衡树的自我修复（AVL、红黑、Treap）用的都是这同一把手术刀。
插入
新节点一律先染红插入。
为什么？染红只可能违反性质 4（出现双红），绝不会碰性质 5（黑高没变）。
染黑则每条路径黑高都变，全局受损。
所以插入的修复问题被压缩成单一的”修双红”。
修双红只有两种情形：
- 叔叔是红：把父亲和叔叔染黑、祖父染红。黑高不变，冲突上移两层。可能一路顶到根，最后根染黑收尾；
- 叔叔是黑：通过一到两次旋转 + 染色，把”之字形”转成”直线形”再转正。局部修完，整个修复终止。
黑叔叔情形画出来看，因为”之字转直线再转正”这两步旋转让很多人背得痛苦。
设新节点 z、父 p、祖父 g（p 为红、g 为黑、叔叔为黑）。
z 和 p 的关系只有两种：
- 直线形（z 与 p 同侧，比如都是左孩子）：对 g 做一次右旋（朝 p 的反方向），p 升到 g 的位置，然后 p 染黑、g 染红，结束；
- 之字形（z 与 p 异侧，p 左孩子、z 右孩子）：先对 p 做一次左旋，把之字压成直线。现在 z 变成 p 的父辈、仍与 g 同侧。再套用直线的处理（对 g 右旋 + 染色），结束。
记忆要点：之字形永远先转成直线，直线形永远一次旋转终结。
两步旋转恰好对应”插入至多两次旋转”的上界，而两步旋转后必须染色两次（p 黑 g 红），把黑高重新配平。
手推两次这个过程，删除情形里的”旋转方向”问题会一并想通。它们是同一套几何。
关键差别在终止性：红叔叔情形向上冒泡，黑叔叔情形原地终结。
所以插入至多两次旋转、O(log n) 次染色。
染色便宜，旋转昂贵，插入的红黑树用昂贵的操作换便宜的操作。
删除
删除比插入麻烦（删黑节点会破坏黑高），要处理”双重黑”的传递，情形分得多但骨架相同：能染色就染色上移，不行就旋转终结。
工程实现里这就是那”著名的八种情况”。
把”八种情况”的骨架抽出来其实只有三类。
删掉黑节点后，经过被删位置的路径少了一个黑。把这个亏空记成”双黑”，向下传给接位的节点：
- 兄弟是红：旋转变色把红兄弟转上去。双黑没消，但兄弟换成了黑的，转到下一类；
- 兄弟是黑、两个侄子都黑：把兄弟染红，“双黑”与兄弟的黑在父节点合并抵消一层。父节点要么结束（父原本是红，改黑补亏空），要么继承双黑继续上移；
- 兄弟是黑、侄子有红：按红侄的位置做一到两次旋转加染色，亏空就地补齐，修复终止。
“最多三次旋转”的上界就来自这个结构：情况 1 至多做一次（随后进入 2 或 3），情况 2 是纯染色上移（无旋转），情况 3 至多两次。
染色沿树向上传 O(log n) 次，但旋转这种昂贵操作被压到了常数。
为什么是红黑树而不是 AVL
AVL 严格平衡（高度差 ≤ 1），查找确实略快。但它的维护代价高。插入可能触发 O(log n) 次旋转，删除同理。
红黑树反过来：查找路径最多多一倍（还是对数，常数小），插入至多 2 次旋转、删除至多 3 次，其余全靠染色。
工程权衡的天平倾向红黑树，因为典型负载是读写混合而不是纯查找。
修改频繁时，红黑树省下的旋转次数远超查找路径加长的损失。
加上实现经过几十年打磨（删除的情形处理高度模式化），它成了标准库的默认选择：C++ 的 map/set、Java 的 TreeMap、Linux 内核的 CFS 调度器数据结构，都是红黑树。
想自己动手实现的话，值得看一眼左倾红黑树（LLRB）：把”红边一律左倾”加进不变量，插入只需二十来行、删除的情形也大幅收缩。
这就是上面那个 B 树视角推到极致（只模拟 2-3 树）的结果。
标准库没有用它，更多是历史与路径依赖，而不是技术否定。
两族的账可以列成一张表，省得在”哪个更好”上空对空：
| AVL | 红黑树 | |
|---|---|---|
| 高度上界 | ≈ 1.44·log₂(n+2) | ≤ 2·log₂(n+1) |
| 插入旋转 | 至多 1 次（单旋或双旋） | 至多 2 次 |
| 删除旋转 | 最坏 O(log n) 次 | 至多 3 次 |
| 查找 | 略快（更矮） | 略慢（常数级） |
| 适合负载 | 读多写少 | 读写混合 |
取舍上，AVL 偏读优化，红黑树读写均衡。
和数据库索引选 B+ 树而不是完美平衡树，是同一种工程智慧。
实现层面还有两个工程惯例。
一是哨兵 NIL：与其让每个叶子有两个空指针、处处判断”是不是空”，不如用一个共享的黑色 NIL 节点代替全部空指针。所有叶子的孩子都指向它，染黑逻辑统一、判断分支减半，代价只是一个常驻对象。
二是parent 指针不能省：插入和删除的修复都要从当前位置向上找父、祖父、叔叔，没有 parent 指针就得自带一条搜索路径栈。
标准库实现清一色带 parent 指针，教科书上的”三个指针域”就是这么来的。
替代方案一瞥
平衡树不是”有序字典”的唯一答案。
**跳表（Skip List）**用完全不同的路线达到同一个复杂度：底层是一条有序链表，向上抽取逐层稀疏的”快速通道”，查找从顶层开始横向走、走不下去就下一层。
期望 O(log n)，靠概率维持平衡，完全没有旋转和染色。
它抢走红黑树一些地盘的原因有三：实现简单得多（没有删除情形的八种分类，插删只有”抛硬币定层高 + 改指针”）。范围查询天然顺手（定位到起点后沿底层链表顺序走即可，树要做中序续算）。按排名查询（“第 k 小”）加个层宽字段就支持。
Redis 的有序集合（zset）选跳表而非红黑树，公开给出的理由正是实现简单与范围操作顺手。
对这个场景，工程优雅压过了理论优雅。
反过来看红黑树守住的地盘：内存紧凑（跳表每个节点要多层前向指针，空间常数更大）、最坏情况有保证（跳表是期望 O(log n)，靠随机性，理论上没有硬上界）、缓存更友好。
所以”需要范围操作、追求实现简单”时看跳表，“要最坏保证与内存紧凑”时看红黑树。
和本章反复出现的主题一致：数据结构选型是需求匹配，不是排名。
在红黑树旋转可视化里做三件事：连续插入升序数据，看树怎么靠旋转保持矮胖。找到一次”叔叔为红”的插入，看冲突怎么向上冒泡。再找一次”叔叔为黑”的插入，看一两步旋转怎么就地终结。
三件事看完，五条性质就不再是需要背诵的条文，而是这套机器的运行日志。
小结
| 需求 | 默认选择 |
|---|---|
| 一次性排序，通用平均最快 | 快排（随机化）或 Introsort |
| 要稳定、要最坏保证 | 归并 |
| 内存极紧 | 堆排 |
| 近有序小数据 | 插入 |
| 整数、值域可控 | 计数/基数 |
| 数据持续增删、随时要查序 | 红黑树（读写混合）/ AVL（读多）/ 跳表（重范围操作） |
排序与红黑树分别处理序这道题的两个阶段：排序回答”怎么一次性把 n 个元素摆好”，有下界 O(n log n) 压阵；红黑树回答”怎么让序在增删中永不失守”，靠”最长路径不超过最短两倍”的松约束兜底。把两场仗放在一起看，序从一次性的动作变成了可以持续维护的性质。
搜索的骨架：从遍历到博弈
排序与红黑树维持的序还是静态的；搜索则是算法世界的主旋律，而且只有一个基本形：维护一个候选容器，反复”取出一个、放进它的邻居”。取出顺序不同，就得到不同的算法——从”看遍整个图”的遍历，到”只找最好那条路”的最短路，再到”图另一头站着会反击的对手”的博弈搜索，三代问题、同一副骨架。
第一层：遍历
遍历要解决的核心问题是别走回头路。
图不是树，边可以成环，没有标记的话会在环上打转。
所以骨架的第一块积木永远是 visited 标记。
第二块积木是一个候选容器：存放”已经发现、还没处理”的节点。
整个循环只有一个：
把起点放进容器并标记while 容器非空: 取出一个节点 v，处理它 把 v 的所有未标记邻居放进容器并标记伪代码里留了一个空：“取出”取哪个？
从容器头部取，是 BFS；从尾部取，是 DFS。
算法的全部差异就藏在这个取出顺序里。
BFS：队列，按层扩散
容器是先进先出的队列时：起点的直接邻居先全部处理完，才轮到”邻居的邻居”。
扩散是按与起点的距离一层一层进行的，像水波纹。
这决定了 BFS 的招牌性质：在边权相同的图里，第一次到达某节点时，走的一定是最少边数路径。
直觉解释：节点按距离分层入队，距离为 d 的层全部处理完之前，距离 d+1 的层根本不会出队。
第一次摸到目标时，不可能存在更短的路线没被摸过。
BFS 的主场问题由此确定：无权最短路（迷宫最少步数、跳棋最少步数、社交网络里的几度人脉）。
推论也顺手可得：把”起点 → 每个节点第一次被谁发现”记下来，就得到一棵以起点为根的最短路树。
DFS：栈，扎到底再回头
容器是后进先出的栈时（递归写法的函数调用栈就是它）：刚发现的邻居立刻被跟进，一路扎到底，无路可走才回退一步换条岔路。
探索形态是一条不断伸出又缩回的触手。
DFS 不保证任何”最”字，但它自带另一种结构信息：回退的时刻就是子树完成的时刻。
递归进入节点时记一个”进戳”、回退时记一个”出戳”，两个时间戳一夹，能得到一堆 BFS 给不了的东西：
- 拓扑排序：按出戳降序排列，就是 DAG 的合法执行顺序（构建系统、任务调度依赖它）；
- 环检测：遇到一个”还在栈里”（已进入、未离开）的节点，必有环；
- 割点/桥：进戳与邻居可达的最早进戳比较，定位网络里的单点故障。
分工很清楚：BFS 回答”多远”，DFS 回答”什么结构”。
怎么选
- 问”最少几步”且边权相同 → BFS，没有第二选择；
- 问”是否存在路”（连通性）→ 都行，DFS 代码更短（递归三行）；
- 问”顺序/依赖/环” → DFS，因为它的时间戳结构；
- 边权不同 → 两者都不对，那是 Dijkstra 的领地。见第二层。
复杂度两者相同：每个节点进出容器一次、每条边看两次，O(V+E)。
空间上 BFS 最坏要装下一整层（稠密图上是 O(V)），DFS 装的是当前路径深（最坏也是 O(V)，但平均浅得多）。
迷宫超大时这是实际考虑项。
骨架的三个变体
同一副骨架改造出几个高频变体：
- 多源 BFS。把起点换成一整层起点。迷宫的所有出口、腐烂橘子问题里的所有烂橘子。一开始就全部放进队列，扩散照旧。第一次摸到某个节点时的距离，就是它到”最近源”的距离。单源 BFS 回答”离起点多远”，多源 BFS 回答”离最近的源多远”，后者在现实问题里出现得更频繁；
- 二分图染色。BFS 按层扩散时顺手给层号标奇偶（或红绿交替着色），扫到一条边连接两个同色节点，图就不是二分图。“能不能分成两组、组内无边”这类问题（排课、组队）不需要任何新结构；
- 连通分量计数。外层套一个”还有没访问过的节点就再跑一遍遍历”的循环，跑了几遍就有几个分量。BFS、DFS 谁来跑都一样，骨架照旧。
还有一个工程层面的提醒：DFS 的递归深度。
链状图上递归 DFS 的栈深等于节点数，几万节点的图足以把默认栈打爆。
生产代码要么改显式栈的迭代写法，要么换 BFS。
双端队列与入度表
0-1 BFS 补上了 BFS 和 Dijkstra 之间的空档。
当边权只有 0 和 1 两种（网格里”平地走一步、传送门免费”这类），优先队列都嫌重。
把普通队列换成双端队列，走 0 权边到达的节点从队头进，走 1 权边的从队尾进。
队头到队尾的距离差永远不超过 1，取出顺序依然正确。
复杂度还是 O(V+E)。
至此”取出策略”的谱系完整了：队列（边权全 1）→ 双端队列（边权 0/1）→ 优先队列（任意边权），一副骨架换三种容器。
Kahn 算法是拓扑排序的另一个入口，而且完全是 BFS 骨架。
统计每个节点的入度，把入度为 0 的（没有任何前置依赖的）放进队列。
每次取出一个、把它指向的所有节点入度减一，减到 0 就入队。
出来的顺序就是合法执行顺序。
它和 DFS”出戳降序”殊途同归，但多送一个赠品：如果处理完的节点数少于总节点数，剩下的节点构成环。
排序和环检测一次完成，构建系统的依赖检查通常用它。
网格上的实现细节
图论题的大多数 bug 不在算法，在网格翻译层：
- 方向数组：
dr = [-1, 1, 0, 0]、dc = [0, 0, -1, 1]配一个循环，代替四段复制粘贴的邻居代码。五行的差别，错误率差一个数量级； - 标记时机：BFS 必须入队时标记。出队时才标记的话，同一个节点会被多个邻居先后塞进队列，队列里出现大量副本，复杂度从 O(V+E) 劣化到 O(V·E)。DFS 的递归写法是进入时标记。两套时机别混用；
- 边界与障碍检查放同一个 if 里：先判坐标合法、再判格子可走、再判未访问，三关过完才入队。漏一关的表现通常是”答案偶尔大 1”或栈溢出，很难靠看代码发现，靠画一个小网格手推一遍立刻现形；
- 多组查询复用 visited 数组时记得清空，或者用”时间戳标记”（每个格子记最后一次被访问的查询编号，省掉清空数组）。竞赛和工程里都常见的技巧。
在搜索过程可视化里对同一个网格分别跑 BFS 和 DFS：BFS 的访问顺序是一个规整的菱形波纹，一圈一圈推向目标；DFS 是一条扭动的长蛇，先吞掉一个方向的所有死角，再折返。
两个画面放在一起，“按层”和”扎深”就再也不用背了。
第二层：最短路
BFS 的队列换成优先队列（按已知代价排序取出），骨架不变，它就变成了 Dijkstra。
处理任意边权的单源最短路。
但 Dijkstra 回答的是”从起点到所有点的最短路”，而现实里常常只问”到某一个点的最短路”。
问题变窄了，算法就该变快。
A* 的全部内容，就是给 Dijkstra 加一个”目标在哪个方向”的直觉，然后证明这个直觉不会带偏结果。
Dijkstra 在单目标问题上浪费在哪
Dijkstra 的循环是：每次从优先队列取出当前已知距离最小的节点 u，用它松弛邻居。
这个”距离最小”的顺序保证第一次弹出目标时，距离已是最终答案。
因为它按”离起点的真实远近”全图同心扩散。
单目标场景的浪费一目了然：目标在东边，Dijkstra 依然花同样的力气向西、向北扩散，把一圈毫无希望的节点全部松弛完毕。
这些探索对”到目标的最短路”毫无贡献。
加一个直觉：f = g + h
A* 只改一处：优先队列的排序键不再是”离起点的已知距离 g”，而是
g(n) 是已知的起点到 n 的实际代价，h(n) 是从 n 到目标的估计代价。
这就是启发式。
现在队列优先弹出的不是”离起点近”的，而是”离起点近 且 看起来离目标也近”的节点。
直觉上，探索被拉成了朝着目标的一个椭圆，而不是全图同心圆。
h 从哪来？取决于问题的结构。
网格地图上最常用三种：
- 曼哈顿距离 |dx| + |dy|：四方向移动时的自然选择；
- 欧几里得距离 √(dx² + dy²)：任意角度移动时用；
- 切比雪夫距离 max(|dx|, |dy|)：八方向（含对角）移动、且对角步按 1 计价时用。
选哪种的原则只有一条：h 不能高估真实剩余代价。
如果几何直觉太弱（真实路网里”直线距离”被河流和高架绕得离谱），还有一步进阶：地标法（ALT）。
预处理时选十几个地标点，预先算好地标到所有节点的精确距离，查询时用”n 经某地标到目标的下界”三角不等式造 h。
它用的全是精确距离，天然可采纳，而查表是 O(1)。
地图服务大规模寻路的标准强化手段。
最优性的代价条件
h 有两个递进的性质：
- 可采纳（admissible）：h(n) ≤ n 到目标的真实代价。此时 A* 找到的第一条到目标的路径就是最优的。直观理由：h 从不高估，意味着 f 值是”总代价的下界”。最优路径上的每个节点 f 都不超过真实最优代价，而任何被提前弹出的”看似便宜”的节点不可能给出更小的下界。形式化就是标准证明，直觉上”h 从不吹牛，所以按 f 排队不会错过真最优”。
- 一致（consistent）：h(u) ≤ cost(u,v) + h(v)，即 h 满足三角不等式。一致性蕴含可采纳性，且保证每个节点至多被展开一次。弹出后不会再以更小的 f 被重新入队。几何距离做 h 时，这三条全部天然满足（欧氏距离本身就是度量，自动满足三角不等式）。
工程上要知道的取舍是：如果 h 偶尔高估一点，A* 会变快但可能给出次优解（问题变成权重 A*，f = g + ε·h，用解的质量换速度）。
很多游戏寻路故意这么干。NPC 差半个格子的”最优”没人看得出来。
它到底省了多少
最好理解的方式是看探索区域。
在无障碍的开阔网格上：
- Dijkstra 探索一个以起点为圆心、以”起点到目标距离”为半径的圆，面积 O(d²)；
- h 完美（h 恒等于真实剩余代价）的 A* 只沿最优路径直走，O(d)；
- 真实的欧氏 h 介于两者之间：探索一个以起讫两点为焦点的椭圆，障碍越少椭圆越窄。
障碍的作用是把椭圆”吹胖”：绕大障碍时，启发式暂时失灵（绕行段的 h 看不出绕的必要），节点照样成批展开。
所以 A* 的收益高度依赖地图形态。开阔地图收益巨大，迷宫式地图退化明显。
在A* 演示里分别放一个空场和一个迷宫，对比探索格子的着色数量，差别立现。
手推一遍：平手裁决是隐藏的第三要素
“h 完美的 A* 只沿最优路径直走”其实藏了一个假设：平手要裁对。
拿一个 3×3 空网格算一遍就能看穿。
起点在左上、终点在右下，四方向移动，曼哈顿距离做 h。
起点到终点的真实代价是 4。
算每个格子的 f = g + h：
- 起点 (0,0)：g=0，h=4，f=4；
- 任意中间格子（比如 (1,1)）：g=2，h=2，f=4；
- 终点 (2,2)：g=4，h=0，f=4。
九个格子全部打平。
这不是巧合：空网格上曼哈顿距离恰好等于真实剩余代价（h 完美），而任何一格都落在某条最优路径上，于是每格的 g + h 都等于最优总代价。
f 完全没有区分度，A* 退化成”在所有 f=4 的格子里凭队列顺序乱选”。
最坏情形照样把整个网格展开。
解法是给平手加一条裁决规则：f 相同时优先取 g 更大的（离目标更近的优先）。
同样的九个格子，这条规则让搜索贴着一条直线走到终点，只展开 O(d) 个节点。
工程结论：启发式的质量决定 f 的下限，平手裁决决定你能不能摸到这个下限。
两个都是必答题。
什么时候 A* 退化回 Dijkstra
h ≡ 0 恒成立（可采纳），此时 f = g，A* 就是 Dijkstra。
这是理解两者的锚点。
实际退化发生在：
- h 太弱：比如网格上明明四方向移动却用了严重低估的距离，排序键里 g 占绝对主导；
- h 方向性为零：图结构没有几何含义（社交网络、依赖图），造不出有意义的 h。这时该用的是双向 Dijkstra 或者按需算法（Dijkstra with early exit：弹出目标即停，本来就能省一半）；
- 目标太多或反复查询：要的是全源/多源距离场，Dijkstra（或 BFS，边权全一时）本来就是对的工具。
单目标问题还有一件常被忽略的武器：双向搜索。
从起点和目标各跑一个 Dijkstra/A*，在中间相遇。
网格上探索面积大约减半，分支因子大的树形空间里省得更狠。
代价是工程复杂度：反向图要有反向边，两侧的”已扩展边界”要正确对接，接歪了会给出看似合理实则次优的路径。
图结构静态、查询频繁的场景（路网）值得做。一次性的图搜索不值得。
反过来，“每帧都要为成百个单位重算寻路”的游戏场景，标准招数也不是削弱 A*，而是缓存与分帧（jPS、层次寻路 HPA* 等），那是另一个话题。
实现清单与常见 bug
动手实现 A*，下面几条是踩过的人都会点头的地方：
- 优先队列里允许重复、弹出时校验。减小某节点 g 时不必去队列里改旧条目（多数堆不支持），直接推入新条目；弹出时若发现它是过期副本（记录的 g 比当前最优大），丢弃即可。这叫惰性删除，省掉”堆内改键”的全部麻烦；
- 目标判定在弹出时做，不在生成时做。h 可采纳但不一致时，一个节点可能先以次优 g 出队、后又以更优 g 更新。生成时判目标会锁定次优解。一致启发式下两种写法等价，但”弹出时判”永远正确，不值得为省一次比较冒险；
- 8 方向移动的对角代价。对角一步的代价若是 √2，切比雪夫距离会高估真实剩余代价（它假设对角一步只花 1），直接破坏可采纳性。该用八分距离（octile，max(|dx|,|dy|) + (√2−1)·min(|dx|,|dy|)）。对角代价按 1 算时切比雪夫才合法。“换了个距离公式就不再最优”是 A* 最隐蔽的一类 bug；
- h 的单位要和边权一致。网格按格数计代价就用格数距离，按米计代价就把距离换算成米。单位错位等于 h 被放大或缩小固定倍数，放大超过真实比例就高估了。
第三层：博弈
遍历与最短路有一个共同前提：图是死的。
边的代价不会因为你走了一步就改变。
可有一类搜索问题，图的另一头站着一个会反击的对手。
你每走一步，可走的路就跟着变。
“最优路径”这个概念失效了，取而代之的问题是”即使对手完美应对，我也能拿到什么”。
井字棋是最小的严肃博弈：3×3 棋盘、两人轮流、最多九步终局。
它小到可以穷举整棵博弈树（合法棋局总共不到 26 万个），又大到足以装下对抗性搜索的全部核心思想：minimax、评估函数、alpha-beta 剪枝。
博弈树
自己下棋的思考方式是”我走这，他大概率走那，那我再走这……”。
把这段思考画全，就是博弈树：每个节点是一个局面，我方走枝和对方走枝逐层交替，叶子是终局（我胜/我负/和棋）。
搜索这棵树的基本法则是 minimax：
- 我方做决策的层（max 层）：选评估值最大的走法；
- 对方做决策的层（min 层）：假设对方足够聪明，选对我评估值最小的走法。
min 层的”悲观假设”是整个方法的灵魂：不是猜测对手怎么走，而是假设对手走得最好。
以此为前提算出的分数才是”即使对手完美应对，我也能拿到的东西”。
这也是为什么 minimax 的走法永远不会被对手一步打穿。
评估函数
井字棋的评估可以做到绝对精确：终局直接标 +1（我胜）、−1（我负）、0（和棋）。
不需要任何启发式。
这是井字棋作为教学案例的奢侈之处。
对更大的游戏（国际象棋），叶子无法穷举到终局，评估函数才变成主角：子力、控制格、王的安全……一堆加权特征的线性组合。
搜索负责看得远，评估负责看得准，两者的分工贯穿所有博弈 AI。
递归实现
有了精确评估，minimax 是一段极短的递归：
minimax(局面, 我方轮到?): if 终局: return ±1 或 0 if 我方轮到: return max over 所有合法走法 of minimax(走后局面, false) else: return min over 所有合法走法 of minimax(走后局面, true)开局的根节点取 max，沿着取到 max 的那一支走，就是完美走法。
井字棋整个博弈树在毫秒级算完，连剪枝都不用就足够快。
它的意义在于把算法缩到一眼能看全，好在更大的棋盘上复用。
这棵树里还藏着一个与 DP 呼应的优化点：同一局面可以由不同的着法顺序到达（先下左上再下右下，与先下右下再下左上，局面相同）。
朴素递归会把它们各搜一遍；给递归加一张”局面 → 已算分数”的缓存表（博弈引擎里叫置换表），重复子树直接命中。
数一数就明白这笔账很值：合法对局序列有 25 万多条，而不同的盘面状态只有几千个。
缓存把搜索空间压掉了一个数量级还多。
alpha-beta
minimax 的结论是精确的，但很多分支白算了。
alpha-beta 剪枝的核心观察：
在 max 层，如果某个走法已经保证拿到 α 分，那么它的兄弟分支里，任何”对手会让结果 ≤ α”的分支不必算完。无论里面藏着多好的结果，对手根本不会让你走到那里。
维护两个数：α 是”我方目前能保证的下界”，β 是”对方允许的上界”。
一旦某个节点发现 α ≥ β（当前分支的结果已超出对方容忍范围），立即停止搜索该分支。
剪掉的是对手永远不会选择的未来，留下的结论与完整 minimax 逐位相同。
剪枝效率强烈依赖走法排序：先试强走法，界限收紧得快，剪得狠。
理想排序下考察节点数从 降到约 。
同样的搜索深度预算，相当于深度翻倍。
排序启发式在井字棋上就可以演示：按”中心 > 角 > 边”排走法（与人类棋感一致），alpha-beta 的剪枝肉眼可见地变快。
国际象棋引擎则维护”吃子优先、历史启发、杀手着法”一整套排序流水线。
这就是为什么所有实战博弈引擎（国际象棋、围棋引擎的搜索层）都把”走法排序”当成一级优化。
必然的和棋
穷举井字棋的博弈论结果：双方都完美时，井字棋必为和棋，先手也没有必胜策略。
随机对局的构成可以佐证先手优势的量级：全部 255,168 条对局序列里，先手胜 131,184 条（约 51%）、后手胜 77,904 条（约 31%）、和棋 46,080 条（约 18%）。
乱下时先手赢面明显占优，但两个完美碰在一起，优势会被精确抵消到零。
这让井字棋成为”博弈论值”最直观的教学样本：一个局面的真实价值只有 −1、0、+1 三种，完美 AI 的每一步都在朝自己的值收敛。
于是完美 AI 的真实行为里藏着一种”谦逊”：面对你的失误它一步不饶（你走错，它立刻赢）；面对你同样完美时，它从第一手起就在为”和”布局。
那些看起来消极的防御性走法，正是 minimax 在告诉你”这个分支我算过了，赢不了，但也不会输”。
让 AI 承认”这局我赢不了”，是最难实现的部分：它要求评估在所有分支上都不抱幻想。
人类棋手的弱点正在这里。优势错觉让人在必和的局里冒进。
这也是为什么引擎分析改变了职业棋训练：它把”幻想”从决策里剥掉了。
让 AI”求胜心切”
严格 minimax 在井字棋上有个人机交互层面的瑕疵：对 AI 来说”第 7 步赢”和”第 5 步赢”分数同为 +1，它可能不紧不慢地绕远路。
正确但令人火大。
经典的修复是深度加权：终局得分改成 ±(10 − 递归深度)，赢在更浅的层得分更高，输拖到更深的层扣得更少。
两行改动，AI 立刻表现出”最快取胜、最慢认输”的求生欲。
博弈论值没变（还是赢、还是不输），决策的”气质”完全不同。
这是”评估函数的精度和表现力是两回事”的最小案例：井字棋用绝对精确的 ±1 已经能赢，但要让机器的行为看起来聪明，评估函数还要编码”多快、多稳”这类人类在意的东西。
棋盘变大之后
把 3×3 换成 15×15 的五子棋，minimax 直接照搬会当场失效：分支因子从不到 10 涨到 200 上下，深度 4 的搜索就是 200⁴ ≈ 16 亿个局面。
井字棋的”穷举特权”没了，三件补丁一件不能少：
- 候选剪枝：空棋盘 225 个落点里，绝大多数毫无意义。只考虑”已有棋子的邻近空位”（距离 ≤ 2 之类），合法候选从两百多缩到二三十。这是五子棋 AI 的第一道、也是收益最大的剪枝；
- 深度受限 + 评估函数：穷举到终局不再可能，把”看得远”改成”看 4～8 步”，叶子用棋形打分。活三、冲四这些威胁模式各配权重（能成五的无限大，活四次之……）。评估函数写得好坏，直接决定棋力档次；
- alpha-beta + 走法排序：分支一大，剪枝从”锦上添花”变成”活下去的前提”，而排序启发式（先试威胁最大的落点）决定剪枝效率。
做完三件，一个像样的五子棋 AI 就有了。
再做置换表、迭代加深、静态搜索（只搜吃子/威胁着法），就是业余比赛的档次。
这条”补丁清单”和下一章深蓝、AlphaGo 的演化是同一条路。
骨架不变，工程逐级加码，井字棋只是把骨架缩到最小。
AI 难度阶梯
给游戏配 AI 时，minimax 不是第一个台阶，也不必是唯一台阶。
按棋力排一条完整的阶梯：
- 随机 AI：均匀挑一个合法格。用于最简单的难度档，也是新手熟悉规则的陪练；
- 规则 AI：手写优先级。能赢就赢、能堵就堵、优先占中心次占角。三五十行代码，棋力已经能赢多数没经验的人类，但所有套路都是明牌；
- minimax（+ alpha-beta）：完美棋力，不可战胜但可逼和；
- 受限深度 minimax：把搜索深度限成 2～3 层，配合浅层评估函数。介于规则 AI 与完美之间，是最自然的中等难度。
井字棋在强化学习里的角色单独一提：它是 Q-learning 的经典第一课。
一张几千格的 Q 表按局面存价值，AI 自我对弈几万局、每次按”实际结果 vs 预期价值”微调，就能收敛到接近 minimax 的棋力。
整个训练在浏览器里几秒跑完，所以井字棋也常是”看强化学习第一次自己学会下棋”的最小沙盒。
顺手交代一下数据结构层面的小，因为它同样是教学样本的一部分：棋盘就是长度 9 的一维数组，空位用占位符表示；赢线是写死的 8 组下标（三行、三列、两对角），终局判定就是把 8 条线各扫一遍；和棋判定是”棋盘满且无赢线”。
加上 minimax 的十几行递归，一个完整 AI 不到百行。
所有该有的部件都小到能放进一次面试白板，这就是它在教学里被用了六十年的原因。
从井字棋到深蓝与 AlphaGo
minimax 骨架的后续演化一目了然：
- 深蓝（1997）：井字棋同款架构 + 暴力工程。专用硬件、精雕的评估函数，每秒两亿局面。国际象棋树大到无法穷举，它赢在”看得远”；
- AlphaGo（2016）：围棋的分支因子约 250，深蓝式暴力彻底失效。解决方案是把 minimax 的”全展开”换成策略网络选点 + 价值网络评估 + 蒙特卡洛树搜索。搜索不再是穷举，而是”聪明的抽样”（随机方法篇的方法论在此登场）；评估函数从手写特征换成神经网络学习。
骨架未变的部分就是井字棋教的那三件：对抗假设（对方最强回应）、前瞻（看得越远越强）、评估（叶子标价）。
变的只是每一件在工程上的实现方式。
动手：逼出它的承认
在井字棋上挑战完美 AI，目标不是赢它。赢不了。
而是逼出它的承认：走出严格最优的每一步，观察它如何一路防御走向和棋；然后故意走错一步，看它如何瞬间收紧绞杀。
这两种体验放在一起，minimax 的”悲观假设”就从公式变成了手感。
对人类对手倒是有实用小抄，而且和 minimax 的结论能对上：先手占角比占中心更能制造对手的失误（中心的对称回应太多，角的应对分支更容易出错），对手一旦应错，先手可以用”双威胁”（同时制造两条连线）一步终结。
xkcd 832 那张著名的全应对图把每个局面的最优应对都画了出来，就是一张人肉版 minimax 查表。
谱系总结
| DFS | BFS | Dijkstra | A* | minimax | |
|---|---|---|---|---|---|
| 取出/核心策略 | 栈 | 队列 | 优先队列（按 g） | 优先队列（按 g + h） | max/min 交替层 |
| 回答的问题 | 结构（顺序/环/依赖） | 全 1 边权最短路 | 任意边权单源最短路 | 单对最短路 | 对抗局面的价值 |
| 探索形状 | 触手 | 菱形波纹 | 同心圆 | 朝目标的椭圆 | 博弈树交错展开 |
| 最优性 | 不保证 | 天然 | 天然 | h 可采纳时保持 | 对手完美假设下最优 |
遍历、寻路、博弈是同一副”候选容器”骨架在三代问题上的展开。容器从栈到队列到优先队列，取出键从”谁先发现”到”谁最近”到”谁更有希望”，直到对手登场、取出键变成”对手最不想要的那步”。A* = Dijkstra + 一个从不高估的导航直觉；minimax = 树搜索 + 一个”对手完美回应”的悲观假设。框架记住了，新算法只是换个容器、换个假设。
博弈 AI：从完美搜索到采样近似
井字棋把博弈搜索的骨架缩到了最小，这一章把镜头拉远：四种对局各自的棋力天花板与适配算法差得很远，本站四个棋盘正好各占一层——井字棋、四子棋、五子棋、黑白棋。双人回合制棋类是 AI 最古老的试验田，它把智能压缩成一个干净的数学结构：双方轮流行动、信息完全公开、一方之得即另一方之失。给这类游戏造对手，本质是回答三个递进的问题：能不能搜到底（完美搜索）、搜不到底怎么估（评估函数与剪枝）、评估函数写不出来怎么办（采样近似）。minimax、α-β 剪枝、MCTS 正是三问的三个答案。
博弈即搜索
先把这个世界的边界划清楚。这里讨论的是零和、完全信息、轮流行动的确定性博弈。
棋盘上没有隐藏信息（区别于斗地主）、没有骰子（区别于双陆棋）、赢家的收益就是输家的损失。
这类博弈有一个早在 1913 年就被 Zermelo 证明的定理：只要博弈有限步内必然结束，那么从任何一个局面出发，双方都存在”最优着法”。要么一方必胜，要么双方必和。
注意这个结论与”人类找不找得到”无关，它只保证存在。
“存在必胜策略”和”知道必胜策略是什么”之间隔着的，就是搜索问题。
博弈树的组织规则上一章已经立过：节点交替属于两个利益相反的玩家，轮到我走的一层（MAX 层）取子节点的最大值，轮到对手走的一层（MIN 层）取最小值——“对手会尽全力坏你的事”不是一句心理描写，而是 MIN 层的取最小值操作。
minimax
有了这棵树，最优着法的定义立刻可算：给每个终局打分（我赢 +1、我输 −1、和 0），自底向上 MAX 层取最大、MIN 层取最小。工程里用的是带深度上限的版本：
function minimax(pos, depth): if 终局 or depth == 0: return evaluate(pos) if 轮到我: best = -∞ for 每个合法着法 m: best = max(best, minimax(走m后的局面, depth-1)) else: best = +∞ for 每个合法着法 m: best = min(best, minimax(走m后的局面, depth-1)) return best复杂度是分支因子 b 的 d 次方。，指数爆炸。
它能不能直接用，完全取决于博弈树有多大。
井字棋是这条门槛上的”最小案例”。9 个格子最多 9 步，合法对局路径总共 255168 条，去重后的不同盘面只有 5478 个。
这两个数字值得数一遍，因为它们的口径不同。把每局都走满九步是 条序列，但任何一方提前连成三子游戏即告终止，继续走的”虚构步”都要从总数里剔除，255168 正是按终止时间分层统计后的真实对局路径数。而 5478 是 3⁹ = 19683 种原始格面里经合法着法可达的那部分（其余全是某个子提前取胜后才会出现的非法盘面）。
这个量级连手机都能在一瞬间搜到底，所以井字棋的 AI 不需要任何近似。它每一手都是把整棵树搜完的完美决策。
和它对弈你最多逼平：井字棋的 Zermelo 答案就是”双方必和”。这是被彻底搜索证明过的，不是推测。
如果你能赢它，说明它有 bug。如果你总输，说明你走的是必败分支。
α-β 剪枝
α-β 剪枝的机制上一章已经拆过：它不改变 minimax 的答案，只砍掉不影响答案的分支。α 是当前路径上 MAX 层已经保证能拿到的下界，β 是 MIN 层已经压住的上界，一旦 α ≥ β 剩余兄弟全部剪掉；效率极度依赖走法顺序，最好情况复杂度从 降到约 ，等效于搜索深度翻倍——这是同一次算力预算下棋力差距的来源。它上桌的第一个大舞台是四子棋（7×6 落子，先连成四子者胜）。
四子棋的完整状态空间在 量级，直接搜到底需要人海级别的算力。
1988 年 Victor Allis 用极其精巧的推理（配合搜索）证明了先手只要从中路开局就必胜。这是博弈搜索史上最著名的成果之一，但对普通对局来说，全宽搜索仍然超预算——于是深度受限的 α-β 搜索成了标准配置，并在每层搜索前先按静态评估把着法排序（或用上一轮搜索的着法作”杀手着法”优先试），让好走法尽早把窗口压窄。
本站的黑白棋把这条阶梯做成了难度档。中档是纯贪心（数翻子数，加上角和边的位置加成），高档才是 minimax 加 α-β 剪枝，叶子处用一个位置权重表估值。
角 +100，边 +10，而贴着角的格子 −15。
最后这个负分单独说。黑白棋里角一旦被占就再也无法被翻转，是全盘最坚固的地。而紧贴角外侧的格子一旦被对手翻走，等于亲手把角递了过去。
所以”少翻两颗子但拿角”是高手着法，“多翻十颗子但送角”是自杀。这类翻子数与位置结构的倒挂，就是评估函数存在的意义：它替搜索把”这盘棋什么才叫好”写下来。
评估函数
α-β 再快，指数还是指数。
五子棋是这条规律的代言人。15×15 的棋盘，每个空位都是候选着法，中盘分支因子在 200 上下。每深一层搜索树大 200 倍，搜十层就是 。
搜不到底，就必须在某个深度强制停下，然后回答一个问题：这个叶子局面，值多少分？
这个打分函数就是评估函数，它是所有棋类 AI 真正的”棋感”所在。
评估函数还有一条容易被忽略的计量纪律：它的量纲要与终局分对齐。
终局给 +∞/−∞（或极大数）表示胜负，中间局面给的分数必须落在”离胜负还有多远”的同一把尺子上。活四评 9000、活三评 500、单子评 1，背后的逻辑是”一个活四离赢已经一步之遥，抵得上一千个散子”。
量纲错乱的评估函数（子力分压过胜负分）会搜出”宁愿少失一子也不挡对方成五”的昏招。这不是搜索的错，是尺子画反了。
好的评估函数长什么样
写评估函数有两个方向相反的失败模式。写得太粗，AI 有算力也没棋力。写得太细，每层搜索慢十倍，等于自断深度。
实践中有效的配方通常只有几条硬指标。
连子结构。五子棋里活三、冲四、活四的价值不是线性的。活四（两头都空的四连）等于下一手必胜，估值要指数级压过任意多个活二。
本站五子棋的评估函数就是沿四个方向数连子。对每个候选点算”己方成形分 ×1.1 + 阻断对方成形分”，那个 1.1 的不对称是个有趣的细节。自己的棋比挡住对方的棋略微更值钱，这符合”进攻优先”的棋理。
一层威胁检测。光有连子分不够，还要在落子模拟后直接问两个二值问题。我下这里是否立刻成五（加 1000000），对方下这里是否立刻成五（加 500000，即封堵义务）。
这两个大数把”硬威胁”从统计分里拔了出来，保证评估函数不会被一堆小分糊住眼睛。
位置权重。黑白棋的角与贴角、五子棋的棋子密度（新子落在已有棋子附近，加密度小分），都是”局面学”的数值化。
四子棋的规则型 AI
有一个反直觉的事实。本站四子棋的 AI 一层搜索都不做，它是纯规则的。
第一步找自己能直接连成四子的列，第二步找对手能连成四子的列去堵，都没有就偏好中列，再在评分最高的几列里随机挑一个。
这看起来寒酸，实际对普通玩家相当难缠。原因在于四子棋的威胁是强制性的。每步只有 7 个选择，任何一个”下一手即胜”的威胁都必须立刻回应，没有别的岔路可走。
这种情况下”找到并执行强制着法”几乎等于浅层搜索的全部收益，而省下的算力是全部。
对比之下就能看清评估函数的适用边界。强制着法多、分支小的游戏，规则可以顶替搜索；分支大、威胁需要多步构造的游戏（五子棋的双活三、三步杀），必须老老实实搜索。
这也是为什么同一个”贪心 + 威胁检测”配方，在五子棋的高难度档里够用、放到四子棋里反而不如那三条硬规则。游戏的组合结构不同，同一层智能的性价比完全不同。
MCTS
评估函数这条路的尽头是围棋。19×19、分支因子约 250，更致命的是**“好局面”根本写不出指标**。一块孤棋的死活要到几十手后才见分晓，任何局部特征都靠不住。
2010 年代棋类 AI 的范式转移就发生在这里：与其让人类写评估函数，不如让程序自己采样。
这就是蒙特卡洛树搜索（MCTS），它把”评估”替换成”随机模拟到终局，看谁赢”。
选择：从根出发，每个节点按 UCB1 公式选子节点。，前者是胜率利用（exploitation），后者按访问次数施加好奇心（exploration）。
扩展：到达一个还没全展开的节点，添加一个新孩子。
模拟：从新节点随机快走到底，得到胜负。
回传：把结果沿路径累加回去，更新每个节点的访问数与胜场数。
搜索越久，访问次数越向好的分支倾斜，根节点访问最多的孩子就是推荐着法。
UCB1 里那个探索常数 c 是整套方法的性格旋钮。c 偏小，算法早早押注当前胜率最高的分支，容易被开局假象骗进次优路。c 偏大，采样被平均主义摊薄，收敛变慢。
它取代的是 minimax 里”评估函数”的位置，却没有引入任何人类先验。棋感从代码里消失了，取而代之的是纯统计。
MCTS 的妙处在于收敛到 minimax 的同时永不假设评估函数。它对围棋而言是”无棋感的暴力”，却靠采样把暴力花在刀刃上。
2016 年 AlphaGo 的飞跃则是在两个环节各塞进一个神经网络。策略网络替随机选择剪枝、价值网络替终局模拟直接估胜率。MCTS 的骨架没变，变的只是每个环节的精度。
弱点也继承下来了。采样有方差，MCTS 在”一眼定胜负的残局”里反而不如几十层 α-β 稳定，因为它可能把采样浪费在显然的分支上。
两条路线也并非老死不相往来。把 minimax 的胜负传播塞进 MCTS 的树内（搜到必胜节点就停止采样、直接回传确定值），得到所谓 MCTS-Solver 的混合体。采样负责开阔地，确定性传播负责残局。
这恰好呼应了上一章的分层：没有哪件武器通吃，成熟的做法是让完美搜索处理它能处理的，采样处理它剩下的。
工程三件套
深度受限的 α-β 搜索要真正上桌对弈，还需要三件工程配件。它们在教科书里常被一笔带过，实际决定同一算法的棋力档位。
迭代加深解决”深度该设几层”的问题。与其猜一个固定深度，不如先搜一层、再搜两层、再搜三层……直到时间预算耗尽，交出最后一层完整的结果。
看起来前面几层的计算全白做了。实际上没有：上一层的最佳着法排序留给下一层当先试强手的提示（剪枝效率因此大涨），而指数级搜索的节点数本来就集中在最后一层，前几层的开销合计不到总额的零头。
迭代加深还免费送一样东西：随时可中断。时间到，手头的答案虽然浅一层，但总比没有强。任何”预算不确定还要出结果”的搜索，这套骨架都适用。
置换表利用一个棋类特有的事实：不同的着法顺序可以到达同一个局面。先走 A 再走 B，与先走 B 再走 A，盘面相同。
给盘面算一个哈希，把”这个局面在深度 d 搜出的值”存进表里，再遇到时直接查表返回。
省下的不是小钱。中盘搜索里置换局面成片出现，命中率常常过半。
工程坑也集中在这里。哈希碰撞会返回错值，局面与深度必须一起校验。悔棋回溯时表项的有效性要跟着管理。
静态搜索修补深度截断的破绽。
搜索到深度上限强制停下估值，会有一个系统性的荒诞：截断点恰好吃在”车被白吃”的半路上。评估函数看到的还是”车还在”的局面，下一层才轮到它消失。
这叫水平线效应：搜索深度像一条地平线，正在发生的灾难只要被推到线外就仿佛不存在。
修补办法是截断后不停，继续只搜吃子与将军这类强制着法，直到局面”安静”下来再估值。
静态搜索的层数不定但分支极窄，实际开销可控。没有它，任何评估函数都会在战术组合面前露怯。这也是”AI 突然送子”这类经典事故的头号来源。
三件套的共同气质是：算法不变，只优化”同样的搜索怎么花得更快”。
迭代加深管预算、置换表管重复、静态搜索管截断质量。它们与 α-β 的关系，好比缓存与索引之于数据库查询本身。
四种对局各归其位
把三件武器和四个棋盘对齐，一张表就说清了。
| 对局 | 分支因子 / 状态规模 | 本站 AI 方案 | 理论答案 |
|---|---|---|---|
| 井字棋 | ≤9 / 约 5×10³ | minimax 搜到底，零近似 | 双方必和 |
| 四子棋 | 7 / 约 4.5×10¹² | 规则型（取胜→封堵→中列） | 先手中列必胜 |
| 五子棋 | 约 200 / 天文数字 | 评估函数 + 一层威胁检测，贪心出子 | 未解 |
| 黑白棋 | 约 10 / 约 10²⁸ | minimax + α-β + 位置权重 | 未解 |
规律浮出来：AI 方案不是按”游戏复杂度”选的，是按”搜索预算与状态空间的比值”选的。
井字棋小到可以全知。
四子棋的强制结构让浅推理顶替了深搜索。
五子棋和黑白棋必须评估，而黑白棋分支因子小（每步通常十来个合法着法），同样的算力能多搜好几层，所以 α-β 的收益在黑白棋上格外显著。这也符合实战观感：黑白棋 AI 的棋力台阶感最强，五子棋 AI 则偶尔会漏掉两步之外的杀招。
难度档的工程做法
面向玩家的 AI 还有最后一层设计：难度不是算力的连续函数，而是刻意做出来的台阶。
常见做法有三种，各有一副不同的手感。
一是削预算。搜索深度从五层降到两层，强 AI 立刻”近视”，但它仍会抓住眼前的战术。适合当中档。
二是降智评估。把位置权重表删掉只留子力计数，AI 看得远却看不懂局面。黑白棋的中档难度正是这么做的（只数翻子数加简单的角边分）。
三是注入受控的随机。在评分前几名的着法里随机挑，而不是永远取最高分。本站四子棋在”没有强制着法”时就是这么走的中列偏好。
三种削法对应三种人类对手的画像。看得近的、看不懂的、会犯松的。好的难度设计是在模仿人的具体缺陷，而不是均匀地变笨。
这也是调试游戏 AI 时最值得自问的问题：我这档难度，输起来像不像一个真实的人输棋？
回头看，这套阶梯就是”什么问题配什么算法”的一份答案：能全搜就别估，能剪枝就别全搜，评估写不出就采样。
三句话各自对应一次算力与问题规模的谈判，而谈判桌上唯一的筹码是问题自身的结构：强制着法、分支宽度、评估可行性。
单人谜题里也有同一套”预算换结构”的故事，四个谜题里的数学讲过四个例子。双人对局比它多出一个活着的对手，于是每一个估值都要在”对手会最坏应对”的前提下重新过一遍秤。
想检验这套分类法，最快的办法就是去四个棋盘上各输一盘。输的方式（被完美搜索逼和、被规则堵死、被评估函数骗角、被剪枝深度压垮）会把每一层武器的性格直接演给你看。