suizhiji

suizhiji

笔者一直无心参加数学竞赛,主要原因是我喜欢能够持续深入地思考一个问题,而不想被竞赛的时间限制所束缚。我并不是一个机灵的人,因此很难有竞赛所需要的“灵光一现”。大概一个多星期前全国数学建模的预赛开始了,我也饶有兴致地关注了一下,并且留意到了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://www.kexue.fm/archives/2067

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

如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。

如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!

如果您需要引用本文,请参考:

苏剑林. (Sep. 22, 2013). 《一个人的数学建模:碎纸复原 》[Blog post]. Retrieved from https://www.kexue.fm/archives/2067

@online{kexuefm-2067,
        title={一个人的数学建模:碎纸复原},
        author={苏剑林},
        year={2013},
        month={Sep},
        url={\url{https://www.kexue.fm/archives/2067}},
}