八数码难题：从BFS到A*的搜索算法优化实战

1. 从一道题看搜索算法的三次认知跃迁

八数码难题，也就是那个经典的3×3滑块拼图，几乎是每个接触搜索算法的人绕不开的一道坎。题目本身很好理解：给你一个3×3的棋盘，上面有1到8八个数字和一个空格，每次只能把空格上下左右相邻的数字滑进空格里，问最少多少步能还原成目标状态。看起来简单，但真正动手写起来，你会发现同一道题用不同思路去解，代码量、运行效率、思维深度完全不在一个量级上。

我最初做这道题的时候，想法特别朴素——BFS暴力搜呗，把所有状态一层层展开，最先碰到目标状态的那条路径就是最短的。这个思路没错，BFS确实能保证最短步数，但问题在于状态空间太大了。9个位置的全排列是9! = 362880种，虽然其中只有一半是可解的，但接近18万的状态量，如果每个状态都用字符串或者数组来存，再配合队列一层层扩展，内存和时间都会让人头皮发麻。更别说如果题目稍微变一下，变成4×4的十五数码，那状态数直接飙到16!级别，暴力BFS根本跑不动。

所以这道题真正的价值不在于“能不能做出来”，而在于它逼着你去思考：怎么让搜索更快？怎么让空间更省？怎么利用问题本身的特性来剪枝？从单向BFS到双向BFS，再到A启发式搜索，每一步进化背后都有非常清晰的动机和取舍。这篇文章我会把这三个阶段的完整思路、代码实现、踩坑经验全部摊开来讲，尤其是那些你在教科书上看不到的细节——比如哈希表怎么设计才不冲突、双向BFS的相遇条件到底怎么写才不会漏解、A的估价函数怎么选才能既快又准。如果你正在学搜索算法，或者被八数码折磨过，这篇内容应该能帮你把整个知识链条串起来。

2. 单向BFS：最直观的起点，也是最容易踩内存坑的地方

2.1 状态表示与去重的基本盘

单向BFS的核心逻辑非常直白：把初始状态扔进队列，每次取出队首状态，尝试所有合法的空格移动，生成新状态，如果新状态没出现过就加入队列，直到某次生成的状态等于目标状态为止。这里第一个要解决的问题就是状态怎么表示。最省事的做法是用一个长度为9的字符串或者整数数组，比如"123456780"表示目标状态，其中0代表空格。字符串的好处是直观，拼接和比较都方便；整数数组的好处是访问快，但比较和哈希稍微麻烦一点。

去重是BFS的生命线。如果不做去重，同一个状态会被反复加入队列，队列会爆炸式增长，程序直接卡死。最朴素的做法是用一个set<string>来记录访问过的状态，每次生成新状态时查一下set。这个方案在小规模数据下能用，但set的底层是红黑树，每次插入和查询都是O(log n)，当状态数接近18万的时候，这个常数开销会非常明显。我实测过，用set去重的单向BFS跑一个稍微复杂一点的初始状态，大概需要几秒钟，而用哈希表可以压到一秒以内。

2.2 康托展开：把排列映射成整数的利器

说到哈希，就不得不提康托展开。这是一个专门用来计算全排列排名的数学工具，能把一个排列唯一映射到一个整数。对于八数码来说，9个数字的全排列有362880种，康托展开可以把每个状态压缩成一个0到362879之间的整数，直接用数组做哈希表，查询和插入都是O(1)。这个优化带来的性能提升是质的飞跃。

康托展开的计算公式是这样的：对于一个排列，从最高位开始，每一位的贡献是“当前位后面比它小的数字个数”乘以“剩余位数的阶乘”。举个例子，排列"123456780"，第一位是1，后面比1小的数字有0个，贡献是0×8!；第二位是2，后面比2小的有0个，贡献是0×7!；以此类推，最后得到的结果就是0，正好对应目标状态的排名。再比如"213456780"，第一位是2，后面比2小的有1个（就是1），贡献是1×8! = 40320，所以它的康托值就是40320。

用代码实现的时候，阶乘可以预先打表，fact[0]=1, fact[1]=1, fact[2]=2, ..., fact[8]=40320。然后对于每个状态，遍历每一位，统计后面比它小的数字个数，累加count * fact[剩余位数]。这个过程是O(n²)的，n=9的时候几乎可以忽略不计。有了康托值，我们就可以开一个大小为362880的布尔数组visited，直接visited[cantor] = true来标记访问，查询也是O(1)，比set快了一个数量级。

注意：康托展开只适用于没有重复元素的排列。八数码里1到8加上0正好是9个不同数字，所以完美适用。如果题目里有重复数字，康托展开就不行了，得换别的哈希方案。

2.3 单向BFS的完整实现与性能实测

