QCon北京「鸿蒙专场」火热来袭!即刻报名,与创新同行~ 了解详情
写点什么

一种更高效的 M*N 拼图自动还原算法解析

  • 2018-05-08
  • 本文字数:4393 字

    阅读完需:约 14 分钟

一, 导语

拼图游戏很适合休闲放松的时候玩,所以在上大学的一段时间里,我比较喜欢玩,用来打发无聊的时光。

恰巧 2016 年李世石与阿尔法狗对弈,虽然我不懂围棋,但也跟着围观了每场比赛。当时我想既然下围棋能够用算法完成,那自动复原拼图应该是更简单的一件事,一定会有算法。人工智能课上老师也讲过复原拼图的\(A^*\) 算法, 上网查资料拼图的复原也大都用\(A^*\) 算法。不过对于复原拼图来讲, \(A^*\) 算法和瞎蒙的差别不大,如果 M 和 N 的值较小\(A^*\) 可以适用,当 M 和 N 过大时由于搜索空间变得太大就不可行了。那么有没有一种更明确的算法,可以计算出复原拼图的路径呢?

二, 基本概念

约定 1 :M*N 拼图是由 m 行 n 列个图块构成的拼图。

约定 2:用大写字母 P 表示拼图,\(P_i\) (i=1,2,3……n) 表示拼图所处的某一状态, \(P_e\) 表示拼图的原始状态或复原状态。

定义 1:复原拼图,可以表示为

\(P_i \overset{f}{\Rightarrow} P_e \),

即算法 f 作用到 \(P_i\) 上,使其回复到\(P_e\) 状态。

定义 2:拼图从\(P_i\) 到\(P_{i+1}\) 的状态变换为\(φ·P_i=P_{i+1}\) ,简写为\(φP_i=P_(i+1)\) ,即φ作用于状态\(P_i\) 使其变化为状态\(P_{i+1}\) 。

约定 3:M*N 拼图,我们用数字 1,2,3……,mn-1 作为图块的编号,用 mn 作为缺失图块的编号。用数字 1,2,3……,mn 表示位置的编号,位置的编号为从左至右,从上至下,依次递增,即左上角位置编号为 1,右下角位置编号为 mn。

约定 4:图块 \(a_j\) 直接称为 \(a_j\)。

以 3*3 拼图为例,它的位置编号如右图:在\(P_e\) 状态下每个图块所在的位置的编号等于图块的编号。

定义3:设mn=o,拼图在状态\(P_i\) 的具体表示为\(P_i=\begin{pmatrix} 1 & 2 & 3 & \cdots & j & \cdots & k & \cdots & o\\ a_1 & a_2 & a_3 & \cdots & a_j & \cdots & a_k & \cdots & a_o \end{pmatrix}\)

, 数列\(α_1,α_2,α_3,……,α_o\) 表示图块编号,数列\(1,2,3,……,o\) 表示位置,如果\(α_j=o\) ,代表\(a_j\) 为缺失的那个图块。

定义4:设\(a_i 所在的位置编号是C_{α_i},表示为\) \(a_j (C_{a_j })\)

或\(a_j (\frac{C_{a_j}-C_{a_j} (modn)}{n},C_{a_j} (modn)),\frac{C_{a_j}-C_{a_j} (modn)}{n}\) 为行号\(C_{a_j } (modn)\) 为列号。

拼图这样的表示方法和置换群的表示方法相同,事实上根据群的定义,拼图的所有状态构成群,可以吧拼图状态的变化看成置换群运算。

三, 等价性证明

本节将证明拼图状态变化与置换运算的等价,这是整个算法的理论基础。

证明:设\(P_i=\begin{pmatrix} 1 & 2 & 3 & \cdots & j & \cdots & k & \cdots & o\\ a_1 & a_2 & a_3 & \cdots & a_j & \cdots & a_k & \cdots & a_o \end{pmatrix}\) ,\(a_j=o\) ,且\(a_k\) 与缺失\(a_j\) 相邻,将\(a_k\) 移动到位置 j,由此\(P_{i+1}=\begin{pmatrix} 1 & 2 & 3 & \cdots & j & \cdots & k & \cdots & o\\ a_1 & a_2 & a_3 & \cdots & a_j & \cdots & a_k & \cdots & a_o \end{pmatrix}\)

