摘要：本文通过研究三种不同特点的碎片复原,建立人工干预次数较少的碎片复原模型.模型一,将碎片排序抽象为图论中的哈密尔顿路径,给出了基于旅行商问题的拼接策略.其中碎片为图的顶点,碎片间的匹配程度(匹配距离)为图的边权.模型二,给出基于文本行特征的碎片行分组算法,对行分组碎片进行横向拼接得到复原的碎片行,再对碎片行进行纵向拼接,得到最终复原结果.其两次拼接皆采用模型一的拼接策略.模型三,基于模型二,考虑到双面信息而采用正反匹配距离,此外,对碎片行做纵向拼按时,将模型一中的拼接策略扩展为多旅行商(2个旅行商)问题的拼接策略,即一条旅行商路径代表纸张的一面,另一条旅行商路径代表纸张的另一面.