把上面的东西串起来，单向BFS的代码结构就很清晰了。队列里存的是状态字符串和当前步数，每次取出队首，找到0的位置，尝试上下左右四个方向，越界就跳过，否则交换0和相邻数字生成新状态，计算康托值，如果没访问过就标记并加入队列。当生成的状态等于目标状态时，返回当前步数加一。

我实测过几组数据。对于目标状态"123456780"，如果初始状态是"123456708"（只需要一步），单向BFS瞬间出结果。但如果初始状态是"806547231"这种比较乱的，单向BFS需要扩展大约10万到15万个状态，耗时在0.5到1秒之间（取决于机器性能）。这个速度对于单组测试数据来说还能接受，但如果题目有多组测试，或者要求你在1秒内跑完，单向BFS就有点悬了。

更关键的是内存。队列里最多可能同时存在几万个状态字符串，每个字符串占9个字节加上字符串对象本身的开销，再加上visited数组的362880个布尔值，整体内存占用大概在几MB到十几MB之间。对于现代计算机来说不算什么，但在一些内存限制严格的在线评测系统上，这个开销需要留意。

还有一个容易被忽略的坑：步数记录。有些实现会把步数直接存在队列里，每个状态带一个int步数。这没问题，但如果你用结构体或者pair来存，队列元素的大小会增加，内存和拷贝开销也会上升。一个更省的做法是用两个队列交替，或者用层序遍历的方式，在每一层开始时记录当前队列大小，处理完这一层的所有状态后步数加一。这样队列里只需要存状态本身，不需要额外存步数。

3. 双向BFS：从两端同时逼近，把搜索空间砍掉一大半

3.1 为什么双向BFS能大幅提速

单向BFS的问题在于，它是从起点开始一层层往外扩散的，扩散的半径越大，边缘的状态数就越多。八数码的状态空间虽然只有36万，但BFS的扩展是指数级增长的，从起点出发走10步可能只覆盖几千个状态，但走20步就可能覆盖十几万个。而目标状态在另一端，单向BFS必须一直扩展到碰到目标为止，中间做了大量“无用功”。

双向BFS的思路是：从起点和终点同时开始BFS，两边轮流扩展一层，直到某一端扩展出的状态在另一端的visited集合里出现过，就说明找到了通路。这个思路的威力在于，如果起点到终点的最短路径长度是L，单向BFS需要扩展大约b^L个状态（b是分支因子，八数码里平均是2到3），而双向BFS只需要扩展大约2×b^(L/2)个状态。当L=20的时候，b^L和b^(L/2)差了b^10倍，这个差距是巨大的。

具体到八数码，我实测过一组数据：初始状态"806547231"，目标状态"123456780"，最短路径是22步。单向BFS需要扩展大约15万个状态，而双向BFS两边各扩展大约2000到3000个状态就相遇了，总扩展量不到6000，速度提升了两个数量级。这个提升在实际做题的时候是决定性的。

3.2 相遇条件的正确写法与常见错误

双向BFS最容易出错的地方就是相遇条件的判断。很多人的第一反应是：当某一端生成的新状态在另一端的visited里出现过，就立刻返回步数之和。这个思路方向是对的，但细节上有坑。

第一个坑是“步数之和”到底怎么算。假设正向BFS当前扩展到了第d1层，反向BFS扩展到了第d2层，现在正向生成的新状态在反向的visited里，那么总步数应该是d1 + 1 + d2，而不是d1 + d2。因为正向生成这个新状态本身消耗了一步，这一步必须算进去。我见过不少人在这里少算了一步，导致答案偏小。

第二个坑是“谁先扩展”。如果正向扩展一层，反向扩展一层，交替进行，那么相遇时两边的层数差最多是1。但如果某一端的状态数特别少，扩展得特别快，可能会出现一端已经扩展了好几层，另一端才扩展了一层的情况。这时候如果直接判断相遇，可能会漏掉更短的路径。正确的做法是：每次只扩展一层，扩展完立刻检查是否有状态出现在另一端的visited里，如果有就返回。不要等两边都扩展完再检查。

第三个坑是“反向BFS的状态生成”。反向BFS是从目标状态出发，向初始状态搜索。但八数码的移动是可逆的，所以反向BFS的扩展逻辑和正向完全一样，不需要额外处理。不过要注意，反向BFS的visited集合和正向是分开的，不能混用。

3.3 双向BFS的代码骨架与优化细节

双向BFS的代码骨架大概是这样的：维护两个队列q1和q2，两个visited数组vis1和vis2，两个步数计数器step1和step2。每次循环，选择当前状态数较少的那个队列进行扩展，扩展完一层后检查是否有状态在另一端的visited里。如果找到了，返回step1 + step2 + 1。

