BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

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

| 作者 魏治涛 关注 0 他的粉丝 发布于 2018年5月9日. 估计阅读时间: 18 分钟 | GMTC大前端的下一站,PWA、Web框架、Node等最新最热的大前端话题邀你一起共同探讨。

一, 导语

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

恰巧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\) 。这是个很粗略的估计,仅供参考。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT