过年的时候，几个侄女拿着手机找到我，请教我游戏的解法，游戏画面大致如下：
该怎么给外甥女说呢？
我这样想的，采用暴力解决方案，进行无限次的尝试，最终会找到解。 玩这个游戏最重要的是培养人的耐心，我一边说着一边操作，进行了大概几十次操作，通过了。 外甥女对我投来了崇拜的眼神，我接着说，其实这里不只是简单的暴力尝试这么简单，我们可以研究一套自动算法，找到最优的解决路径。
后面被叫去吃饭了，关于游戏的思考中断了。
回来之后，我重新思考这个问题，如何找到最优解呢？这些游戏看似简单，我们把他抽象成一个编程题，输入为一个 nn 的矩阵，其中填充了 0 到 nn-1 的数字，假设 0 是空格子，每次只能移动 0 元素相邻的元素与其交换位置，最终输出移动格子的序列号，使得矩阵顺序排列。
通过查找网络和 AI 工具，了解到确实有一些算法来帮助解决这些谜题如下：
- 启发式模式解法（ Pattern Solving ）
- 启发式搜索算法 A* 算法 使用曼哈顿距离（ Manhattan Distance ）作为启发函数
- 启发式搜索算法 A* 算法 使用错位方块数（ Misplaced Tiles ）作为启发函数
- 启发式搜索算法 A* 算法 使用线性冲突（ Linear Conflict ）作为启发函数
- IDA* (Iterative Deepening A)
- 双向广度优先搜索（ Bidirectional BFS ）
他们的时间复杂度和空间复杂度各不相同，我将他们部署到前端页面，发现他们的效果对不同的场景差异很大。
以下是 deepseek 的对他们时间空间复杂度对比
对比总结
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| Pattern Solving | O(1) | O(1) | 快速解决特定简单局面 |
| A* (Manhattan) | ~O(b^(d/2)) | O(b^d) | 需平衡速度与内存的中等规模问题 |
| A* (Misplaced Tiles) | ~O(b^d) | O(b^d) | 简单场景，启发式要求不高 |
| A* (Linear Conflict) | ~O(b^(d/2)) | O(b^d) | 复杂障碍下的高效求解 |
| IDA* | O(b^d) | O(b*d) | 内存受限，允许牺牲时间换取空间 |
| Bidirectional BFS | ~O(b^(d/2)) | O(b^(d/2)) | 内存充足，追求最快解 |
受到哥飞老师影响，开发了一个站点，研究了提供滑块拼图的解决方案。
这里提供了 6 种算法方案，经过测试发现，简单的 case ，如只需要挪动一格 方法 2-6 能给出结论，但是稍微复杂一些的情况，就卡死了。
方法 1 虽然稳定，但是对于只需要挪动一格场景，也会给出 103 步的方案
还有没有好的办法呢？
 |
1
czfy 1 天前 via Android  4
你哥飞在这里被喷得那么厉害，没告诉你这个摸鱼论坛工作日才有流量，周末没人来么
还是退学费去吧 |
 |
2
Charlie17Li 1 天前
@czfy 刚开始还是认真看下来，看到飞哥果断看了一眼评论区，笑麻了
|
 |
3
hwdq0012 1 天前
ddqn 强化学习适合做这个
|
 |
4
nBlock OP |
 |
5
774157009 1 天前
管它机器推用什么什么 star 算法，我自己推就一个原则把乱序的格子缩减到 n-1*n-1 ，排序一横一竖。不是最优的方法，但是简单直观哈哈哈哈
|
 |
6
drymonfidelia 1 天前
一步都不移，直接 start 104 步
|
Select Language