免费下载案例集|20+数字化领先企业人才培养实践经验 了解详情
写点什么

一种更高效的 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:503207

评论

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

Nautilus Chain上首个DEX PoseiSwap即将开启IDO,潜力几何?

威廉META

干货 | IDaaS 身份即服务背后的基石

Authing

从0到1:活动报名小程序开发笔记

CC同学

Nautilus Chain上首个DEX PoseiSwap即将开启IDO,潜力几何?

大瞿科技

MongoDB源码学习:原子操作WriteUnitOfWork

云里有只猫

mongodb 源码刨析

写给程序员的可逆计算理论辨析补遗

canonical

低代码 可逆计算 范畴论

强渡大渡河!华为云GaussDB支撑华为MetaERP系统全面替换

YG科技

Microsoft Remote Desktop下载,微软远程连接工具

Rose

microsoft remote desktop 微软远程桌面连接工具 mac远程链接

开源赋能 普惠未来|腾讯寄语2023开放原子全球开源峰会

开放原子开源基金会

开源 开放原子全球开源峰会 开放原子

如何在企业中培养平台工程文化?

SEAL安全

平台工程 平台工程文化

爱了,Spring Cloud Alibaba内部微服务架构笔记真的太牛了

Java你猿哥

Java 微服务 微服务架构 Spring Cloud ssm

设计模式之不一样的责任链模式

越长大越悲伤

Java 设计模式

synchronized和Lock有什么区别?

javacn.site

Focus Matrix for Mac(智能任务管理器) v1.6.1激活版

Rose

Focus Matrix Focus Matrix破解 focus matrix mac激活版 智能任务管理器

App Cleaner & Uninstaller:mac专业的系统清理优化工具

Rose

App Cleaner 系统清理工具 苹果mac系统优化 App Cleaner 破解

【2023华为云CodeArts Build 实战训练营】云端实战-玩转编译构建

华为云PaaS服务小智

云计算 华为云 华为开发者大会2023

如何从零实现一个简单的Spring Bean容器

Java你猿哥

Java spring ssm Spring Bean Java web

Java上进了,JDK21 要来了,并发编程再也不是噩梦了

Java你猿哥

Java jdk ssm

硬核!力扣官方首发了这套1568页LeetCode算法刷题笔记(彩页版)

Java你猿哥

面试 算法 LeetCode ssm

开源赋能 普惠未来|OpenHarmony诚邀您参与2023开放原子全球开源峰会

开放原子开源基金会

开源 OpenHarmony 开放原子

Nautilus Chain上首个DEX PoseiSwap即将开启IDO,潜力几何?

鳄鱼视界

C语言编程-typedef

芯动大师

Nautilus Chain上首个DEX PoseiSwap即将开启IDO,潜力几何?

西柚子

怎么看阿里拆中台这件事

agnostic

中台架构

Xcode for Mac(开发工具)v14.3.1正式版

Rose

Xcode Mac版 Xcode中文版 Xcode破解版

Go 语言流行 ORM 框架 GORM 使用介绍

江湖十年

后端 ORM框架 ORM Go 语言 gorm

mac高质量图像浏览处理软件 GraphicConverter 12 v12.0.3(6140)中文直装版

Rose

GraphicConverter 12中文 GraphicConverter破解 mac图像浏览器 GraphicConverter下载

技术驱动,数据赋能,华为云GaussDB给世界一个更优选择

YG科技

来聊聊才离职就被拉黑禁用的这些事

HoneyMoose

Windows 高效应用快捷键

Andy

简单好用的便利贴工具:Sticky 激活版

真大的脸盆

Mac Mac 软件 便利贴工具 便利贴软件

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