一个人的数学建模：碎纸复原

笔者一直无心参加数学竞赛，主要原因是我喜欢能够持续深入地思考一个问题，而不想被竞赛的时间限制所束缚。我并不是一个机灵的人，因此很难有竞赛所需要的“灵光一现”。大概一个多星期前全国数学建模的预赛开始了，我也饶有兴致地关注了一下，并且留意到了B题这道有趣的题目——碎纸复原，然后就开始思考算法了。那时候应该是9月13日中午，我开始了一个人的数学建模，“一个人”并不是说我一个人就组成一支队了，而是我一个人自由高效地在构思算法、摸索代码，不为比赛，只为达到目的，那种兴奋一直持续到了当晚凌晨三点。

我心目中的完美题目是那种有难度，但是又很容易看懂题目意思的题目。B题无疑就是这类题，它的要求再简单不过了，就是把一张纸撕碎成很小片，然后叫你还原而已。当然，建模的题目还做了很大的简化，碎片都是理想的矩形，这样就大大降低了难度，要不然我们还要获取碎片的形状，这就比较困难了。需要详细了解题目的可以参考本文附件。

我一开始的想法是适用ORC系统把碎片上的文字都转换成可编辑的文字格式，但是后来一想这不大可能，因为很多字都被切碎了。接着就想到如果字在被切碎的情况下，碎片的边沿是相同的，凭这个可以判断哪两个碎片是相邻的。其实整体算法就是这样了：比较碎片的边沿。但是将这个思想转化为代码还有一段很长的路。首先是怎么获取边缘的信息，最好的办法当然是把图片转换为矩阵，但是当时并没有接触过类似的东西，只有在互联网上漫天撒网，开始打算用C++，后来发现用Matlab更直接，Matlab读取图片就直接转换为矩阵了，非常方便。解决了这个问题，剩下的基本上就没有难度了，就是写一些循环和判断而已。我的程序也包括在附件之中。

有一点比较深刻的是，从13日的中午12点到14日的凌晨3点，我是从完全不懂图片矩阵处理出发，通过不断Google和百度，最终粗糙地写好了程序，中间还夹杂着我的两节体育课。（那时我刚重装完系统，收藏夹是空的，但是到我写完程序之后，收藏夹已经满了。）因此我觉得，B题大概是这次数学建模是最简单的题目了。所以我就不理解，为什么我身边的同学都没有选择B题....??（要知道，不懂代码不是主要的，一两天之内绝对可以把所需要的代码学会，关键是算法......）

完整地写好代码已经是第二天的凌晨三天了，赶紧睡了个觉，第二天早上有社团的活动要忙，中午才有时间继续玩弄，后来和子谋讨论了一下，发现他也在做B题，我们谈到附件三和附件四的复原。事实上，我昨晚只是完成了附件一和附件二的复原，那种情况比较简单，因为它只把原纸张竖直剪成了一个个矩形长条；而附件三和附件四则是把纸张剪成更小的矩形，判断难度加大，需要更多人工干预。一时我也想不出什么好办法，晚上也折腾了一下，还是没有特别好的效果。

又过了一天，子谋说附件三搞定了。果然是有压力就有动力，真佩服他！于是赶紧问了一下他的思路。真的是很妙的思路——我知道要加入人工干预，但是我不知道干预在哪里——他告诉我可以人工找出第一列，后面再进行匹配！于是乎，对我而言，这个问题就到此结束了。因为这次经历引起了我的另外一个兴趣——ORC识别系统。我在想把图片上的文字转换为可编辑的文字（比如Word）是怎么实现的，也构思了一下算法，发现很复杂，用Matlab肯定不行（晚上评价说Matlab的循环很慢），到时候多学学C++，看看能不能在这方面做点什么？

关于碎纸复原，国外也还有一个更高级一些的比赛，有兴趣的朋友可以关注：
《碎纸复原，真的能做到！》：
http://www.guokr.com/article/78259/

这比赛的难度高多了！

比较丑陋的程序，也没有进行太多注释，高手请忽略~
附件：2013数学建模B.zip

转载到请包括本文地址：https://kexue.fm/archives/2067

更详细的转载事宜请参考：《科学空间FAQ》