2013B 碎纸片拼接复原的数学方法

《2013B 碎纸片拼接复原的数学方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２卷第５－６期数学建模及其应用Ｖｏｌ．２Ｎｏ．５－６２０１３年１１月ＭａｔｈｅｍａｔｉｃａｌＭｏｄｅｌｉｎｇａｎｄＩｔｓＡｐｐｌｉｃａｔｉｏｎｓＮｏｖ．２０１３檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺殣殣檺檺全国大学生数学建模竞赛专栏檺檺殣殣檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺碎纸片拼接复原的数学方法薛毅（北京工业大学应用数理学院，北京１００１２４）摘要：就２０１３年“高教社杯”全国大学生数学建模竞赛Ｂ题“碎纸片的拼接复原”提出了一种用“纯数学手段”完成拼接复原的方法，可概括为３步：ＴＳＰ，聚类分析和双面信息的利用。根据题目要求给出了３个

2、步骤中人工干预的方式与时间节点。关键词：旅行商问题；聚类分析；碎纸片拼接中图分类号：Ｏ２２１．７；Ｏ２１２．４；ＴＰ３９１．４１文献标志码：Ａ文章编号：２０９５－３０７０（２０１３）５－６－０００９－０５碎纸复原问题最著名的例子应该是２０１１－１０－２９美国国防部高级研究计划局宣布的碎纸复原挑战赛。该［１］项赛事共有９０００多支队伍参加，获胜队将得到５００００美元的奖金。今年的竞赛题“碎纸片的拼接复原”看似与挑战赛相同，但问题的难度有着本质的不同。首先，需要拼接复原的文件是纯文本的打印文件，并不是挑战赛的手写文件；其次，碎纸片由计算机生成，

3、也就是说，碎纸片没有毛边，并不是真正由碎纸机粉碎而成的，这样就大大降低了问题的难度，使学生有可能在３天的时间内完成。为了确保学生在３天的时间内完成竞赛内容，命题人特意将问题分解成３个子问题：问题１仅考虑只有纵切情形的碎纸片；问题２碎纸片是由纵切与横切两种情形得到的；问题３双面打印文件碎纸片的拼接复原。这３个问题实际上在告诉我们解题的思路，因此，解决问题的方案也分成３步：１）建立仅有纵切情形的数学模型—旅行商问题（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ，ＴＳＰ）；２）先将碎纸片还原到各自所在的行—聚类分析，再使用１）中的方法（ＴＳＰ

4、）复原成正确的“横条”，最后使用人工干预的方法拼接成原始文件；３）使用碎纸片的双面信息，提高行聚类的准确率。根据题目要求，在这３步中均要考虑人工干预的方式，以及干预的时间节点。１仅有纵切的情形—旅行商问题１．１数据的读取与处理读取数据是求解问题的关键。读取数据的方法是非常简单的，大部分的计算机语言都可完成，例如Ｍａｔｌａｂ软件中的ｉｍｒｅａｄ函数。读取数据后，可以将数据作二值化处理。直观来讲，二值化处理的目的是使黑的更黑，白的更白，便于后面的聚类与拼接。笔者曾做过经二值化和未经二值化处理的数据的对比实验，结果表明，数据经二值化处理后其复原率

5、有一定程度的提高。１．２建模—旅行商问题建模思想是基于“相邻的两条碎纸片的灰度应该比较接近”这一事实提出的，它同时也给出了完成问题１求解的启发式算法。１）找出整个文件中最左侧的碎纸片（碎片的左侧为空白，数值均为２５５，设碎纸片编号为ｋ１，置ｉｎｄｅｘ＝收稿日期：２０１３－１１－１３通讯作者：薛毅，Ｅ－ｍａｉｌ：ｘｕｅｙｉ＠ｂｊｕｔ．ｅｄｕ．ｃｎ·９··竞赛专栏·碎纸片拼接复原的数学方法２０１３年１１月ｋ１，Ｉ＝｛１，２，…，１９｝＼｛ｋ１｝，ｉ＝１；２）如果ｉ＝１９，则停止计算，输出拼接复原图序号ｉｎｄｅｘ，否则计算第ｊ（ｊ∈Ｉ）个碎纸片最

6、左侧的列与第ｋｉ个碎纸片最右侧的列之间的距离，记距离最小的碎纸片的编号为ｋｉ＋１；３）置ｉｎｄｅｘ＝ｉｎｄｅｘ∪ｋｉ＋１，Ｉ＝Ｉ｛ｋｉ＋１｝，ｉ＝ｉ＋１，转２）。由于仅纵切情形的碎纸片两侧的信息量较大，上述启发式算法可以得到附件１和附件２的拼接复原图，而且也不需要人工干预。这种方法看似很好，但也存在两个致命的缺点：第一，它是一种局部寻优方法，而且计算复杂度高；第二，这种方法不便于推广，不利于在问题２和问题３的求解中使用。为克服上述算法的缺点，提出一种全局寻优的方法，即将问题转化成旅行商问题（ＴＳＰ）。将碎纸片看作城市（共１９个），定义城市间

7、的距离，即碎纸片之间的距离，定义方法为：对于碎纸片Ａ和碎纸片Ｂ，用碎纸片Ａ最右侧的列与碎纸片Ｂ最左侧的列之间的距离定义为两者之间的距离，同理可以定义碎纸片Ｂ到碎纸片Ａ的距离。用此方法可以定义两个碎纸片之间的距离，形成一个一个非对称的距离矩阵。注意到，整个文件最左侧碎纸片的左侧与最右侧碎纸片的右侧均为空白，这样就可以形成圈。因此，仅纵切情形的拼接复原问题转化求解最小距离的Ｈａｍｉｌｔｏｎ圈，即旅行商问题。１．３距离的定义距离的定义有多种，如果数据没有二值化，可以使用绝对值距离（或称棋盘距离）、Ｅｕｃｌｉｄ距离、Ｃｈｅｂｙｓｈｅｖ距离等。二值化

8、后的数据可以使用Ｈａｍｍｉｎｇ距离或Ｊａｃｃａｒｄ距离。本文使用的是Ｊａｃｃａｒｄ距离，定ｍ２义为ｄｉｊ＝，其中，ｍ１为两个向量中１－１配对的总数，ｍ０为０－０配对的总数，ｍ２为