IDA*算法求解15-puzzle的优化实践：从曼哈顿距离到线性冲突

简介：面向人工智能学习者与算法竞赛爱好者的IDA算法求解15-puzzle问题完整Python实现。项目不仅实现了经典的迭代加深A搜索，还针对启发式函数、节点扩展、剪枝策略等环节做了多处优化，并对15-puzzle的状态表示、移动生成与查重逻辑进行了专项处理，能有效压缩搜索空间、提升求解速度。资源以单个py脚本（IDAstar.py）形式提供，压缩包仅2KB，代码紧凑、结构清晰，适合直接阅读、修改与复用。目前已有610人学习下载。读者可借此快速获得一个可运行的优化版求解器，并从中提炼曼哈顿距离/汉明距离启发式设计、深度迭代边界控制、状态去重与解路径还原等关键实现技巧。对于需要完成人工智能课程设计、准备算法面试或研究启发式搜索的开发者，这是一份轻量而完整的参考样例。 如果你也是被“15-puzzle”这道题折磨过的人，应该能明白那种感觉：解法思路一眼看穿，无非是搜索；但真把代码交上去，等结果等到怀疑人生。我在做人工智能课的大作业时选了IDA算法来解决15-puzzle（4×4滑动拼图）最优解问题，折腾了大半个星期，把能优化的点全做了一遍，最后在普通笔记本上也能秒解大部分随机实例。这篇文章把我踩过的坑和真正有效的优化手段都摊开讲，给正在做同类作业、或者想彻底搞懂IDA为什么对这类问题有奇效的同学作参考。

要提前说明的是，这篇不打算停留在“调用一个库跑出答案”的程度。我会从状态空间的数学特征讲起，再讲IDA*的框架，然后逐条拆解搜索性能的天花板到底卡在哪里，最后给出一个可以直接编译运行的C++参考实现。

1. 先用两个数学问题卡住一般搜索

1.1 状态空间不是大，是大到可以吃掉内存

很多人的第一反应是“15-puzzle不就是一个搜索吗”，我一开始也是这么想的。4×4棋盘上16个格子（15个数字加一个空格）的全排列是16!种，但由于滑动操作的性质，其中只有一半状态能到达目标态。也就是说，真实状态空间大概是：

16! / 2 ≈ 10,461,394,944,000

约10.46万亿个可达状态。

这个数字意味着什么？BFS在十几层之后，队列里的节点数量就会让内存报表不堪重负。A稍微聪明一点，使用启发式函数引导扩展方向，但A仍然需要一张open表来存放所有待扩展的节点，这张表在15-puzzle这种状态爆炸的问题上同样会快速膨胀。我试过用一个简单的A*跑随机测试，一两分钟不出结果还只是小事，实时内存占用肉眼可见在涨，这才是真正劝退我的地方。

IDA*解决这个问题的思路很朴素：不要open表，把“记忆”换成“反复重搜”。每次限制一个深度阈值f = g + h，在这个阈值内做深度优先搜索；搜不到解就提高阈值再来一轮。DFS只需要维护当前搜索路径上的状态，内存消耗只和最优解深度有关。15-puzzle的最优解通常在40到80步之间，所以路径栈顶多几十上百层，内存压力几乎可以忽略。

1.2 可解性判定：一半的状态根本不值得跑

如果输入的状态本身不可达目标态，写再多搜索优化都是白跑。随机打乱一个15-puzzle状态，恰好可解的概率只有50%。因此第一件该做的事是判定可解性。

判定方法很简单：把空格从序列中拿掉，数剩下15个数字的逆序数；再数空格从底部数起是第几行（最底下一行记为0）。逆序数 + 空格底部行数如果为偶数，状态可解，否则不可解。

这个结论的来历也不复杂。一次水平滑动不会改变逆序数，也不会改变空格所在行；一次竖直滑动会让某个数字跨过3个格子，逆序数奇偶性发生翻转，同时空格所在行的奇偶性也翻转，两者相加的奇偶性不变。目标状态显然是“偶数”，所以所有可达状态都满足这个条件。

这段逻辑直接用代码写就是：

