八数码难题是很多人接触人工智能搜索算法时第一个真正“动手”的练兵场。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格所以曼哈顿距离 ≥ 错位数。而且任意一步移动只让一个数字块横移或竖移一格因此单步实际代价变化上限是1h2不会超过剩余真实步数。所以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 线性冲突代价 × 2f值中使用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_nodes200000): 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 节点扩展数量对比表下表是实测观察到的一个典型结果不同机器上耗时会有差异扩展节点数是稳定的状态启发式扩展节点数相对倍数解步数备注123456708h1错位数51.0倍2所有h都能秒解123456708h2曼哈顿51.0倍2同上123456708h3欧氏距离51.0倍2同上123456708h4曼哈顿冲突51.0倍2同上567481230h1错位数32874约14.5倍24最多能搜耗时几百毫秒567481230h2曼哈顿22681.0倍24常规推荐选择567481230h3欧氏距离4912约2.2倍24不如h2紧567481230h4曼哈顿冲突1179约0.52倍24额外计算冲突仍划算如果换成h0也就是恒返回0A*退化成迪杰斯特拉式搜索扩展节点数会直接冲到十几万甚至更多那是真正的暴力盲搜。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表。每一种方向都会让你对“搜索”的理解再深一层。这个玩具一样的问题值得慢慢嚼。
八数码难题是很多人接触人工智能搜索算法时第一个真正“动手”的练兵场。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格所以曼哈顿距离 ≥ 错位数。而且任意一步移动只让一个数字块横移或竖移一格因此单步实际代价变化上限是1h2不会超过剩余真实步数。所以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 线性冲突代价 × 2f值中使用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_nodes200000): 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 节点扩展数量对比表下表是实测观察到的一个典型结果不同机器上耗时会有差异扩展节点数是稳定的状态启发式扩展节点数相对倍数解步数备注123456708h1错位数51.0倍2所有h都能秒解123456708h2曼哈顿51.0倍2同上123456708h3欧氏距离51.0倍2同上123456708h4曼哈顿冲突51.0倍2同上567481230h1错位数32874约14.5倍24最多能搜耗时几百毫秒567481230h2曼哈顿22681.0倍24常规推荐选择567481230h3欧氏距离4912约2.2倍24不如h2紧567481230h4曼哈顿冲突1179约0.52倍24额外计算冲突仍划算如果换成h0也就是恒返回0A*退化成迪杰斯特拉式搜索扩展节点数会直接冲到十几万甚至更多那是真正的暴力盲搜。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表。每一种方向都会让你对“搜索”的理解再深一层。这个玩具一样的问题值得慢慢嚼。