选择状态数较少的队列进行扩展是一个重要的优化。因为双向BFS的总扩展量取决于两边扩展量的乘积，如果一边扩展得特别多，另一边扩展得特别少，总扩展量反而会变大。每次选择较小的队列扩展，可以让两边的扩展量尽量均衡，从而最小化总扩展量。

还有一个细节是visited数组的复用。因为康托值是0到362879的整数，我们可以开两个布尔数组，分别对应正向和反向。但布尔数组在C++里每个元素占1个字节，362880个元素就是362880字节，两个数组加起来不到1MB，完全可以接受。如果用bitset，每个元素只占1个bit，内存占用可以进一步压缩到原来的八分之一，但查询和设置的常数开销会稍微大一点。实测下来，对于八数码这个规模，布尔数组和bitset的性能差异可以忽略不计，用哪个都行。

提示：双向BFS的相遇判断必须在“扩展完一层之后”进行，而不是在“生成一个新状态时”进行。如果在生成新状态时立刻判断，可能会因为两边的扩展不同步而漏掉最优解。这个坑我在早期实现的时候踩过，调了很久才找到原因。

4. A*启发式搜索：用估价函数给搜索装上导航

4.1 估价函数的设计哲学

A*算法的核心思想是：在BFS的基础上，给每个状态加一个“估价”，表示从当前状态到目标状态的预估代价。搜索时优先扩展“当前代价 + 预估代价”最小的状态，这样就能把搜索方向引导到更有希望的区域，避免盲目扩散。

对于八数码，当前代价就是已经走的步数g(n)，预估代价h(n)需要我们自己设计。h(n)的设计有两个关键要求：第一，它必须小于等于真实代价，否则A*可能找不到最优解；第二，它越接近真实代价，搜索效率越高。这两个要求看起来简单，但实际设计的时候需要仔细权衡。

最常用的两个估价函数是“错位数”和“曼哈顿距离”。错位数就是统计当前状态有多少个数字不在目标位置上，比如当前状态是"123456708"，目标状态是"123456780"，只有最后两位不同，错位数是2。曼哈顿距离是统计每个数字当前位置到目标位置的曼哈顿距离之和，比如数字8在位置7（从0开始数），目标位置是位置8，曼哈顿距离是1；数字0在位置8，目标位置是位置7，曼哈顿距离也是1，总和是2。

曼哈顿距离明显比错位数更精确，因为它考虑了数字需要移动的实际距离。实测下来，用曼哈顿距离的A比用错位数的A快好几倍。但曼哈顿距离也不是完美的，它忽略了一个重要因素：数字之间的相互阻挡。比如两个数字需要交换位置，曼哈顿距离会认为它们各走一步就行，但实际上它们必须绕路，真实代价比曼哈顿距离大。所以曼哈顿距离仍然是一个“低估”，满足A*的要求，但还有改进空间。

4.2 曼哈顿距离的计算与优化

曼哈顿距离的计算本身很简单：对于每个数字1到8，找到它在当前状态中的位置和在目标状态中的位置，计算行差绝对值加列差绝对值，累加即可。0不需要计算，因为0是空格，它的位置不影响其他数字的移动。

但这里有一个优化技巧：目标状态的位置是固定的，可以预先打表。比如数字1在目标状态的位置是0（第0行第0列），数字2的位置是1，以此类推。这样计算曼哈顿距离的时候，只需要遍历当前状态的9个位置，对于每个非零数字，查表得到目标位置，计算距离，累加。这个过程是O(9)的，非常快。

还有一个更进一步的优化：增量式计算曼哈顿距离。每次移动空格的时候，只有一个数字的位置发生了变化，所以曼哈顿距离的变化量可以只计算这个数字的贡献变化，而不需要重新计算整个状态的曼哈顿距离。这个优化在A里特别有用，因为A需要频繁计算估价函数，增量式计算可以把每次计算的复杂度从O(9)降到O(1)。不过实现起来稍微复杂一点，需要在状态转移的时候记录哪个数字移动了，以及它的旧位置和新位置。

4.3 A*的优先队列实现与性能对比

A*的代码结构和BFS很像，区别在于队列换成了优先队列，每次取出f(n) = g(n) + h(n)最小的状态。优先队列里存的是状态、g值和h值，比较函数按照f值排序。如果f值相同，可以按照h值排序，优先扩展h值小的（也就是更接近目标的），这是一个常见的优化技巧。

我实测过三组数据，对比单向BFS、双向BFS和A*（曼哈顿距离）的性能：

从数据可以看出，A的扩展状态数最少，速度最快。但A也有它的局限性：优先队列的每次操作是O(log n)的，而BFS的队列是O(1)的。当状态数比较少的时候，A的优先队列开销可能会抵消掉扩展状态数少的优势。不过对于八数码这个规模，A的优势还是很明显的。