bool solvable(const vector<int>& b) { int inv = 0; for (int i = 0; i < 16; i++) for (int j = i + 1; j < 16; j++) { int a = b[i], c = b[j]; if (a && c && a > c) inv++; } int blank = -1; for (int i = 0; i < 16; i++) if (b[i] == 0) blank = i; int rowFromBottom = 3 - ROW[blank]; return (inv + rowFromBottom) % 2 == 0; }

注意：如果输入状态不可解，直接返回“unsolvable”，不要让搜索代码开工。

2. IDA*的搜索框架与两个基础剪枝

2.1 阈值滚动是怎么工作的

IDA*的核心是一个带阈值限制的DFS。设当前状态为s，已经走过的步数为g，启发式函数估计还要走h步，那么f = g + h。每一轮搜索中，只有当f不超过阈值limit时才允许继续深入；一旦f > limit就剪掉，并记录这个超限值。

一轮DFS结束后如果没有找到解，就把limit更新为“本轮所有超限值里最小的那个”，再重新开始搜索。这个更新方式比limit逐次加1高效得多，因为最小超限值意味着下一轮至少能多探索一条更有希望的路径，不会在无意义的低阈值上反复空转。

为什么第一次搜索成功一定是最优解？因为limit严格按最小超限增长，只有当limit达到真实最优解长度时，目标状态才可能第一次出现在搜索范围内。由于路径是无权图上的步数，第一个被搜索到的解一定就是最短解。

2.2 两个几乎免费的剪枝

IDA*的DFS路径必须避免回头路，我加了两个剪枝，实测效果都非常明显。

第一个是“不回上一步”。如果当前空格位置是p，上一步移动后空格位置是q，那么这一步再把空格移回p，等于把上一步撤销，纯浪费。检查一下移动目标位置，如果等于上一步的空格位置就直接跳过。

第二个是“路径防环”。很多初学者只做“不回上一步”就完事，但15-puzzle里还存在更长的环，比如空格绕一个2×2小方块转一圈，会回到之前的状态。这种环会让搜索反复在同一个状态附近绕圈，白白消耗节点数。我用一个哈希集合保存当前搜索路径上的所有状态，每进入一个新状态先查重，回溯时删除对应记录。这个集合只维护“从起点到当前节点”这一条路径上的状态，不维护所有访问过的状态，因为IDA*每一轮阈值搜索都会重新开始，全局访问集合会误伤不同路径。

代码上的正确姿势是：

inPath.insert(ns); sol.push_back(mv.dir); if (dfs(...)) return true; sol.pop_back(); inPath.erase(ns);

插入、递归、删除必须配对。漏掉erase会在路径回溯后留下一个“幽灵状态”，导致搜索误认为某状态已经被访问过，直接漏掉可行解。

3. 启发式函数：从曼哈顿距离到线性冲突

3.1 曼哈顿距离为什么是合法下界

启发式函数是IDA*性能的第一决定因素。最基础的是曼哈顿距离：对每个数字块，计算它当前位置到目标位置的横向距离加纵向距离，再求和。

int mdState(u64 s) { int sum = 0; for (int p = 0; p < 16; p++) sum += md[tile(s, p)][p]; return sum; }

这里的md[t][p]是打表预计算好的，t表示数字块编号，p表示棋盘位置。曼哈顿距离一定不超过真实剩余步数，因为每一步只移动一个数字块，而一个数字块每移动一格顶多让它的曼哈顿距离减少1。这个性质叫可采纳性（admissible），是IDA*保证最优解的前提。

曼哈顿距离实现简单，计算速度快，但对一些“互相挡路”的局面估计不足。举个例子，某一行最终应该排列成1 2 3 4，当前这一行是2 1 3 4。按照曼哈顿距离，1和2各自距离目标位置只有1格，总共贡献2，但这一行里1和2位置颠倒，要把它们理顺，至少还要额外花两步。曼哈顿距离看不见这种阻碍，于是启发式偏低，搜索就会在这个方向上多浪费大量节点。

3.2 线性冲突：一个必须小心的增强启发式

线性冲突就是用来补上曼哈顿距离盲区的。基本想法是：在同一目标行（或同一目标列）上，如果有两个数字块的顺序反了，那么它们相互“挡路”，至少需要额外两步才能让它们各归其位。

