过年的时候,几个侄女拿着手机找到我,请教我游戏的解法,游戏画面大致如下:

sliding puzzle game

该怎么给外甥女说呢?

我这样想的,采用暴力解决方案,进行无限次的尝试,最终会找到解。 玩这个游戏最重要的是培养人的耐心,我一边说着一边操作,进行了大概几十次操作,通过了。 外甥女对我投来了崇拜的眼神,我接着说,其实这里不只是简单的暴力尝试这么简单,我们可以研究一套自动算法,找到最优的解决路径。

后面被叫去吃饭了,关于游戏的思考中断了。

回来之后,我重新思考这个问题,如何找到最优解呢?这些游戏看似简单,我们把他抽象成一个编程题,输入为一个 nn 的矩阵,其中填充了 0 到 nn-1 的数字,假设 0 是空格子,每次只能移动 0 元素相邻的元素与其交换位置,最终输出移动格子的序列号,使得矩阵顺序排列。

通过查找网络和 AI 工具,了解到确实有一些算法来帮助解决这些谜题如下:

  1. 启发式模式解法( Pattern Solving )
  2. 启发式搜索算法 A* 算法 使用曼哈顿距离( Manhattan Distance )作为启发函数
  3. 启发式搜索算法 A* 算法 使用错位方块数( Misplaced Tiles )作为启发函数
  4. 启发式搜索算法 A* 算法 使用线性冲突( Linear Conflict )作为启发函数
  5. IDA* (Iterative Deepening A)
  6. 双向广度优先搜索( 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)) 内存充足,追求最快解

受到哥飞老师影响,开发了一个站点,研究了提供滑块拼图的解决方案。

Sliding Puzzle Solver

这里提供了 6 种算法方案,经过测试发现,简单的 case ,如只需要挪动一格 方法 2-6 能给出结论,但是稍微复杂一些的情况,就卡死了。

方法 1 虽然稳定,但是对于只需要挪动一格场景,也会给出 103 步的方案

还有没有好的办法呢?

举报· 724 次点击
登录 注册 站外分享
6 条回复  
drymonfidelia 小成 前天 17:12
一步都不移,直接 start 104 步
774157009 小成 前天 17:06
管它机器推用什么什么 star 算法,我自己推就一个原则把乱序的格子缩减到 n-1*n-1 ,排序一横一竖。不是最优的方法,但是简单直观哈哈哈哈
nBlock 楼主 初学 前天 16:43
@hwdq0012 #3 谢谢 我研究下 @czfy #1 我无所谓啦,主要是工作日当牛马,哪有空发帖。 @Charlie17Li #2 老哥 看到你这句,我也笑麻了 XDD
hwdq0012 初学 前天 15:24
ddqn 强化学习适合做这个
Charlie17Li 初学 前天 15:17
@czfy 刚开始还是认真看下来,看到飞哥果断看了一眼评论区,笑麻了
czfy 小成 前天 14:31
你哥飞在这里被喷得那么厉害,没告诉你这个摸鱼论坛工作日才有流量,周末没人来么 还是退学费去吧
返回顶部