简介：这份资源面向人工智能初学者与算法进阶者，聚焦用IDA*（迭代加深A*）算法求解经典15-puzzle滑动拼图问题，帮助读者理解启发式搜索在状态空间规划中的落地方式。包内共1个文件，为单个Python脚本，压缩包约2KB，轻量易读，可直接运行调试，便于对照代码理解算法流程。IDA通过反复深度优先搜索并逐步抬高阈值，规避了A可能因初始深度过大而浪费算力的问题；脚本中可结合曼哈顿距离或汉明距离构造启发式函数h(n)，并围绕f(n)=g(n)+h(n)展开剪枝与优化，作者对能优化的环节均做了处理。目前已有611人学习下载，适合想掌握IDA*实现细节、启发式函数设计及15-puzzle求解思路的读者参考，也可作为课程实验或算法练习的对照材料。
1. 15-puzzle 为什么值得用 IDA* 认真做一遍
15-puzzle 是很多人接触启发式搜索的第一个练手项目，但真正把它做到「能优化的都优化了」，远不是写个 A* 就能收工的。它状态空间约 10.5 万亿，A* 在内存里存 visited 表会直接爆掉；而 IDA* 用深度优先加迭代加深，把内存压到 O(深度)，代价是重复搜索。标题里那句「能优化的都优化了」，说的其实是一整套工程组合拳：可解性判定、启发函数选型、线性冲突、置换表、走法剪枝、状态编码。这套东西在人工智能课程里是经典作业，在工程上则是理解启发式搜索边界的最佳样本。如果你正在做搜索算法、路径规划、拼图求解器，或者只是想把 IDA* 从伪代码变成能跑 80 步随机局面的代码，这篇可以照着复现。
2. 先把可解性和状态表示定下来：别让搜索跑在死局上
2.1 逆序数判定：一半的随机局面根本无解
15-puzzle 的合法状态只占全部排列的一半。判定方法用逆序数：把棋盘按行展开成 16 个数字（空格记为 0），忽略 0 后统计逆序对数量。对于 4×4 棋盘，当且仅当「逆序数 + 空格所在行号（从底部数起）」为偶数时有解。这个判定必须在搜索前做，否则你会花几个小时去搜一个永远搜不到的解，血泪经验。
def is_solvable(board): # board: 长度16的列表，0 表示空格 flat = [x for x in board if x != 0] inversions = 0 for i in range(len(flat)): for j in range(i + 1, len(flat)): if flat[i] > flat[j]: inversions += 1 # 空格所在行，从底部数起（0-indexed 从下往上） blank_row_from_bottom = 3 - (board.index(0) // 4) return (inversions + blank_row_from_bottom) % 2 == 0逻辑说明：先剔除 0 得到 15 个数字的序列，双重循环统计逆序对。参数上，blank_row_from_bottom用3 - row是因为判定公式要求从底部计数。这个函数 O(1) 级别（固定 15 个数），放在搜索前调用一次即可。注意别把空格行号算成从上往下，这是最常见的翻车点，会导致有解局面被判死。
2.2 状态编码：用整数而不是列表做哈希键
搜索过程中要频繁查置换表，如果把棋盘存成 tuple 或 list，哈希和比较开销会拖垮性能。常见做法是把 16 个格子每格 4 bit 打包进一个 64 位整数。空格用 0 表示，其余 1~15 各占 4 bit。
def encode(board): code = 0 for v in board: code = (code << 4) | v return code def decode(code): board = [0] * 16 for i in range(15, -1, -1): board[i] = code & 0xF code >>= 4 return board逻辑说明：encode每次左移 4 位再或上新值，最终得到一个 64 位整数。decode反向逐位取出。参数上，4 bit 刚好能表示 0~15，不浪费。这样置换表的 key 就是一个 Python int，哈希极快。如果追求极致，可以用数组代替字典做置换表，但要注意内存和冲突处理，新手先用 dict 跑通。
2.3 走法生成与父节点剪枝
每步只能移动空格上下左右。生成后继时，必须排除「走回上一步」的方向，否则会在两个状态间来回震荡，迭代加深直接失效。
def neighbors(code, blank_pos, last_move): # last_move: 上一步移动的方向，用于剪枝 moves = [] r, c = divmod(blank_pos, 4) for dr, dc, name in [(-1,0,'U'), (1,0,'D'), (0,-1,'L'), (0,1,'R')]: nr, nc = r + dr, c + dc if 0 <= nr < 4 and 0 <= nc < 4: if name == last_move: continue # 不走回头路 moves.append((nr * 4 + nc, name)) return moves逻辑说明：divmod把一维下标拆成行列。方向名用于和last_move比较，相同则跳过。参数上，last_move初始传 None。这个剪枝能砍掉约一半的分支，是 IDA* 能跑起来的基础。注意别把「相反方向」和「相同方向」搞混，剪的是回退那一步。
3. IDA* 主循环：迭代加深怎么和启发函数配合
3.1 阈值迭代：从曼哈顿距离起步，每次取最小超限值
IDA* 的核心是外层用一个 f 值阈值做迭代加深。初始阈值设为起点的启发值 h(start)，每轮 DFS 只扩展 f = g + h ≤ threshold 的节点。如果没找到解，就把这一轮遇到的最小超限 f 值作为下一轮阈值。
def ida_star(start, goal, heuristic): threshold = heuristic(start) path = [start] while True: # 返回 (found, next_threshold) found, next_threshold = dfs(start, 0, threshold, path, heuristic, None) if found: return path[:] if next_threshold == float('inf'): return None # 无解 threshold = next_threshold逻辑说明：threshold从 h(start) 开始，保证第一轮就有机会。dfs返回两个值：是否找到解，以及本轮超出阈值的最小 f 值。参数上，next_threshold初始为无穷大，DFS 中每遇到一个超限节点就更新它。这个设计让阈值单调递增，不会漏解。注意如果next_threshold没被更新过，说明状态空间已穷尽，直接返回无解。
3.2 DFS 递归：f 值剪枝和路径维护
内层 DFS 是递归的，每进入一个节点先算 f = g + h，超过阈值就返回并记录。找到目标就逐层回传 True。
def dfs(state, g, threshold, path, heuristic, last_move): f = g + heuristic(state) if f > threshold: return False, f if state == GOAL: return True, f min_exceed = float('inf') blank_pos = state.index(0) for next_pos, move in neighbors(state, blank_pos, last_move): new_state = state[:] new_state[blank_pos], new_state[next_pos] = new_state[next_pos], new_state[blank_pos] path.append(new_state) found, exceed = dfs(new_state, g + 1, threshold, path, heuristic, move) if found: return True, exceed min_exceed = min(min_exceed, exceed) path.pop() return False, min_exceed逻辑说明：f > threshold时立即剪枝并回传 f 值。min_exceed收集本轮所有超限节点里最小的 f，作为下一轮阈值。参数上，g是当前深度，last_move用于剪枝。注意path.pop()必须在递归返回后执行，否则路径会错乱。这里用 list 复制状态，如果性能吃紧可以改成原地交换再换回，但新手先保证正确。
3.3 启发函数接口：曼哈顿距离和线性冲突
启发函数是 IDA* 的命脉。曼哈顿距离是基础，线性冲突是「能优化的都优化了」的关键增量。
GOAL_POS = {1:(0,0), 2:(0,1), 3:(0,2), 4:(0,3), 5:(1,0), 6:(1,1), 7:(1,2), 8:(1,3), 9:(2,0),10:(2,1),11:(2,2),12:(2,3), 13:(3,0),14:(3,1),15:(3,2)} def manhattan(state): total = 0 for i, v in enumerate(state): if v == 0: continue r, c = divmod(i, 4) gr, gc = GOAL_POS[v] total += abs(r - gr) + abs(c - gc) return total逻辑说明：遍历每个非空格，累加它到目标位置的行列距离。参数上，GOAL_POS是预计算的目标坐标表，避免每次算除法。这个函数是 admissible 的，不会高估。注意空格不参与计算，否则会多算。
线性冲突在此基础上加：如果同一行有两个块，它们的目标行也是这一行，但当前列顺序和目标列顺序相反，则至少多花 2 步。实现时按行和列分别扫描。
def linear_conflict(state): conflict = 0 # 行冲突 for row in range(4): tiles = [] for col in range(4): v = state[row * 4 + col] if v != 0 and GOAL_POS[v][0] == row: tiles.append((col, GOAL_POS[v][1])) for i in range(len(tiles)): for j in range(i + 1, len(tiles)): if tiles[i][1] > tiles[j][1]: conflict += 2 # 列冲突同理，略 return conflict逻辑说明：对每一行，收集目标行等于当前行的块，按当前列排序后检查目标列是否逆序。每发现一对逆序加 2。参数上，只统计目标行匹配的块，否则会误判。这个增量通常能把节点数砍掉 30%~50%，是性价比最高的优化。
4. 把性能榨干：置换表、走法排序和编码级优化
4.1 置换表：用字典存已访问状态的最小 g 值
IDA* 会重复访问同一状态，置换表记录每个状态见过的最小 g。再次遇到时，如果当前 g 不小于记录值，直接剪枝。
transposition = {} def dfs_with_tt(state, g, threshold, path, heuristic, last_move): code = encode(state) if code in transposition and transposition[code] <= g: return False, float('inf') transposition[code] = g f = g + heuristic(state) if f > threshold: return False, f # ... 其余同前逻辑说明：transposition是全局字典，key 是编码后的整数。如果已记录更优的 g，当前分支不可能更好，剪掉。参数上，<= g表示允许相等时剪枝，因为路径长度一样没必要重搜。注意置换表在每轮迭代加深之间要清空，否则阈值变化后旧记录会误剪。
4.2 走法排序：先扩展 h 小的方向
DFS 里后继的扩展顺序直接影响找到解的速度。常见做法是按后继的 h 值升序排列，先走看起来更接近目标的。
def ordered_neighbors(state, blank_pos, last_move, heuristic): moves = neighbors(state, blank_pos, last_move) scored = [] for next_pos, move in moves: new_state = state[:] new_state[blank_pos], new_state[next_pos] = new_state[next_pos], new_state[blank_pos] scored.append((heuristic(new_state), next_pos, move, new_state)) scored.sort(key=lambda x: x[0]) return scored逻辑说明：对每个后继算 h 值，排序后返回。参数上，heuristic传入当前使用的启发函数。这个排序让 DFS 更快撞到解，减少无效展开。注意排序本身有开销，如果 h 计算很贵，可以只对前几个候选排序，或者用更便宜的估计。
4.3 编码级优化：预计算邻居表和原地交换
每次divmod和 list 复制都是开销。可以把每个位置的邻居预计算成表，状态用 list 原地交换再换回。
NEIGHBOR_TABLE = {} for pos in range(16): r, c = divmod(pos, 4) lst = [] for dr, dc, name in [(-1,0,'U'), (1,0,'D'), (0,-1,'L'), (0,1,'R')]: nr, nc = r + dr, c + dc if 0 <= nr < 4 and 0 <= nc < 4: lst.append((nr * 4 + nc, name)) NEIGHBOR_TABLE[pos] = lst逻辑说明：预计算每个位置的合法移动，搜索时直接查表。参数上，NEIGHBOR_TABLE是模块级常量。原地交换的写法是state[a], state[b] = state[b], state[a]，递归后换回。这样省掉大量 list 复制，实测能快 2~3 倍。注意换回的顺序要和交换时对称，否则状态会错。
5. 避坑与排查：IDA* 跑不动时先看这几处
5.1 搜索几小时不出结果，内存还暴涨
现象：程序跑很久不返回，内存持续上升。原因：置换表没在迭代间清空，或者把 visited 当 A* 用存了全部状态。解决：每轮迭代加深前transposition.clear()，并且置换表只存当前轮见过的状态。如果内存还是涨，检查是不是在递归里不断复制大对象。
5.2 明明有解却返回无解
现象：可解性判定通过，但 IDA* 返回 None。原因：走法剪枝把last_move传错，或者阈值更新逻辑漏了。解决：先关掉父节点剪枝跑一次，如果能出解说明剪枝写反了。再检查next_threshold是否在每层都正确回传，常见错误是只在最外层更新。
5.3 解的长度比最优解长很多
现象：找到了解，但步数明显偏多。原因：启发函数不可采纳，或者置换表剪枝条件写成了<而不是<=。解决：确认曼哈顿距离和线性冲突都是 admissible 的，线性冲突每对只加 2 不能多。置换表用<=剪枝，保证相同 g 不重搜。
5.4 线性冲突加了反而更慢
现象：启用线性冲突后总时间变长。原因：h 计算开销超过了剪枝收益，或者实现里重复扫描。解决：把线性冲突的扫描限制在目标行/列匹配的块上，别全盘扫。如果局面简单，可以设阈值，h 小于某值时不用线性冲突。
5.5 随机局面生成出无解局
现象：生成的局面搜不到解。原因：随机打乱时没做可解性检查。解决：生成后调is_solvable，不通过就重新打乱。更稳的做法是从目标态反向随机走 N 步，保证有解。
6. 进阶技巧：用模式数据库把 80 步局面压进可接受时间
前面所有优化加起来，跑 40~50 步的随机局面通常没问题，但 80 步的极端局面还是吃力。真正「能优化的都优化了」的最后一块拼图是模式数据库（Pattern Database）。思路是把部分块拿出来单独建表，预计算它们到目标的最短距离，搜索时查表求和作为 h。常见做法是选 7~8 个块加空格建一个 PDB，用 BFS 从目标态反向填表。
from collections import deque def build_pdb(tiles): # tiles: 参与建表的块编号集合，空格始终参与 # 返回 dict: 编码后的子状态 -> 最短距离 pdb = {} start = tuple(range(16)) # 目标态 # 把不参与的块统一映射成同一个占位符，压缩状态 def abstract(state): return tuple(v if v in tiles or v == 0 else -1 for v in state) start_abs = abstract(start) pdb[start_abs] = 0 q = deque([start]) while q: state = q.popleft() d = pdb[abstract(state)] blank = state.index(0) for next_pos, _ in NEIGHBOR_TABLE[blank]: new_state = list(state) new_state[blank], new_state[next_pos] = new_state[next_pos], new_state[blank] key = abstract(new_state) if key not in pdb: pdb[key] = d + 1 q.append(tuple(new_state)) return pdb逻辑说明：abstract把不参与的块统一成 -1，压缩状态空间。BFS 从目标态反向扩展，记录每个抽象状态的最短距离。参数上，tiles选 7 个块时表大小约 58 万，内存可控；选 8 个块表会大一个量级。搜索时对当前状态做同样的抽象，查表得到 h。多个 PDB 可以相加，但要注意块不重叠才 admissible。
实际用的时候，把 PDB 的 h 和曼哈顿、线性冲突取最大值，或者相加（如果块集不重叠）。我一般会建两个 7 块 PDB，一个覆盖上半区，一个覆盖下半区，取和作为 h。这样 80 步局面的节点数能从千万级降到百万级，配合置换表和走法排序，几分钟内能出解。
验证方法很简单：拿一个已知最优步数的局面，比如从目标态反向走 20 步生成的，看你的 IDA* 返回的步数是否等于 20。如果大于，说明 h 不够强或者剪枝有漏；如果小于，说明 h 不可采纳，赶紧查线性冲突和 PDB 的加法。我自己的习惯是每加一个优化就跑一组 50 个随机局面，记录平均节点数和耗时，只有两个指标都下降才保留。这套流程走下来，15-puzzle 的 IDA* 基本就摸到工程上限了。希望帮到你。
本文还有配套的精品资源，点击获取
