文档介绍：2013 高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参
赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网
上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或
其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文
引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。如有
违反竞赛章程和参赛规则的行为,我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展
示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。

我们参赛选择的题号是(从 A/B/C/D 中选择一项填写): B
我们的参赛报名号为(如果赛区设置报名号的话): 20001040
所属学校(请填写完整的全名): 国防科学技术大学
参赛队员(打印并签名) :1. 向航
2. 王帆
3. 郭树璇
指导教师或指导教师组负责人(打印并签名):
(论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。以上内容
请仔细核对,提交后将不再允许做任何修改。如填写错误,论文可能被取消评奖资格。)

日期: 2013 年 9 月 16 日

赛区评阅编号(由赛区组委会评阅前进行编号):
2013 高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号(由赛区组委会评阅前进行编号):

赛区评阅记录(可供赛区评阅时使用):

评
阅
人

评
分

备
注

全国统一编号(由赛区组委会送交全国前编号):

全国评阅编号(由全国组委会评阅前进行编号):
基于旅行商规划模型的碎纸片拼接复原问题研究
摘要
本文分别针对 RSSTD(Reconstruction of Strip Shredded Text Document)、
RCCSTD(Reconstruction of cross-cut Shredded Text Document)和 Two-Sides
RCCSTD 三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我
们对于 RSSTD 问题,建立了基于二值匹配度的 TSP 模型,并将其转化为线性规
划模型,利用贪心策略复原了该问题的中文和英文碎片;然后对于 RCCSTD 问
题,由于中英文字的差别,我们分别建立了基于改进误差评估的汉字拼接模型和
基于文字基线的误差评估的英文字拼接模型,并利用误差评估匹配算法,复原了
该问题的中文和英文碎片;随后我们针对正反两面的 RCCSTD 问题,利用基线
的概念将正反两面分行,转化为 RCCSTD 问题,并复原了该问题的英文碎片。
最后,我们对模型的算法和结果进行了检验和分析。
◎问题一:我们针对仅纵切的情况,首先将图像进行数字化处理,转换为了
二值图像,然后得到各图像的边缘,并计算所有碎片与其他碎片边缘的匹配程度。
然后,根据两两碎片之间的匹配程度建立了 TSP 模型,并将其划归为线性规划
模型。最终,我们根据左边距的信息确定了左边第一碎片,随后设计了基于匹配
度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对
于中英文两种情况适用性均较好,且该过程不需要人工干预。
◎问题二:我们针对既纵切又横切的情况,由于中英文的差异性,我们在进
行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的
碎片,随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评
估模型,将剩余的碎片进行分行聚类,然后再利用基于误差评估的行内匹配算法
对行内进行了拼接,最终利用行间匹配算法对行间的碎片进行了再拼接,最终得
到了拼接复原结果。对于拼接过程中可能出现误判的情况,我们利用 GUI 编写
了人机交互的人工干预界面,用人的直觉判断提高匹配的成功率和完整性。
◎问题三:我们针对正反两面的情况,首先根据正反基线信息,分别确定了
左右两边的碎片,然后利用基线差值将其两两聚类,聚类以后其正反方向也一并
确定,随后我们将其与剩余碎片进行分行聚类,最终又利用行内匹配和行间匹配
算法得到了