这一步看着简单，里面却藏着一个大坑。我第一次实现时，把同一行里所有冲突对都加进去，每个冲突对额外加2。程序跑出来的结果不对：最优解步数直接被高估，原本有解的实例被判定成无解，或者给出的解根本不是最优解。原因很简单，如果一行里有三个数字块形成循环冲突，比如3 1 2，其中存在多对逆序关系，但它们背后的“额外两步”可能部分重叠，简单累加所有冲突对会突破可采纳性边界，让启发式变得不合法。

正确处理方法是：在每一行（列）内，找一组互不相交的冲突对，也就是每个数字块最多只参与一个被计入的冲突对。每找到一对，就给启发式加2。这样得到的启发式才仍然是一个合法的下界。

int lineConflict(u64 s, bool isRow, int idx) { vector<pair<int,int>> v; for (int i = 0; i < 4; i++) { int pos = isRow ? idx * 4 + i : idx + i * 4; int t = tile(s, pos); if (t == 0) continue; int line = isRow ? ROW[tp[t]] : COL[tp[t]]; if (line != idx) continue; v.push_back({i, isRow ? COL[tp[t]] : ROW[tp[t]]}); } sort(v.begin(), v.end()); int cnt = 0; vector<bool> used(v.size(), false); for (int i = 0; i < (int)v.size(); i++) { if (used[i]) continue; for (int j = i + 1; j < (int)v.size(); j++) { if (used[j]) continue; if (v[i].first < v[j].first && v[i].second > v[j].second) { cnt++; used[i] = used[j] = true; break; } } } return cnt * 2; }

这里用了一个贪心配对：当前位置靠左、但目标位置却更靠右的数字块，和另一个位置靠右但目标位置更靠左的数字块配对。配对一旦成立，两个数字块都标记为“已占用”，不再参与其他配对。这个版本不一定能配出最多冲突对，但配对出来的每一对都是互不相交的，所以启发式一定合法。想更强的话，同一行最多4个数字块，完全可以用位掩码暴力枚举最大互不相交冲突对数量，收益不大但代码会多不少。

最终启发式函数就是曼哈顿距离加上所有行、列的线性冲突步数：

int hState(u64 s) { return mdState(s) + conflictState(s); }

加入线性冲突之后，搜索节点数通常能再缩小一个数量级，这是15-puzzle这类问题上性价比最高的启发式增强。

4. 工程级优化：状态编码与增量计算的取舍

4.1 64位整数编码一个状态

搜索程序如果直接操作一个二维数组，每次复制状态都是16次内存拷贝，还要额外处理边界判断。我选择把整个棋盘压缩到一个unsigned long long里：每个格子用4个二进制位表示数字块编号0到15，16个格子正好占满64位。

inline int tile(u64 s, int p) { return (s >> (p * 4)) & 15; } inline u64 putTile(u64 s, int p, int v) { return (s & ~(15ULL << (p * 4))) | (u64(v) << (p * 4)); }

这样做的好处是：状态比较、哈希运算、内存传递都变得极快。移动一个数字块只需要两次位操作，而不是搬移整个数组。

伴随状态编码，我还预计算了一张邻接表。每个棋盘位置最多有上下左右四个移动方向，直接把可移动到的位置编号存下来，搜索时直接查表，省掉每次的边界判断。

4.2 移动排序：先走启发式最看好的方向

同一个阈值下，节点扩展顺序对搜索速度影响很大。如果每次先扩展明显更接近目标的方向，解可以更早出现；如果先往坏方向钻，往往要把很多低质量分支全部耗尽才会回头。

我每次扩展时先做一次移动排序：生成四个候选方向，分别计算移动后的启发式值hState(ns)，按升序排列后再进入递归。这个排序会让DFS优先尝试曼哈顿距离改进最大、线性冲突最少的方向，实际效果非常可观。