在置换群中有 \((j,k)∙P_i=P_{i+1}\),在前文已经定义\(φ·P_i=P_{i+1}\) ,由\(\begin{cases} &(j,k)\cdot P_i=P_{i+1} \\ &\varphi \cdot P_i=P_{i+1} \end{cases}\Rightarrow (j,k)\Leftrightarrow \varphi \)

,即φ等价为对换。拼图一系列状态的变化,可以表示为一系列对换运算。

四, 算法描述

现在我们已经有了描述拼图的数学工具,本部分给出算法的描述。

1,自上而下,自左至右,按行复原,并设当前要复原的图块为\(a_j (C_{a_j} )\) 。

2,如果\(\frac{a_j-a_j (modn)}{n} <m-1\) ,\(a_j (modn) <n-1\) , 直接将\(a_j\) 移回位置\(a_j\) 。

3,如果\(\frac{a_j-a_j (modn)}{n} <m-1\) , \(a_j (modn) =n-1\), 将 \(a_j\) 移动到位置 \(a_j+1\),

再将\(a_j+1\) 移动到位置\(a_j+1+n\) , 最后同时复原这两个图块。

4,如果\(\frac{a_j-a_j (modn)}{n} =m-1\) ,\(a_j (modn) <n-1\) , 将\(a_j\) 移动到位置\(a_j+n\) ,

再将\(a_j+n\) 移动到位置 \(a_j+n+1\),最后同时复原这两个图块。

5,如果\(\frac{a_j-a_j (modn)}{n} =m-1\) , \(a_j (modn) =n-1\),顺时针或逆时针移动最后三块,直至回复到原来位置。至此拼图复原。

仅仅有这个算法还不够,我们还需要一个可以将\(a_j\) 移动到指定位置的算法。

五, 相对位置分析—— \(a_j\) 至目标

将某一图块移动到某一位置,是实现拼图复原基本思路的关键,也是最困难的步骤。这里分两步来实现:

  1. 将 mn 移动到\(a_j\) 附近,且 \(a_j\) 位置不变 。
  2. 将\(a_j\) 移动到目标位置。

如图:

mn 可能处在相对\(a_j\) 的 8 个方位中的一个,将 mn 移动到 \(a_j\) 的正上、正下、正左、正右。 相对位置\(a_j\) 则有 16 种可能的方位。也就是说如果根据相对方位来规划路线需要分析 512 种情况。当然真实情况数要少于 512 种。

约定 5:命名\(\rho_1\) 为正上,\(\rho_2\) 为右上,\(\rho_3\) 为正右,\(\rho_4\) 为右下, \(\rho_5\) 为正下, \(\rho_6\) 为左下,\(\rho_7\) 为正左,\(\rho_8\) 为左上。

定义 5:\(\psi (x)\) 为目标位置, \(\psi\) 为目标。

\(\psi\) 是代表目标的占位符,并无其它意义。我们的目的是通过一系列对换将\(a_j\) 移动到目标位置\(\psi (x)\) 。

可以将\(\rho_9\) 至\(\rho_{16}\) 方位看成\(\rho_1\) 至 \(\rho_8\) 方位的复合,如同分解向量一样将其分解为两个方位,这样可以将 16 种情况减少到 8 种。

约定6:先正向再斜向。

定义6:\(\rho_a=\rho_b+\rho_c\) (8<a<=16;b=1,3,5,7;c=2,4,6,8), 符号+ 表示方位的复合运算。

表1 列出了\(\rho_9\) 至 \(\rho_{16}\) 的分解方式:

表1:方位分解表

分析基本的8 种方位,已知\(a_j (C_{a_j}) \) 可得\(\psi (x)\) ,推出:\(\begin{cases} & a_j(\frac{C_{a_j}-C_{a_j}modn}{n},C_{a_j}modn)\\ & \psi (\frac{x-xmodn}{n},xmodn) \end{cases} \)

定义7:\( \frac{x-xmodn}{n}- \frac{C_{a_j}-C_{a_j}modn}{n}=\Delta r\),\(\Delta r\) 为行差。

定义8:\(xmodn-C_{a_j}modn=\Delta c\) , \(\Delta c\) 为列差。

定义9:\(|\Delta r|-|\Delta c|=\Delta d\) , \(\Delta d\) 为行列差, 即行差的绝对值减去列差的绝对值。

表2 列出了方位与坐标差值的关系

表2:方位关系表

表3 列出了复合方位与坐标差值的关系

表3:复合方位关系表

六, 相对位置分析——mn 至\(a_j\)

mn(它是缺失的那个,但我们仍认为它是一个存在的图块,mn 的特殊性是只有它才能和周围的图块相交换)至\(a_j\) 的相对位置仍然是任意的,但是将 mn 移动到想要的位置则简单一些。分析两者相对位置的原因是,\(a_j\) 的移动需要借助 mn,所以我们要根据\(a_j\) ,将 mn 移动到合适的位置。有四个带选取的位置分别是:\(C_{a_j }-1,C_{a_j }+1,C_{a_j}-n,C_{a_j}+n\)

如图划分了合适的位置与方位\(\rho\) 的关系,

表 4 与上图对应

表 4

不管两者如何对应,我们的目的本质是将 mn 移动到四个位置中的一个。

约定 7:将 mn 移动到\(a_j\) 附近,优先竖向移动,再横向移动。

七, 拼图移动策略

我们首先要考虑如何把 mn 移动到合理的位置,上图只描述了可能的移动路径。在真正的情况中可以遵守以下策略:优先竖向移动,mn 在到达合理位置是不应改变\(a_j\) 的位置。

移动\(a_j\) 到目标位置,要完成这个任务,其实更应关注 mn 如何移动,mn 作为缺失块,周围图块只能移动到 mn 所在的位置。这时 mn 的移动轨迹,具有周期性,mn 的轨迹也能用公式表示出来。

八, 拼图移动定理

我们已将定义了很多概念,也做了很多约定。但是到目前为止我们还没有充分的利用起它们。尤其是拼图的状态变化可等价于对换运算,我们还未用到。后面的公式显示了数学的威力。

已知 \(a_j (C_{a_j} )\),\(mn(C_{mn} )\) , \(\psi (x_1),\psi (x_2)\) 为 \(a_j\) 要到达的目标, \(\Delta r_1, \Delta c_1, \Delta d_1\) 为\(a_j\) 与目标\(\psi (x_1)\) 的行差、列差、行列差, \(\Delta r_2, \Delta c_2, \Delta d_2\) 为 mn 与目标\(\psi (x_2)\) 的行差、列差、行列差。

定理 1:将 mn 竖向移动\(\Delta r_2\) (-m<\(\Delta r_2\) <m) 行, 拼图起始状态为\(P_i\) , 等价于

定理 2:将 mn 横向移动\(\Delta c_2\) (-n<\(\Delta c_2\) <n ) 列,拼图起始状态为 \(P_i\), 等价于

定理 3:将\(a_j\) 竖向移动\(\Delta r_1\) (-m<\(\Delta r_1\) <m) 行,拼图起始状态为\(P_i\) , 等价于

定理 4:将\(a_j\) 横向移动\(\Delta c_1\) (-n<\(\Delta c_1\) <n ) 列,拼图起始状态为\(P_i\) , 等价于

定理 5:将\(a_j\) 斜向移动 \(\Delta r_1\) (-m<\(\Delta r_1\) <m) 行\(\Delta c_1\) (-n<\(\Delta c_1\) <n ) 列,且 \(|\Delta r_1|=|\Delta c_1|\),

拼图起始状态为\(P_i\) , 等价于

定理中的公式很复杂,但是有了它们我们设想的算法便能实现。

九, 真实情况分析

复原拼图遇到的路径状况数目要少一些,而且有以下规律:

设当前刚复原\(a_j\) 且\(0<jmodn<n-1\) 。

  1. mn 所在的位置必然在 j+1 或 j+n。
  2. \(a_{j+1}\) 必然在 mn 的左下、正下、右下、正右、右上、正左方位中的一个。
  3. \(a_{j+1}\) 可能在位置 j+1 或任何一个大于 j+1 的位置。
  4. 如果\(a_{j+1}\) 不在位置 j+1 ,则\(j+1-(j+1)modn<C_{a_j}-C_{a_j} modn\) 。

这四条规律可以稍微降低算法实现的难度。同时复原拼图时有一条限制:不能破坏已复原的图块。

十, 与\(A^*\) 算法的比较

这个算法暂且命名为:拟人策略算法。

在文章开头我说过 \(A^*\) 算法和瞎蒙没啥区别,如果不在这里说出理由,恐怕要受人指摘了,毕竟人工智能课上老师可是重点讲过\(A^*\) 算法。由于我没有相关\(A^*\) 算法的实现,在这里只在理论上比较两种算法的优劣,并分别论述。

