手里拿着一个打乱的3x3数字滑盘想把它复原成目标排列又不想靠蛮力瞎试——这就是八数码问题最直观的形态。作为搜索算法的经典入门题它几乎出现在每一本人工智能教材里也是面试和课程设计中高频出现的题目。但网上大部分讲解要么只贴一段能跑的代码要么只讲曼哈顿距离怎么算很少有人把为什么这样设计启发函数为什么选中A而不是广度优先讲透。这篇博文我就从零开始把启发式搜索解决八数码问题的完整链路捋一遍状态建模、可解性判定、启发函数选型、A实现细节再到实测数据和踩坑心得。对刚接触搜索算法的同学看完可以直接照着实现对已经写过一遍的人也能从中找到一些以前忽略的细节。1. 问题建模与可解性判定棋盘先变成可计算的序列写搜索算法之前第一件事不是急着写循环而是把八数码棋盘这个具体对象抽象成程序里可以比较、可以哈希、可以遍历的数据结构。这个建模如果没做好后面所有代码都会变得很别扭。1.1 用一维元组表示3x3棋盘我见过不少同学用二维数组[[a,b,c],[d,e,f],[g,h,i]]来表示棋盘。二维数组读起来直观但在搜索代码里问题不少比较两个状态是否相等要嵌套循环哈希时要转成不可变类型生成邻居时行列变换的代码也容易出错。我的习惯是直接用一维元组(a,b,c,d,e,f,g,h,i)下标0到8对应棋盘从左到右、从上到下的位置。空格用0表示其余1到8表示对应数字。比如我演示用的初始状态4 3 5 2 8 1 7 6 0用元组表示就是(4,3,5,2,8,1,7,6,0)目标状态用标准排列(1,2,3,4,5,6,7,8,0)。为什么用元组而不是列表因为元组是不可变的可以直接放进集合、字典和堆里不会出现字典里存的state被意外修改这种低级事故。搜索算法里状态是被反复复制和比较的不可变性带来的安全收益远大于那一点点创建开销。下标的映射关系也简单row index // 3col index % 3。反过来index row * 3 col。这一步是整个问题建模的地基后面所有函数——曼哈顿距离、邻居生成、目标判断——都建立在这套约定上。1.2 逆序数搜索前先判生死八数码问题有个很反直觉的特性不是随便一个棋盘状态都能通过合法移动回到目标。有些初始状态天生无解你再怎么搜永远都搜不到。这就引出了预处理阶段最重要的一件事——可解性判定。判定依据是逆序数的奇偶性。把棋盘去掉空格后按行展开成一个序列统计所有前面数字比后面数字大的数对数量这个数量就是逆序数。关键结论是任意一次空格移动要么交换一个数字和空格的位置而这个交换在去掉空格的序列中等价于该数字跨过了偶数个相邻数字不改变逆序数的奇偶性。所以最终结论是初始状态和目标状态的逆序数奇偶性相同则可解不同则无解。如果目标状态是标准的(1,2,3,4,5,6,7,8,0)其去掉空格后的序列逆序数为0是偶数那么判定条件就退化成初始状态去掉0之后的逆序数必须是偶数。拿上面那个初始状态验证去掉0得到[4,3,5,2,8,1,7,6]逐个数一遍4后面比它小的有3、2、1共3个3后面有2、1共2个5后面有2、1共2个2后面有1共1个8后面有1、7、6共3个7后面有6共1个总计12偶数判定为可解。和实际验证一致——这个状态确实能还原到目标。1.3 可解性判断的代码实现写代码只需要两层循环O(n^2)也完全没压力毕竟只有8个数字def is_solvable(state): seq [x for x in state if x ! 0] inversions 0 for i in range(len(seq)): for j in range(i 1, len(seq)): if seq[i] seq[j]: inversions 1 return inversions % 2 0这段代码放在搜索函数之前是无解棋局的预过滤器。我见过有人没有做这一步直接让搜索算法跑一个无解状态结果BFS把所有18万个可达状态都遍历完了还在继续找用A*的人更惨堆里的节点会持续膨胀直到内存耗尽。更隐蔽的问题出在测试环节随机生成初始状态时大约一半无解如果代码里没有判定很可能调试半天发现程序卡死其实是在搜索一个不可能到达的目标。所以无论项目是用来做课程作业还是做性能测试都建议先把这十几行写在前面。2. 搜索的思路从全图遍历到每一步都打分可解性判定只是前置工作。真正的问题核心是在181440个可达状态里怎么快速找到一条从初始状态到目标状态的路径。这里就涉及搜索策略的选择也是为什么用启发式搜索这个问题的答案。2.1 状态空间的真实规模先看一个数据8个数字加一个空格的排列总数是9!也就是362880种。但因为上面说的奇偶性限制真正可达的状态只有一半181440个。这个数字本身不大如果你的初始状态离目标只有几步BFS广度优先搜索二三十层内就能搞定根本用不上复杂算法。但问题是盲目搜索的扩展速度是按层数指数增长的。假设平均每个状态有2到3个有效后继状态BFS想找到一条深度为20的最优解可能在15层就积累了数万到数十万个待扩展节点时间上还能忍空间上队列压得很满。一旦棋盘从8数码变成15数码4x4状态空间直接跳到10^13量级BFS就彻底不可行了。这也是搜索算法课上必然会强调的一点对状态空间的规模要有数盲目搜索只配用来做小规模的参照对比。2.2 估价函数f(n)g(n)h(n)的三层含义启发式搜索的核心思想是给每个搜索节点打一个分用这个分决定下一个扩展谁。A*算法是这个思想下最著名的实现它的估价函数长这样f(n) g(n) h(n)拆开看g(n)从初始状态走到当前状态n已经消耗的实际步数。这个值在搜索过程中是精确已知的。h(n)从当前状态n出发到目标状态的估计剩余步数。这个值是启发函数给出的猜测也是整个搜索算法的灵魂。f(n)综合已经走过的和估计还剩的代表从起点经过n到终点的预估总代价。A*每轮从待扩展节点的集合叫open表里取出f值最小的节点进行扩展。这个策略翻译成人话就是每次挑看起来最有希望快速到达目标的路线先走。为什么这样设计之所以不只看g是因为只看g等价于BFS层序遍历完全不关心目标在哪之所以不只看h是因为只看h会变成贪心搜索容易陷入局部最优解的死胡同——某个节点虽然距离目标估计很近但绕了一大圈才走到那。把两者加起来等于在稳妥和激进之间做了个平衡。2.3 好的h需要满足可采纳性与一致性h(n)不是随便设一个感觉上差不多的数就行。A*要保证找到最优解h必须满足一个关键性质可采纳性admissible即h(n)永远不大于从n到终点的真实最少步数。换句话说启发函数可以低估但绝对不能高估剩余代价。低估的直觉很好理解你给每个节点打的剩余分打得越保守搜索就倾向多扩展一些节点但不会骗算法把一条次优路径误判成最优路径。反过来如果某个启发函数在某一步高估了它就可能把一个最优解路径上的节点打出很高的f值让算法优先走另一条更长的路最终找到的解就不是最优的了。还有一个相关的性质叫一致性consistency。简单来说对任意两个相邻状态n和n需要满足 h(n) ≤ cost(n, n) h(n)。这个条件保证了f(n)沿路径单调不减A*不会出现回头修正某个已经关闭节点的复杂局面。好消息是只要h是可采纳的且是从目标状态通过某种松弛问题算出来的通常也满足一致性。八数码里常用的几个启发函数都是安全的这点我到下一章再细说。3. 启发函数选型四种候选方案的表现差异启发式搜索省不省力全看h(n)质量高不高。一个区分度差的h会让算法退化成有点智商的BFS一个优秀但仍是可采纳的h能砍掉数量级的扩展量。下面我用同一个初始状态对比四种方案看看它们各自的脾气和适用场景。3.1 错位数最朴素、最容易被想到最简单的h是数一下当前棋盘上有多少个数字不在目标位置。比如目标位置是(1,2,3,4,5,6,7,8,0)当前状态(4,3,5,2,8,1,7,6,0)里位置0应该是1现在是4错位置1应该是2现在是3错位置2应该是3现在是5错依次数下来你会发现除位置8的空格外8个数字全部错位。h 8。这个启发函数的好处是计算飞快一次遍历就能完成。但缺点也明显它完全忽略了一个数字离目标位置的距离。两个错位数字可能只差一步也可能绕了大半个棋盘但h值完全一样。这导致f评分模糊大量f值相同的节点挤在一起算法虽然在前进但方向感很弱扩展量明显偏大。它适合用来做最基础的演示或者作为验证A*框架是否写对的冒烟测试不适合追求性能的场景。3.2 曼哈顿距离八数码的默认答案曼哈顿距离是八数码问题上最常用的启发函数。对每个数字计算它在当前棋盘上的位置和目标棋盘上的位置之间的行距离加列距离然后把8个数字的距离累加起来。之所以叫曼哈顿是因为它模拟了只能在网格上横竖移动走过的路程很像曼哈顿街区的道路格局。计算方式很直观。每个空格每次只能上下左右移动一格那么一个数字要回到目标位置至少需要移动行差 列差这么多步而空格在移动中最多顺便把某个数字往目标方向挪一格。所以总曼哈顿距离一定不会超过真实的最优步数满足可采纳性。这是曼哈顿距离成为默认选择的核心原因既不会低估太多信息量足够又严格保证最优性。在我那个18层左右的初始状态上用它做hA*扩展的节点数通常只有错位数方案的十分之一上下。代码实现也很简单预先算好每个数字的目标坐标遍历当前状态累加即可。3.3 线性冲突让曼哈顿更聪明的改进曼哈顿距离虽然好但在某些局面下会过度乐观。举个例子棋盘的一行里有两个数字它们的目标位置也都在这一行但左右顺序反了。比如目标顺序是1在2左边即 1 2当前这一行却是 2 1。按曼哈顿距离算这两个数字的行差都是0列差都是1合计贡献2步。但实际还原它们需要几步先把2往右移、把1往左移让它们各归各位——仅仅移动2和1自己是不够的因为它们互相挡住必然要借用空白格绕一下。真实步数至少是曼哈顿距离贡献的2步 额外的2步也就是4步。这种同一行或同一列内、目标也在同一行或同一列、但前后顺序颠倒的情况就叫线性冲突。改进办法是在曼哈顿距离的基础上每检测到一对这种冲突就给h加上2。注意一次移动最多只能解决一对冲突所以每个冲突加2不会超过真实代价依然满足可采纳性。实现时逐行逐列检测即可。效果上它把曼哈顿距离那部分过度乐观的估计算回来了搜索节点数通常还能再降一半左右。3.4 为什么不推荐欧几里得距离和加权曼哈顿每次讲完曼哈顿距离总有人问那用欧几里得距离行不行欧几里得距离计算的是直线距离的平方根形式在棋盘网格环境下真实移动只能走横竖直线距离往往比曼哈顿距离还要小虽然也是可采纳的但低估得更厉害信息量更少搜索扩展量通常更大。更糟糕的是它需要开平方运算浮点运算比整数加法慢一个数量级在八数码这种每一步代价为1的问题里毫无收益。另一种常见的念头是给曼哈顿距离乘一个大于1的系数来加强引导比如 h 1.5 * manhattan。这种方法确实能大幅减少搜索节点数但代价是打破可采纳性A*不再保证找到最优解。如果你只是想快速得到一个还不错的解它可以接受但如果题目要求的是最优路径比如需要输出最少步数它就是万劫不复。我在调试期曾经想当然地用过加权曼哈顿结果解出来的路径比真实最优解多了好几步排查了半天才发现是h的锅。搜索算法里启发函数必须可采纳这条红线真不是随便说说的。三种有效启发函数在信息量与计算成本上的对比可以简单汇总成下面这张表方便理解不同选型之间的取舍关系启发函数计算成本估计精度是否可采纳适合场景错位数极低低是验证框架、教学演示曼哈顿距离低中是八数码日常最优解线性冲突中高是追求更少节点、更大局面加权曼哈顿低看似高实则危险否只能接受次优解的场景4. A*算法落地数据结构选型与代码拆解理解了启发函数接下来就是工程实现。这也是很多教程跳过的部分大家都会讲A*的伪代码但很少有文章告诉你Python里怎么把频繁取最小值、需要更新已有节点优先级、还要快速查重这几个需求同时照顾好。其实围绕三个数据结构就能把代码组织得很干净。4.1 三个关键数据结构A*的核心循环是从open表里取出f值最小的节点扩展它把产生的后继节点放入open表。为了高效支持这个流程我需要优先队列heapq堆负责取f值最小的节点。Python的heapq是小顶堆每次heappop都能拿到当前最小元操作复杂度O(log N)。放进堆里的每项是一个三元组(f, g, state)其中f和g的先后顺序决定了同f值时先扩展谁一般是g大离目标更近的节点先扩展。哈希字典g_score记录已经发现的状态state对应的最优g值。因为同一个状态可能从不同路径到达g值更小的那条路径更值得保留。集合closed记录已经完成扩展的状态。凡是进入closed的状态说明它的最优g值已确定之后再次遇到可以直接跳过。这三个数据结构的角色容易混。我习惯用一句话区分堆负责接下来扩展谁g_score负责记住这个状态目前有多近closed负责这个状态已经榨干价值了别再碰它。4.2 核心代码逐步拆解下面的代码是我常用的一个版本去掉了所有无关细节把关键路径全部留出来from heapq import heappush, heappop GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def manhattan(state): goal_pos {1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (1, 0), 5: (1, 1), 6: (1, 2), 7: (2, 0), 8: (2, 1), 0: (2, 2)} total 0 for i, val in enumerate(state): if val 0: continue r i // 3 c i % 3 gr, gc goal_pos[val] total abs(r - gr) abs(c - gc) return total def linear_conflict(state): def row_conflicts(row): conflicts 0 positions {} for col, val in enumerate(row): if val ! 0: positions[val] col items sorted(positions.items()) for (v1, c1), (v2, c2) in zip(items, items[1:]): if c1 c2: conflicts 1 return conflicts rows [state[0:3], state[3:6], state[6:9]] cols [[state[r * 3 c] for r in range(3)] for c in range(3)] rc sum(row_conflicts(r) for r in rows) cc sum(row_conflicts(list(col)) for col in cols) return 2 * (rc cc) def h_value(state, use_conflictTrue): base manhattan(state) return base linear_conflict(state) if use_conflict else base def neighbors(state): zero state.index(0) r, c divmod(zero, 3) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: nz nr * 3 nc lst list(state) lst[zero], lst[nz] lst[nz], lst[zero] yield tuple(lst) def solve_a_star(init, use_conflictTrue): if not is_solvable(init): return None open_heap [(h_value(init, use_conflict), 0, init)] came_from {init: None} g_score {init: 0} closed set() while open_heap: f, g, cur heappop(open_heap) if cur in closed: continue closed.add(cur) if cur GOAL: path [] while cur is not None: path.append(cur) cur came_from[cur] return path[::-1] for nxt in neighbors(cur): tentative_g g 1 if tentative_g g_score.get(nxt, float(inf)): continue came_from[nxt] cur g_score[nxt] tentative_g f_score tentative_g h_value(nxt, use_conflict) heappush(open_heap, (f_score, tentative_g, nxt)) return None几个值得注意的细节。第一open_heap里的(f, g, state)三元组排序规则是f优先、g次之。这样当两个节点的f相同时g更大的那个排在前面优先被扩展相当于优先挑快要到终点的路径能减少一些扩展量。第二if tentative_g g_score.get(nxt, float(inf))这一行是跳过期权的关键。它表示如果从当前节点过去到达nxt的g值并不比之前记录的最优g值小那这条路径就没价值直接放弃只有到达g值更小的路径才需要入堆和更新前驱。这天然覆盖了没访问过的新节点get默认无穷大和曾被更差路径访问过的节点。第三哪怕有了这个判断同一个节点仍然可能因为不同的f值多次入堆。所以主循环开头要有if cur in closed: continue这行负责把已经扩展过的重复节点从堆里弹出来丢掉。没有这行程序也能跑但堆里会堆积大量无效项内存和时间都浪费得很冤枉。4.3 路径回溯的细节当cur GOAL成立时我们从目标状态开始不断沿着came_from往前找直到某个状态的前驱是None即初始状态然后把这条链倒过来。这里有个容易踩的小坑有人把came_from命名为parent但初始状态的parent是什么都没设而设成了自己回溯时没有判空直接while循环结果陷入了无限循环或者回溯列表多了一个无意义的初始状态复制。我的约定是初始状态的came_from设为None回溯时判空退出干净利落。另外由于A的启发函数满足可采纳性第一次从堆里弹出来且恰好等于GOAL的那条路径一定是最优路径。不需要在找到目标后对比多条路径取最小这也是A优雅的保证。5. 用同一个例子实测四组配置算法写完光看代码感觉不出来不同启发函数的差距。我直接用上文那个初始状态(4,3,5,2,8,1,7,6,0)跑了一轮目标状态用标准排列。机器性能不同会导致时间数值有波动但扩展节点数的数量级差异是稳定的适合用来体会启发函数的分量。为了公平四组配置跑的是同一个搜索框架只切换h函数。5.1 实测结果启发函数质量与扩展量的关系下面是我的测试机上跑出来的数据节点数统计的是从堆里取出来完成扩展的状态数量启发函数扩展节点数约找到的解步数运行耗时约错位数600016步最优几百毫秒曼哈顿距离800左右16步最优几十毫秒曼哈顿 线性冲突300左右16步最优十几毫秒加权曼哈顿系数1.5100左右18步非最优几毫秒这个表格的信息量很大。横向对比前两行能看出来同样保证最优解曼哈顿距离把扩展节点数压缩了大约一个数量级第三行再叠加线性冲突又能压缩一半以上。这就是启发函数质量的实打实收益。第四行加权曼哈顿表面最快、节点最少但解从16步退化到18步多了两步——这就是拿最优性换速度的代价。看完数据我多说一句节点数少不代表总耗时一定更低因为更强的h往往单次计算成本更高。但对于八数码曼哈顿和线性冲突的计算都是简单的整数运算开销差不了多少收益却实实在在。真到了15数码那种更复杂的棋盘h计算成本更高工程上还得分情况讨论不能一味追求更强h。5.2 工程上容易掉进去的三个坑第一重复节点入堆。只要用了g_score的仅当更优时才入堆策略就可能出现一个state以多个不同的f值存在于堆里程序跑久了堆里会积累很多无效节点。我调试时遇到过堆长度几千、但closed集合只有几百的情况明显就是大量重复节点没被及时过滤。解决办法一是堆弹出时查closed二是在这之后再做一次tentative_g g_score.get(nxt, ...)判断双保险过滤。第二目标状态不要写错0的位置。标准目标(1,2,3,4,5,6,7,8,0)里空格在右下角但很多人容易把目标写成(1,2,3,4,5,6,7,0,8)或者(0,1,2,3,4,5,6,7,8)。0的位置一旦错了h函数的目标坐标表全错搜索能找到解的只有那些恰好两边奇偶性相同的巧合情况一旦不同就会无限搜。排查时如果算法一直搜不到解除了怀疑可解性也建议打印一下GOAL常量确认。第三无解的初始状态别直接进A*。前面说过随机生成的状态大约一半无解如果没有前置的is_solvable过滤A*会把全部181440个状态都扩展一遍还找不到目标堆空掉之后返回None。看起来像是程序挂了其实是状态空间遍历完了。这个排查起来很花时间所以最好像我代码里那样在进入搜索前先判一下可解性seconds就返回None。5.3 从A向IDA扩展的思路A虽然好用的但open表会持续存放大量节点。八数码还能接受15数码的时候内存压力会迅速增大。如果有一天你需要在更大棋盘上解决同类问题可以顺势了解一下迭代加深AIDA*。IDA的思路是不维护全局open表而是用递归深度优先 阈值迭代的方式每轮只允许f值不超过某个阈值的节点入栈搜索。一轮找不到解就把阈值抬高一点再从头搜。因为每轮搜索的内存开销只有一条递归路径的深度内存占用从所有待扩展节点降到O(深度)是空间上的巨大解放。缺点是同一节点会被重复搜索时间上会有所牺牲。对八数码来说A已经绰绰有余但顺着这个思路去理解IDA*能帮你把启发式搜索这一族算法连成一张更完整的知识网。回到最开始的问题为什么非要用启发式搜索我的体会是八数码这种状态空间看起来不大的问题用盲目搜索也能勉强跑通一旦换成更复杂的问题模型盲目搜索会迅速崩盘。而启发式搜索的价值恰恰在于它把问题的结构信息注入到搜索过程中让人可以根据h函数计算成本与搜索复杂度之间的平衡设计出契合问题的最优解方案。把这个思路带着无论之后做路径规划、拼图还原还是更大规模的组合优化问题心里都会更有底。顺带说一句如果面试或者考试遇到八数码能当面讲清楚曼哈顿距离为什么可采纳、线性冲突为什么额外加2、加权曼哈顿为什么导致次优解这些点本身就比单写一个能跑的A*值钱得多。 
长河君 · 2026/10/16 5:46:03 · 阅读 1.2k 八数码问题求解：A*算法与启发式搜索实战解析
手里拿着一个打乱的3x3数字滑盘想把它复原成目标排列又不想靠蛮力瞎试——这就是八数码问题最直观的形态。作为搜索算法的经典入门题它几乎出现在每一本人工智能教材里也是面试和课程设计中高频出现的题目。但网上大部分讲解要么只贴一段能跑的代码要么只讲曼哈顿距离怎么算很少有人把为什么这样设计启发函数为什么选中A而不是广度优先讲透。这篇博文我就从零开始把启发式搜索解决八数码问题的完整链路捋一遍状态建模、可解性判定、启发函数选型、A实现细节再到实测数据和踩坑心得。对刚接触搜索算法的同学看完可以直接照着实现对已经写过一遍的人也能从中找到一些以前忽略的细节。1. 问题建模与可解性判定棋盘先变成可计算的序列写搜索算法之前第一件事不是急着写循环而是把八数码棋盘这个具体对象抽象成程序里可以比较、可以哈希、可以遍历的数据结构。这个建模如果没做好后面所有代码都会变得很别扭。1.1 用一维元组表示3x3棋盘我见过不少同学用二维数组[[a,b,c],[d,e,f],[g,h,i]]来表示棋盘。二维数组读起来直观但在搜索代码里问题不少比较两个状态是否相等要嵌套循环哈希时要转成不可变类型生成邻居时行列变换的代码也容易出错。我的习惯是直接用一维元组(a,b,c,d,e,f,g,h,i)下标0到8对应棋盘从左到右、从上到下的位置。空格用0表示其余1到8表示对应数字。比如我演示用的初始状态4 3 5 2 8 1 7 6 0用元组表示就是(4,3,5,2,8,1,7,6,0)目标状态用标准排列(1,2,3,4,5,6,7,8,0)。为什么用元组而不是列表因为元组是不可变的可以直接放进集合、字典和堆里不会出现字典里存的state被意外修改这种低级事故。搜索算法里状态是被反复复制和比较的不可变性带来的安全收益远大于那一点点创建开销。下标的映射关系也简单row index // 3col index % 3。反过来index row * 3 col。这一步是整个问题建模的地基后面所有函数——曼哈顿距离、邻居生成、目标判断——都建立在这套约定上。1.2 逆序数搜索前先判生死八数码问题有个很反直觉的特性不是随便一个棋盘状态都能通过合法移动回到目标。有些初始状态天生无解你再怎么搜永远都搜不到。这就引出了预处理阶段最重要的一件事——可解性判定。判定依据是逆序数的奇偶性。把棋盘去掉空格后按行展开成一个序列统计所有前面数字比后面数字大的数对数量这个数量就是逆序数。关键结论是任意一次空格移动要么交换一个数字和空格的位置而这个交换在去掉空格的序列中等价于该数字跨过了偶数个相邻数字不改变逆序数的奇偶性。所以最终结论是初始状态和目标状态的逆序数奇偶性相同则可解不同则无解。如果目标状态是标准的(1,2,3,4,5,6,7,8,0)其去掉空格后的序列逆序数为0是偶数那么判定条件就退化成初始状态去掉0之后的逆序数必须是偶数。拿上面那个初始状态验证去掉0得到[4,3,5,2,8,1,7,6]逐个数一遍4后面比它小的有3、2、1共3个3后面有2、1共2个5后面有2、1共2个2后面有1共1个8后面有1、7、6共3个7后面有6共1个总计12偶数判定为可解。和实际验证一致——这个状态确实能还原到目标。1.3 可解性判断的代码实现写代码只需要两层循环O(n^2)也完全没压力毕竟只有8个数字def is_solvable(state): seq [x for x in state if x ! 0] inversions 0 for i in range(len(seq)): for j in range(i 1, len(seq)): if seq[i] seq[j]: inversions 1 return inversions % 2 0这段代码放在搜索函数之前是无解棋局的预过滤器。我见过有人没有做这一步直接让搜索算法跑一个无解状态结果BFS把所有18万个可达状态都遍历完了还在继续找用A*的人更惨堆里的节点会持续膨胀直到内存耗尽。更隐蔽的问题出在测试环节随机生成初始状态时大约一半无解如果代码里没有判定很可能调试半天发现程序卡死其实是在搜索一个不可能到达的目标。所以无论项目是用来做课程作业还是做性能测试都建议先把这十几行写在前面。2. 搜索的思路从全图遍历到每一步都打分可解性判定只是前置工作。真正的问题核心是在181440个可达状态里怎么快速找到一条从初始状态到目标状态的路径。这里就涉及搜索策略的选择也是为什么用启发式搜索这个问题的答案。2.1 状态空间的真实规模先看一个数据8个数字加一个空格的排列总数是9!也就是362880种。但因为上面说的奇偶性限制真正可达的状态只有一半181440个。这个数字本身不大如果你的初始状态离目标只有几步BFS广度优先搜索二三十层内就能搞定根本用不上复杂算法。但问题是盲目搜索的扩展速度是按层数指数增长的。假设平均每个状态有2到3个有效后继状态BFS想找到一条深度为20的最优解可能在15层就积累了数万到数十万个待扩展节点时间上还能忍空间上队列压得很满。一旦棋盘从8数码变成15数码4x4状态空间直接跳到10^13量级BFS就彻底不可行了。这也是搜索算法课上必然会强调的一点对状态空间的规模要有数盲目搜索只配用来做小规模的参照对比。2.2 估价函数f(n)g(n)h(n)的三层含义启发式搜索的核心思想是给每个搜索节点打一个分用这个分决定下一个扩展谁。A*算法是这个思想下最著名的实现它的估价函数长这样f(n) g(n) h(n)拆开看g(n)从初始状态走到当前状态n已经消耗的实际步数。这个值在搜索过程中是精确已知的。h(n)从当前状态n出发到目标状态的估计剩余步数。这个值是启发函数给出的猜测也是整个搜索算法的灵魂。f(n)综合已经走过的和估计还剩的代表从起点经过n到终点的预估总代价。A*每轮从待扩展节点的集合叫open表里取出f值最小的节点进行扩展。这个策略翻译成人话就是每次挑看起来最有希望快速到达目标的路线先走。为什么这样设计之所以不只看g是因为只看g等价于BFS层序遍历完全不关心目标在哪之所以不只看h是因为只看h会变成贪心搜索容易陷入局部最优解的死胡同——某个节点虽然距离目标估计很近但绕了一大圈才走到那。把两者加起来等于在稳妥和激进之间做了个平衡。2.3 好的h需要满足可采纳性与一致性h(n)不是随便设一个感觉上差不多的数就行。A*要保证找到最优解h必须满足一个关键性质可采纳性admissible即h(n)永远不大于从n到终点的真实最少步数。换句话说启发函数可以低估但绝对不能高估剩余代价。低估的直觉很好理解你给每个节点打的剩余分打得越保守搜索就倾向多扩展一些节点但不会骗算法把一条次优路径误判成最优路径。反过来如果某个启发函数在某一步高估了它就可能把一个最优解路径上的节点打出很高的f值让算法优先走另一条更长的路最终找到的解就不是最优的了。还有一个相关的性质叫一致性consistency。简单来说对任意两个相邻状态n和n需要满足 h(n) ≤ cost(n, n) h(n)。这个条件保证了f(n)沿路径单调不减A*不会出现回头修正某个已经关闭节点的复杂局面。好消息是只要h是可采纳的且是从目标状态通过某种松弛问题算出来的通常也满足一致性。八数码里常用的几个启发函数都是安全的这点我到下一章再细说。3. 启发函数选型四种候选方案的表现差异启发式搜索省不省力全看h(n)质量高不高。一个区分度差的h会让算法退化成有点智商的BFS一个优秀但仍是可采纳的h能砍掉数量级的扩展量。下面我用同一个初始状态对比四种方案看看它们各自的脾气和适用场景。3.1 错位数最朴素、最容易被想到最简单的h是数一下当前棋盘上有多少个数字不在目标位置。比如目标位置是(1,2,3,4,5,6,7,8,0)当前状态(4,3,5,2,8,1,7,6,0)里位置0应该是1现在是4错位置1应该是2现在是3错位置2应该是3现在是5错依次数下来你会发现除位置8的空格外8个数字全部错位。h 8。这个启发函数的好处是计算飞快一次遍历就能完成。但缺点也明显它完全忽略了一个数字离目标位置的距离。两个错位数字可能只差一步也可能绕了大半个棋盘但h值完全一样。这导致f评分模糊大量f值相同的节点挤在一起算法虽然在前进但方向感很弱扩展量明显偏大。它适合用来做最基础的演示或者作为验证A*框架是否写对的冒烟测试不适合追求性能的场景。3.2 曼哈顿距离八数码的默认答案曼哈顿距离是八数码问题上最常用的启发函数。对每个数字计算它在当前棋盘上的位置和目标棋盘上的位置之间的行距离加列距离然后把8个数字的距离累加起来。之所以叫曼哈顿是因为它模拟了只能在网格上横竖移动走过的路程很像曼哈顿街区的道路格局。计算方式很直观。每个空格每次只能上下左右移动一格那么一个数字要回到目标位置至少需要移动行差 列差这么多步而空格在移动中最多顺便把某个数字往目标方向挪一格。所以总曼哈顿距离一定不会超过真实的最优步数满足可采纳性。这是曼哈顿距离成为默认选择的核心原因既不会低估太多信息量足够又严格保证最优性。在我那个18层左右的初始状态上用它做hA*扩展的节点数通常只有错位数方案的十分之一上下。代码实现也很简单预先算好每个数字的目标坐标遍历当前状态累加即可。3.3 线性冲突让曼哈顿更聪明的改进曼哈顿距离虽然好但在某些局面下会过度乐观。举个例子棋盘的一行里有两个数字它们的目标位置也都在这一行但左右顺序反了。比如目标顺序是1在2左边即 1 2当前这一行却是 2 1。按曼哈顿距离算这两个数字的行差都是0列差都是1合计贡献2步。但实际还原它们需要几步先把2往右移、把1往左移让它们各归各位——仅仅移动2和1自己是不够的因为它们互相挡住必然要借用空白格绕一下。真实步数至少是曼哈顿距离贡献的2步 额外的2步也就是4步。这种同一行或同一列内、目标也在同一行或同一列、但前后顺序颠倒的情况就叫线性冲突。改进办法是在曼哈顿距离的基础上每检测到一对这种冲突就给h加上2。注意一次移动最多只能解决一对冲突所以每个冲突加2不会超过真实代价依然满足可采纳性。实现时逐行逐列检测即可。效果上它把曼哈顿距离那部分过度乐观的估计算回来了搜索节点数通常还能再降一半左右。3.4 为什么不推荐欧几里得距离和加权曼哈顿每次讲完曼哈顿距离总有人问那用欧几里得距离行不行欧几里得距离计算的是直线距离的平方根形式在棋盘网格环境下真实移动只能走横竖直线距离往往比曼哈顿距离还要小虽然也是可采纳的但低估得更厉害信息量更少搜索扩展量通常更大。更糟糕的是它需要开平方运算浮点运算比整数加法慢一个数量级在八数码这种每一步代价为1的问题里毫无收益。另一种常见的念头是给曼哈顿距离乘一个大于1的系数来加强引导比如 h 1.5 * manhattan。这种方法确实能大幅减少搜索节点数但代价是打破可采纳性A*不再保证找到最优解。如果你只是想快速得到一个还不错的解它可以接受但如果题目要求的是最优路径比如需要输出最少步数它就是万劫不复。我在调试期曾经想当然地用过加权曼哈顿结果解出来的路径比真实最优解多了好几步排查了半天才发现是h的锅。搜索算法里启发函数必须可采纳这条红线真不是随便说说的。三种有效启发函数在信息量与计算成本上的对比可以简单汇总成下面这张表方便理解不同选型之间的取舍关系启发函数计算成本估计精度是否可采纳适合场景错位数极低低是验证框架、教学演示曼哈顿距离低中是八数码日常最优解线性冲突中高是追求更少节点、更大局面加权曼哈顿低看似高实则危险否只能接受次优解的场景4. A*算法落地数据结构选型与代码拆解理解了启发函数接下来就是工程实现。这也是很多教程跳过的部分大家都会讲A*的伪代码但很少有文章告诉你Python里怎么把频繁取最小值、需要更新已有节点优先级、还要快速查重这几个需求同时照顾好。其实围绕三个数据结构就能把代码组织得很干净。4.1 三个关键数据结构A*的核心循环是从open表里取出f值最小的节点扩展它把产生的后继节点放入open表。为了高效支持这个流程我需要优先队列heapq堆负责取f值最小的节点。Python的heapq是小顶堆每次heappop都能拿到当前最小元操作复杂度O(log N)。放进堆里的每项是一个三元组(f, g, state)其中f和g的先后顺序决定了同f值时先扩展谁一般是g大离目标更近的节点先扩展。哈希字典g_score记录已经发现的状态state对应的最优g值。因为同一个状态可能从不同路径到达g值更小的那条路径更值得保留。集合closed记录已经完成扩展的状态。凡是进入closed的状态说明它的最优g值已确定之后再次遇到可以直接跳过。这三个数据结构的角色容易混。我习惯用一句话区分堆负责接下来扩展谁g_score负责记住这个状态目前有多近closed负责这个状态已经榨干价值了别再碰它。4.2 核心代码逐步拆解下面的代码是我常用的一个版本去掉了所有无关细节把关键路径全部留出来from heapq import heappush, heappop GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def manhattan(state): goal_pos {1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (1, 0), 5: (1, 1), 6: (1, 2), 7: (2, 0), 8: (2, 1), 0: (2, 2)} total 0 for i, val in enumerate(state): if val 0: continue r i // 3 c i % 3 gr, gc goal_pos[val] total abs(r - gr) abs(c - gc) return total def linear_conflict(state): def row_conflicts(row): conflicts 0 positions {} for col, val in enumerate(row): if val ! 0: positions[val] col items sorted(positions.items()) for (v1, c1), (v2, c2) in zip(items, items[1:]): if c1 c2: conflicts 1 return conflicts rows [state[0:3], state[3:6], state[6:9]] cols [[state[r * 3 c] for r in range(3)] for c in range(3)] rc sum(row_conflicts(r) for r in rows) cc sum(row_conflicts(list(col)) for col in cols) return 2 * (rc cc) def h_value(state, use_conflictTrue): base manhattan(state) return base linear_conflict(state) if use_conflict else base def neighbors(state): zero state.index(0) r, c divmod(zero, 3) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: nz nr * 3 nc lst list(state) lst[zero], lst[nz] lst[nz], lst[zero] yield tuple(lst) def solve_a_star(init, use_conflictTrue): if not is_solvable(init): return None open_heap [(h_value(init, use_conflict), 0, init)] came_from {init: None} g_score {init: 0} closed set() while open_heap: f, g, cur heappop(open_heap) if cur in closed: continue closed.add(cur) if cur GOAL: path [] while cur is not None: path.append(cur) cur came_from[cur] return path[::-1] for nxt in neighbors(cur): tentative_g g 1 if tentative_g g_score.get(nxt, float(inf)): continue came_from[nxt] cur g_score[nxt] tentative_g f_score tentative_g h_value(nxt, use_conflict) heappush(open_heap, (f_score, tentative_g, nxt)) return None几个值得注意的细节。第一open_heap里的(f, g, state)三元组排序规则是f优先、g次之。这样当两个节点的f相同时g更大的那个排在前面优先被扩展相当于优先挑快要到终点的路径能减少一些扩展量。第二if tentative_g g_score.get(nxt, float(inf))这一行是跳过期权的关键。它表示如果从当前节点过去到达nxt的g值并不比之前记录的最优g值小那这条路径就没价值直接放弃只有到达g值更小的路径才需要入堆和更新前驱。这天然覆盖了没访问过的新节点get默认无穷大和曾被更差路径访问过的节点。第三哪怕有了这个判断同一个节点仍然可能因为不同的f值多次入堆。所以主循环开头要有if cur in closed: continue这行负责把已经扩展过的重复节点从堆里弹出来丢掉。没有这行程序也能跑但堆里会堆积大量无效项内存和时间都浪费得很冤枉。4.3 路径回溯的细节当cur GOAL成立时我们从目标状态开始不断沿着came_from往前找直到某个状态的前驱是None即初始状态然后把这条链倒过来。这里有个容易踩的小坑有人把came_from命名为parent但初始状态的parent是什么都没设而设成了自己回溯时没有判空直接while循环结果陷入了无限循环或者回溯列表多了一个无意义的初始状态复制。我的约定是初始状态的came_from设为None回溯时判空退出干净利落。另外由于A的启发函数满足可采纳性第一次从堆里弹出来且恰好等于GOAL的那条路径一定是最优路径。不需要在找到目标后对比多条路径取最小这也是A优雅的保证。5. 用同一个例子实测四组配置算法写完光看代码感觉不出来不同启发函数的差距。我直接用上文那个初始状态(4,3,5,2,8,1,7,6,0)跑了一轮目标状态用标准排列。机器性能不同会导致时间数值有波动但扩展节点数的数量级差异是稳定的适合用来体会启发函数的分量。为了公平四组配置跑的是同一个搜索框架只切换h函数。5.1 实测结果启发函数质量与扩展量的关系下面是我的测试机上跑出来的数据节点数统计的是从堆里取出来完成扩展的状态数量启发函数扩展节点数约找到的解步数运行耗时约错位数600016步最优几百毫秒曼哈顿距离800左右16步最优几十毫秒曼哈顿 线性冲突300左右16步最优十几毫秒加权曼哈顿系数1.5100左右18步非最优几毫秒这个表格的信息量很大。横向对比前两行能看出来同样保证最优解曼哈顿距离把扩展节点数压缩了大约一个数量级第三行再叠加线性冲突又能压缩一半以上。这就是启发函数质量的实打实收益。第四行加权曼哈顿表面最快、节点最少但解从16步退化到18步多了两步——这就是拿最优性换速度的代价。看完数据我多说一句节点数少不代表总耗时一定更低因为更强的h往往单次计算成本更高。但对于八数码曼哈顿和线性冲突的计算都是简单的整数运算开销差不了多少收益却实实在在。真到了15数码那种更复杂的棋盘h计算成本更高工程上还得分情况讨论不能一味追求更强h。5.2 工程上容易掉进去的三个坑第一重复节点入堆。只要用了g_score的仅当更优时才入堆策略就可能出现一个state以多个不同的f值存在于堆里程序跑久了堆里会积累很多无效节点。我调试时遇到过堆长度几千、但closed集合只有几百的情况明显就是大量重复节点没被及时过滤。解决办法一是堆弹出时查closed二是在这之后再做一次tentative_g g_score.get(nxt, ...)判断双保险过滤。第二目标状态不要写错0的位置。标准目标(1,2,3,4,5,6,7,8,0)里空格在右下角但很多人容易把目标写成(1,2,3,4,5,6,7,0,8)或者(0,1,2,3,4,5,6,7,8)。0的位置一旦错了h函数的目标坐标表全错搜索能找到解的只有那些恰好两边奇偶性相同的巧合情况一旦不同就会无限搜。排查时如果算法一直搜不到解除了怀疑可解性也建议打印一下GOAL常量确认。第三无解的初始状态别直接进A*。前面说过随机生成的状态大约一半无解如果没有前置的is_solvable过滤A*会把全部181440个状态都扩展一遍还找不到目标堆空掉之后返回None。看起来像是程序挂了其实是状态空间遍历完了。这个排查起来很花时间所以最好像我代码里那样在进入搜索前先判一下可解性seconds就返回None。5.3 从A向IDA扩展的思路A虽然好用的但open表会持续存放大量节点。八数码还能接受15数码的时候内存压力会迅速增大。如果有一天你需要在更大棋盘上解决同类问题可以顺势了解一下迭代加深AIDA*。IDA的思路是不维护全局open表而是用递归深度优先 阈值迭代的方式每轮只允许f值不超过某个阈值的节点入栈搜索。一轮找不到解就把阈值抬高一点再从头搜。因为每轮搜索的内存开销只有一条递归路径的深度内存占用从所有待扩展节点降到O(深度)是空间上的巨大解放。缺点是同一节点会被重复搜索时间上会有所牺牲。对八数码来说A已经绰绰有余但顺着这个思路去理解IDA*能帮你把启发式搜索这一族算法连成一张更完整的知识网。回到最开始的问题为什么非要用启发式搜索我的体会是八数码这种状态空间看起来不大的问题用盲目搜索也能勉强跑通一旦换成更复杂的问题模型盲目搜索会迅速崩盘。而启发式搜索的价值恰恰在于它把问题的结构信息注入到搜索过程中让人可以根据h函数计算成本与搜索复杂度之间的平衡设计出契合问题的最优解方案。把这个思路带着无论之后做路径规划、拼图还原还是更大规模的组合优化问题心里都会更有底。顺带说一句如果面试或者考试遇到八数码能当面讲清楚曼哈顿距离为什么可采纳、线性冲突为什么额外加2、加权曼哈顿为什么导致次优解这些点本身就比单写一个能跑的A*值钱得多。