{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 leelitian3 的文章《2013年国模 B题 碎纸片拼接》','https://www.xiaopingtou.net/article-50601.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
重新做下2013年国模 B题 碎纸片拼接，只怪当年太年轻啊，现在再看这道题就是单人solo的节奏。。。。。。。。
1,2太简单，就不做了，3,4选第四题做一下，第3题是中文，字方方正正，比英文要简单，第5题相比第3,4题难度没有太大提高，但太烦了，也不做了。。。
先说下参赛时的思路： 因为碎片大小只有180*72，最右一列的信息太少，所以我又多用了2列（并非全部使用），用之前1,2问拼接出来的完整纸片作为训练集合，训练了一个神经网络，用前一张纸片的末3列信息生成下一张纸片第一列的预测，然后与剩下的纸片作对比，然后选择差异小的进行拼接。先给大家看下效果
只生成第一列的预测，为了方便观看，拉宽了一点，上下各有2个像素的盲区，作对比时默认忽略。 实际效果非常好！
当时存在的问题： 1.想将碎纸片分成11组（行），不知道有效的算法 2.如果直接选择差异最小的进行组合，会出现如下图的坑爹状况。
现在顺着原来的思路重新做一下，以下正文： 一、对碎片的初步处理 读入碎片，选择0.1为阈值进行二值化，并用1减去二值化后的矩阵，此时白 {MOD}像素对应元素为0，黑 {MOD}对应1。 选择0.1是因为当时希望处理后的209个矩阵元素和的方差最小。
二、将碎片分为11组 采用K均值算法 K均值算法是一种无监督学习的聚类算法，具体可以搜一下，下面举一个二维的例子：（图片来自http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html）
要解决的问题：将平面上的点分成2组（图a） 步骤： 1.在平面上随机选择2个点作为中心c1, c2（图b） 2.计算各点到2个中心的距离，若Pi点到c1点距离比到c2近，就认为这个点属于c1，反之亦然（图c） 3.将中心点移动到各自点簇的中心（图d） 4.重复步骤2,3，重新计算距离，重新划分点簇（图e） 5.最终结果（图f）
由于起始点是随机选取的，最大迭代次数（步骤2,3的重复次数）也可以自己设定，所以最终结果也存在一定的随机性。
回到这道题，将碎片逐行求和，生成一个180维的向量（也可以简化下），作为坐标，然后执行K均值算法。 由于K均值算法不能保证均分，可以多次执行，将其中含有19个元素的点簇的逐步提取出来 第一次执行，k=12（比11效果好），分出5组 第二次，k=7，分出3组 第三次，k=3，分出1组 最后38张碎片，总是分成20+18，暂时放置。
三、逐行拼接 将组内的矩阵纵向求和，得到72维的向量，根据头尾0的长度，很容易就选出了最左和最右的碎片，记为L,R。 执行神经网络，生成一个19*19的距离矩阵Dij，元素dij表示第i张碎片的预测值与第j张碎片实际值的差异（我采用的是均方误），越小即表示这两个碎片连接的可能性越大。
现在我们要解决一个固定起点与终点的open的旅行商问题（Open Traveling Salesman Problem ，不知道open怎么翻译，开放的旅行商问题？） 简述下旅行商问题：有n座城市，一个商人要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线，即求图论中的Hamilton回路。 open就是指最后不用回到起始城市。
将此问题改写成一个0-1规划问题，然后扔到Lingo里面求得全局最优解。得到碎片的顺序，一步到位，拼接成功：
也可以对距离矩阵D略作处理，转换成不open的TSP： 令D(L,R)=充分大，D(R,L)=充分小，这样保证形成的回路中，L与R永远不会相连，R与L必定相连。
最后考察18+20的2组碎片，记为class_18,class_20： 在class_20中，搜索到了2个左侧碎片，L1，L2，而class_18中没有找到左侧碎片。那我们可以认为L1，L2有一个是属于class_18的。 将L1，L2分别与剩下的18块进行拼接，进行人工干预，此时遇到了问题，不知道什么原因，很长时间没有解出来，迫不得已，放弃传统解法，选用了遗传算法，得下面2组序列
很容易就将剩下的2组碎片分组。 传统算法可以保证是全局最优解，而遗传算法只能保证是局部最优，故所得序列不一定准确，需多次执行，进行人工干预微调。
最终，我们将209个小碎片拼接成了11个横向碎片。
四、整体拼接 将11个碎片读入并进行与之前相同的处理，对每个矩阵横向求和，得到11个180维的向量，向量中的元素即代表了对应行的黑 {MOD}像素的个数，根据0的长度，我们很容易得到了最上最下两片碎片。 现在我们希望求得行间距与字的高度。 考虑到t,y,i等字母，上下会多出那么一部分，为去除这部分的影响，做如下处理： 向量中元素如果大于100，则重新赋值为1，否则为0。 这样，统计出字高约为23，行间距约为40。 根据上方纸片的字高与行间距信息，预测下一张纸片的信息，作对比，生成一个11*11的距离矩阵，又是一个TSP问题，求解，最后得到整体的序列，拼接成功。
先说下参赛时的思路： 因为碎片大小只有180*72，最右一列的信息太少，所以我又多用了2列（并非全部使用），用之前1,2问拼接出来的完整纸片作为训练集合，训练了一个神经网络，用前一张纸片的末3列信息生成下一张纸片第一列的预测，然后与剩下的纸片作对比，然后选择差异小的进行拼接。先给大家看下效果
只生成第一列的预测，为了方便观看，拉宽了一点，上下各有2个像素的盲区，作对比时默认忽略。 实际效果非常好！
当时存在的问题： 1.想将碎纸片分成11组（行），不知道有效的算法 2.如果直接选择差异最小的进行组合，会出现如下图的坑爹状况。
现在顺着原来的思路重新做一下，以下正文： 一、对碎片的初步处理 读入碎片，选择0.1为阈值进行二值化，并用1减去二值化后的矩阵，此时白 {MOD}像素对应元素为0，黑 {MOD}对应1。 选择0.1是因为当时希望处理后的209个矩阵元素和的方差最小。
二、将碎片分为11组 采用K均值算法 K均值算法是一种无监督学习的聚类算法，具体可以搜一下，下面举一个二维的例子：（图片来自http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html）
要解决的问题：将平面上的点分成2组（图a） 步骤： 1.在平面上随机选择2个点作为中心c1, c2（图b） 2.计算各点到2个中心的距离，若Pi点到c1点距离比到c2近，就认为这个点属于c1，反之亦然（图c） 3.将中心点移动到各自点簇的中心（图d） 4.重复步骤2,3，重新计算距离，重新划分点簇（图e） 5.最终结果（图f）
由于起始点是随机选取的，最大迭代次数（步骤2,3的重复次数）也可以自己设定，所以最终结果也存在一定的随机性。
回到这道题，将碎片逐行求和，生成一个180维的向量（也可以简化下），作为坐标，然后执行K均值算法。 由于K均值算法不能保证均分，可以多次执行，将其中含有19个元素的点簇的逐步提取出来 第一次执行，k=12（比11效果好），分出5组 第二次，k=7，分出3组 第三次，k=3，分出1组 最后38张碎片，总是分成20+18，暂时放置。
三、逐行拼接 将组内的矩阵纵向求和，得到72维的向量，根据头尾0的长度，很容易就选出了最左和最右的碎片，记为L,R。 执行神经网络，生成一个19*19的距离矩阵Dij，元素dij表示第i张碎片的预测值与第j张碎片实际值的差异（我采用的是均方误），越小即表示这两个碎片连接的可能性越大。
现在我们要解决一个固定起点与终点的open的旅行商问题（Open Traveling Salesman Problem ，不知道open怎么翻译，开放的旅行商问题？） 简述下旅行商问题：有n座城市，一个商人要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线，即求图论中的Hamilton回路。 open就是指最后不用回到起始城市。
将此问题改写成一个0-1规划问题，然后扔到Lingo里面求得全局最优解。得到碎片的顺序，一步到位，拼接成功：
也可以对距离矩阵D略作处理，转换成不open的TSP： 令D(L,R)=充分大，D(R,L)=充分小，这样保证形成的回路中，L与R永远不会相连，R与L必定相连。
最后考察18+20的2组碎片，记为class_18,class_20： 在class_20中，搜索到了2个左侧碎片，L1，L2，而class_18中没有找到左侧碎片。那我们可以认为L1，L2有一个是属于class_18的。 将L1，L2分别与剩下的18块进行拼接，进行人工干预，此时遇到了问题，不知道什么原因，很长时间没有解出来，迫不得已，放弃传统解法，选用了遗传算法，得下面2组序列
很容易就将剩下的2组碎片分组。 传统算法可以保证是全局最优解，而遗传算法只能保证是局部最优，故所得序列不一定准确，需多次执行，进行人工干预微调。
最终，我们将209个小碎片拼接成了11个横向碎片。
四、整体拼接 将11个碎片读入并进行与之前相同的处理，对每个矩阵横向求和，得到11个180维的向量，向量中的元素即代表了对应行的黑 {MOD}像素的个数，根据0的长度，我们很容易得到了最上最下两片碎片。 现在我们希望求得行间距与字的高度。 考虑到t,y,i等字母，上下会多出那么一部分，为去除这部分的影响，做如下处理： 向量中元素如果大于100，则重新赋值为1，否则为0。 这样，统计出字高约为23，行间距约为40。 根据上方纸片的字高与行间距信息，预测下一张纸片的信息，作对比，生成一个11*11的距离矩阵，又是一个TSP问题，求解，最后得到整体的序列，拼接成功。