严格来说，为了性能还可以做增量更新，比如移动一个数字块后，曼哈顿距离只对这个数字块发生变化，线性冲突也只影响它原来所在的行列和现在所在的行列，理论上可以用增量方式维护，不必重算全局。我在参考代码里选择了直观的全量重算，因为hState本身很快，而且实际瓶颈往往在哈希查重和递归开销上，不是这几次启发式计算。如果你追求极限性能，可以把当前启发式值作为参数传给递归，移动后只更新受影响数字块的曼哈顿距离和最多四个line的冲突计数，这能省下不少重复计算。

4.3 阈值跳变是暗藏的加速器

阈值更新看似细节，优化效果却不小。如果不保存最小超限值，而是每次limit+1，那么一个最优解为60步的实例，你可能要在limit=40、41、42……一共二十多轮里反复从头搜索，累计下来的重复工作量非常惊人。用“记录所有超限f的最小值”的方式，一轮搜索结束后直接跳到下一个可行的阈值，迭代轮数往往只有个位数。这个改动只有三行代码，但效果立竿见影。

5. 实测效果：优化到底改变了什么

我用自己电脑上的一个60步左右随机实例做了对照，量级大致如下，不同实例会有波动，但整体趋势非常稳定。

路径防环是投入产出比最高的优化。很多初学者只做“不回上一步”，于是搜索树里全是空格绕一圈回到原状态的长环，节点数被这些无效路径灌满。加了路径防环后，搜索树立刻瘦了一大圈。

线性冲突的效果同样明显，它把启发式从“勉强能用”提升到“真正有方向感”。移动排序和阈值跳变更像锦上添花，但在难例上，这种“添花”决定了一块蛋糕从几秒变成几百毫秒。

6. 完整参考代码与运行说明

下面是一份可以直接编译运行的C++17参考实现。输入16个数字，代表棋盘从左到右、从上到下的格子，空格用0表示。输出求解步数和每一步移动后空格的新位置编号，也可以自行改成输出UDLR方向字符。

#include <bits/stdc++.h> using namespace std; using u64 = unsigned long long; const int ROW[16] = {0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3}; const int COL[16] = {0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3}; int tp[16], md[16][16], adj[16][4]; inline int tile(u64 s, int p) { return (s >> (p * 4)) & 15; } inline u64 putTile(u64 s, int p, int v) { return (s & ~(15ULL << (p * 4))) | (u64(v) << (p * 4)); } void init() { for (int t = 0; t < 16; t++) tp[t] = (t == 0 ? 15 : t - 1); for (int t = 0; t < 16; t++) for (int p = 0; p < 16; p++) md[t][p] = abs(ROW[p] - ROW[tp[t]]) + abs(COL[p] - COL[tp[t]]); for (int p = 0; p < 16; p++) { adj[p][0] = ROW[p] > 0 ? p - 4 : -1; adj[p][1] = ROW[p] < 3 ? p + 4 : -1; adj[p][2] = COL[p] > 0 ? p - 1 : -1; adj[p][3] = COL[p] < 3 ? p + 1 : -1; } } bool solvable(const vector<int>& b) { int inv = 0; for (int i = 0; i < 16; i++) for (int j = i + 1; j < 16; j++) { int a = b[i], c = b[j]; if (a && c && a > c) inv++; } int blank = -1; for (int i = 0; i < 16; i++) if (b[i] == 0) blank = i; return (inv + (3 - ROW[blank])) % 2 == 0; } int mdState(u64 s) { int sum = 0; for (int p = 0; p < 16; p++) sum += md[tile(s, p)][p]; return sum; } int lineConflict(u64 s, bool isRow, int idx) { vector<pair<int,int>> v; for (int i = 0; i < 4; i++) { int pos = isRow ? idx * 4 + i : idx + i * 4; int t = tile(s, pos); if (t == 0) continue; int line = isRow ? ROW[tp[t]] : COL[tp[t]]; if (line != idx) continue; v.push_back({i, isRow ? COL[tp[t]] : ROW[tp[t]]}); } sort(v.begin(), v.end()); int cnt = 0; vector<bool> used(v.size(), false); for (int i = 0; i < (int)v.size(); i++) { if (used[i]) continue; for (int j = i + 1; j < (int)v.size(); j++) { if (used[j]) continue; if (v[i].first < v[j].first && v[i].second > v[j].second) { cnt++; used[i] = used[j] = true; break; } } } return cnt * 2; } int conflictState(u64 s) { int sum = 0; for (int r = 0; r < 4; r++) sum += lineConflict(s, true, r); for (int c = 0; c < 4; c++) sum += lineConflict(s, false, c); return sum; } int hState(u64 s) { return mdState(s) + conflictState(s); } int limit; unordered_set<u64> inPath; struct Move { int dir, to; u64 ns; int nh; }; bool dfs(u64 s, int blank, int g, int& nextLimit, vector<int>& sol) { int h = hState(s); int f = g + h; if (f > limit) { nextLimit = min(nextLimit, f); return false; } if (h == 0) return true; vector<Move> moves; for (int d = 0; d < 4; d++) { int to = adj[blank][d]; if (to < 0) continue; u64 ns = s; ns = putTile(ns, blank, tile(ns, to)); ns = putTile(ns, to, 0); moves.push_back({d, to, ns, hState(ns)}); } sort(moves.begin(), moves.end(), [](const Move& a, const Move& b) { return a.nh < b.nh; }); for (auto& mv : moves) { if (inPath.count(mv.ns)) continue; inPath.insert(mv.ns); sol.push_back(mv.dir); if (dfs(mv.ns, mv.to, g + 1, nextLimit, sol)) return true; sol.pop_back(); inPath.erase(mv.ns); } return false; } vector<int> solve15(u64 start, int blank) { limit = hState(start); vector<int> sol; inPath.clear(); inPath.insert(start); while (true) { int nextLimit = INT_MAX; sol.clear(); if (dfs(start, blank, 0, nextLimit, sol)) return sol; limit = nextLimit; } } int main() { init(); vector<int> b(16); for (int i = 0; i < 16; i++) cin >> b[i]; if (!solvable(b)) { cout << "unsolvable\n"; return 0; } u64 s = 0; int blank = -1; for (int p = 0; p < 16; p++) { s = putTile(s, p, b[p]); if (b[p] == 0) blank = p; } vector<int> sol = solve15(s, blank); const string dirName = "UDLR"; cout << "moves: " << sol.size() << "\n"; for (int d : sol) cout << dirName[d]; cout << "\n"; return 0; }