还有一个需要注意的地方：A的visited数组不能简单地用布尔值。因为A可能会多次到达同一个状态，但每次到达的g值可能不同。如果第一次到达某个状态时g值较大，后面又通过另一条路径以更小的g值到达，那么应该允许更新。所以visited数组里存的应该是“到达该状态的最小g值”，而不是简单的“是否访问过”。当新路径的g值小于已记录的最小g值时，才更新并重新加入优先队列。这个细节如果处理不好，A*可能会返回非最优解。

注意：A*的估价函数必须满足“一致性”条件，才能保证每个状态只被扩展一次。曼哈顿距离满足一致性，所以可以安全使用。但如果自己设计了一个不满足一致性的估价函数，就需要允许重复扩展，否则可能找不到最优解。

5. 三种算法的选型逻辑与实战踩坑记录

5.1 什么时候用哪种算法

三种算法各有适用场景，不能一概而论。单向BFS适合状态空间小、对代码简洁度要求高的场景，比如教学演示或者状态数在几万以内的题目。它的优点是逻辑简单、不容易写错，缺点是状态数一多就慢。

双向BFS适合状态空间中等、但最短路径较长的场景。八数码的最短路径最长可以到31步，这时候单向BFS基本跑不动，双向BFS还能勉强应付。双向BFS的代码复杂度比单向BFS高不少，主要是相遇条件的判断和两边队列的协调，但性能提升是值得的。

A适合对性能要求极高、且能设计出好估价函数的场景。八数码的曼哈顿距离估价函数效果很好，所以A在这道题上表现最优。但A的代码复杂度最高，优先队列、g值更新、一致性判断这些细节都需要仔细处理。如果估价函数设计得不好，A可能比双向BFS还慢。

我的建议是：如果是平时练习或者教学，从单向BFS开始，把基础打牢；如果是在线评测卡时间，优先考虑A*；如果估价函数不好设计，退而求其次用双向BFS。

5.2 那些年我踩过的坑

第一个坑是康托展开的阶乘表。我一开始把阶乘表打成了fact[0]=0, fact[1]=1, fact[2]=2, ...，结果所有状态的康托值都偏小，visited数组的索引全乱了，程序跑出来的答案完全不对。后来才发现fact[0]应该是1，因为0! = 1。这个错误很隐蔽，因为大部分状态的康托值看起来都“差不多”，只有仔细对比才能发现。

第二个坑是双向BFS的步数计算。我一开始写的是step1 + step2，结果答案总是比正确答案小1。后来才想明白，正向生成新状态的那一步没有算进去，应该是step1 + step2 + 1。这个坑我在前面提过，但真的很容易犯，因为直觉上会觉得“两边步数加起来就是总步数”，忽略了中间那一步。

第三个坑是A的visited数组。我一开始用布尔数组，结果发现有时候会返回非最优解。后来改成记录最小g值的数组，每次新路径的g值更小时才更新，问题就解决了。这个坑的根源在于A可能会多次到达同一个状态，如果简单地标记“已访问”就跳过，可能会错过更优的路径。

第四个坑是优先队列的比较函数。我一开始只按f值排序，结果发现当f值相同时，搜索效率很低。后来改成f值相同时按h值排序，优先扩展h值小的状态，效率提升了不少。这个优化的原理是：h值小说明状态更接近目标，优先扩展这些状态可以更快找到解。

5.3 从八数码延伸到更一般的搜索问题

八数码虽然是一道具体的题目，但它背后的搜索思想可以延伸到很多问题。比如路径规划、游戏AI、资源调度，本质上都是在状态空间里找一条从起点到终点的最优路径。单向BFS、双向BFS、A*这三种思路，分别对应了“从起点盲目搜索”、“从两端同时搜索”、“用启发式信息引导搜索”三种策略。

在实际工程中，A及其变种（比如IDA、加权A*）用得最多，因为它们的效率最高。但A的效果高度依赖于估价函数的设计，如果估价函数不好，A可能还不如BFS。所以学会设计好的估价函数，比学会A*的代码模板更重要。

双向BFS在一些特定场景下也很有用，比如状态空间很大但最短路径不长的情况。它的优势在于不需要设计估价函数，只要问题可逆就能用。但双向BFS的代码复杂度较高，需要仔细处理两边的协调和相遇判断。

单向BFS虽然效率最低，但它是所有搜索算法的基础。理解了单向BFS，才能理解双向BFS和A为什么要那样设计。所以我的建议是：先把单向BFS写熟，再学双向BFS，最后学A。每一步都要亲手实现、亲手调错，才能真正掌握。

最后分享一个我在调八数码时常用的小技巧：写一个简单的验证函数，用单向BFS跑出最短步数，然后用双向BFS和A*跑同样的数据，对比结果是否一致。如果三种算法给出的答案都一样，说明实现基本正确；如果不一样，就逐个排查。这个交叉验证的方法帮我省了很多调试时间，推荐你也试试。