可还原拼图的状态数呈阶乘式的增长,4*4 拼图的状态数为\(\frac{16!}{2}\) ,5*5 拼图的状态数为\(\frac{25!}{2}\) ,m*n 拼图的状态数为 \(\frac{(mn)!}{2}\)。\(A^*\) 算法采用预估函数剪去不必要的分支,假设这个预估函数由图块与本来位置的距离之和决定。 \(P_i\) 的预估值不会超过\((mn)^3\) ,随着 m*n 的增大会有\((mn)^3\ll \frac{(mn)!}{2}\) 。当 m*n 较小时,剪枝还能实现,当 m*n 较大时 \(A^*\) 算法必然要搜索巨大的状态空间,这会是灾难。另外,预估函数和拼图复原并不会有必然的关系,某一状态预估函数的值小不一定意味着它好复原。

拟人策略算法与之最大的区别是它不进行状态空间搜索,它按照人类复原拼图的模式进行复原。实际上我们可以估算出一个人复原拼图需要多少次交换,按照上文给出的算法,\(a_j\) 回到自己的位置大概会经过\(\frac{m+n}{2}\) 格如果\(a_j\) 每移动一格需进行 6 次交换,对于 m*n 个图块回到自己的位置会需要\(\frac{m+n}{2}*6*mn=3mn(m+n)\) ,将 mn 移动到 \(a_j\) 附近估计需\(\frac{m+n}{2}\) 次交换,m*n 个图块就需要\(0.5mn(m+n)\) 次交换,两者总计 \(3.5mn(m+n)\) 次交换。如果实现这个算法,它的时间复杂度可能会正比于\((mn)^2\) 。这是个很粗略的估计,仅供参考。

2018-05-08 17:503514

评论

发布
暂无评论
发现更多内容

“麻烦”的处理流程

zhoo299

随笔杂谈

做一个有原则的码农可好?

Dawn

极客大学架构师训练营

产品视角看推荐算法

峰池

人工智能 算法 产品经理 推荐算法

618你的系统顶住了么?系统发生重大灾难难道只能“删库跑路”?

punkboy

小师妹学JVM之:GC的垃圾回收算法

程序那些事

JVM 小师妹 JIT GC 签约计划第二季

架构师训练营第二章课后作业

叮叮董董

架构师训练营第二周

小树林

给行动找个理由

Neco.W

行动派 决策

为什么坐车会晕车呢

石云升

生活,随想 日常思考 晕车

ARTS打卡Week 04

teoking

ios LeetCode ARTS 打卡计划

品软件架构原则模式之美

老姜

架构师训练营第2周学习总结

Season

极客大学架构师训练营

第二次作业总结

朱月俊

基本的面向对象原则(Basic OO principles)

旭东(Frank)

编程思维 极客大学架构师训练营

架构师训练营二期作业

老姜

第二次作业

朱月俊

架构师训练营-第二章-依赖倒置原则&接口隔离原则

而立

极客大学架构师训练营

第二周学习总结

武鹏

架构师训练营 - 第二周架构师实现自己架构的主要手段

zcj

极客大学架构师训练营

哪些框架是遵循依赖倒置原则的?

朱月俊

老大吩咐的可重入分布式锁,终于完美的实现了!!!

楼下小黑哥

Java redis 分布式锁

依赖倒置和案例

王锟

这也太拧巴了吧?结局意想不到

非著名程序员

程序员 程序人生 提升认知

数据库周刊28│开发者最喜爱的数据库是什么?阿里云脱口秀聊程序员转型;MySQL update误操作;PG流复制踩坑;PG异机归档;MySQL架构选型;Oracle技能表;Oracle文件损坏处理……

墨天轮

数据库

什么是依赖倒置原则,为什么有时候依赖倒置原则又被称为好莱坞原则?

朱月俊

用接口隔离原则优化 Cache 类的设计

朱月俊

架构师训练营第二章总结

叮叮董董

依赖倒置原则

极客李

一个包子铺看懂 I/O 模型演变

小眼睛聊技术

Java 程序员 架构 后端 nio

千万不能让程序员给娃娃取名字

码农神说

程序员

第二周作业

武鹏

一种更高效的M*N拼图自动还原算法解析_语言 & 开发_魏治涛_InfoQ精选文章