代码里dirName = "UDLR"分别对应上、下、左、右。输入目标状态1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0时，程序会直接输出moves: 0。

7. 踩坑记录与个人心得

第一个坑是线性冲突配对的合法性。我前面已经提到过，如果不加“互不相交”的限制，启发式会高估真实步数。这个问题最隐蔽的地方在于：它不是每次都会出错，只有特定排列触发时结果才不对，你很容易误以为代码本身没问题，再把锅甩给IDA*实现。排查的时候可以写一个暴力BFS小规模对比，或者用足够多的随机实例做最优解步数校验，发现问题会更快。

第二个坑是路径防环集合的清理。unordered_set在深搜回溯时一定要记得erase。我调试时遇到过一次搜索假死，排查半天发现是少了一步删除，导致某个状态明明不在当前路径上，却被判定为“已访问”，照成路径被强行截断。正确性上的问题还好发现，性能上的隐性损失才是更吓人的——如果删错了，搜索可能悄无声息地漏掉最优解，跑得越快错得越离谱。

第三个坑是“能优化的都优化了”并不等于代码越复杂越好。移动排序里如果为了精确增量更新线性冲突，需要维护每行每列的冲突计数，代码复杂度会翻好几倍。我在参考代码里选择全量重算启发式，因为实测下来这已经足够快，瓶颈更多在搜索节点本身的数量。如果后续还想继续压榨性能，方向有两个：一是用模式数据库（Pattern Database）替代线性冲突，把启发式精度再往上推；二是做并行IDA*，多个线程按不同阈值区间或不同分支同时搜索。但这两个方向都会显著增加实现难度，对课程作业来说往往不划算。

回过头看，15-puzzle这个经典题目最迷人的地方，就是它把搜索算法里的每一个关键决策都摆到了台面上：状态空间太大怎么办，启发式如何设计才合法，如何用工程手段把理论算法变成能跑的代码。把这些点一个个想透，比单纯记住IDA*的三行伪代码有价值得多。

本文还有配套的精品资源，点击获取