国家集训队2003论文集 金恺

《国家集训队2003论文集 金恺》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起长沙市长郡中学金恺正方形剖分问题问题描述：将n×n个小格组成的大正方形分割成若干个较小的整数边长的正方形，要求分成的小正方形数目最小。范围：1≤n≤32。编程环境：FreePascal。可用64MB空间n=7时的一个最小数目的剖分方案，需要9个小正方形。分析当n为偶数时最少需要4个小正方形：1234n/2n/2n/2n/2当n为奇数时，很难发现有什么数学规律。设fi,j表示一个i×j的矩形最少可以被剖分成多少个小正方形:n=7时，求出结果为10，并不是最优值。原因：最优方案不一定能被某条直线分割。ijkj-k

2、ijki-kn711131719232931其他fn,n1012121414161616相同最优值911111313131415相差111113210fn,n仅是一个可行解，不过其值与最优解十分接近的。目前只能用搜索！优化：搜索之前先用上述动态规划方程求出一个较优值，限制搜索层次。搜索量巨大，仅用这一条优化，效率十分低下。如何搜索？搜索的对象和顺序从大量的搜索题(比如说IOI的Depot等)可以看出，搜索的顺序和对象是十分重要的，本题应该用什么作为搜索对象，搜索顺序又是怎样呢？搜索的对象：每个小正方形的位置和边长。一种最简单的搜索顺序为：给大正方形中第i行第j

3、列的小格编号(i-1)n+j，每次选择编号最小的未覆盖的小格作为小正方形左上角的坐标，然后枚举它的边长。速度太慢，需要大量剪枝!剪枝1、避重性剪枝：(对称性)规定左上角的那个小正方形的边长小于等于其他三个角上的小正方形的边长，右上角的小正方形边长大于等于左下角的小正方形边长。2、平方和剪枝：11=12+12+32。设Sumi表示至少要多少个整数才能使得这些整数的平方和等于i,则改进搜索的顺序按上述搜索顺序，每一步中大正方形被覆盖的区域都是凹凸不平的(如右图)，不方便剪枝，搜索效率也比较低。有没有更高效的搜索顺序呢？既要不遗漏(正确性)、不重复(高效性)；又要能

4、够方便的剪枝。猜想：任何剖分方案是否都能通过若干条剖分线把一个个小正方形剖分出来呢？类矩形凸出部分凹入部分剖分线——一条从左下角到右上角的只往右或往上走的曲线探寻新的搜索顺序定义：证明大正方形就是一个类矩形，他的右边界和下边界连起来就是一条剖分线；对于任意一个类矩形，从下到上的检查每一个凸出部分的右下角格子所在的小正方形，总有一个能够被分割出来。新的搜索顺序搜索时每次选择一个凹入部分的左上角作为小正方形的左上角，小正方形的边长小于等于这个凹入部分的宽，就能够保证在任何时候已覆盖区域为一个类矩形。缺点：相同的剖分方案可能会被搜索多次。123132规定前一个小正方

5、形不完全处于后一个的上部。新增剪枝1、一个类矩形若包含x个凸出部分，则它至少要x个小正方形才能拼出，因为每个凸出部分右下角的小格都要属于不同的小正方形中。实践证明：大多数情况下这个下界比Sumi要精确得多。2、对右图所示的两种情况：它们沿“左上—右下”对角线是对称的，可以只搜它们中的任一种情况。搜索效率：在最慢时(n=31)只要20s左右就能够出解了。(测试环境(R)4CPU1.7GHz)还有什么方法能够使搜索效率再大幅提高呢？看下边这棵搜索树：当搜到蓝色结点时，若已经使用了x个小正方形,而这个节点到目标结点的最小深度为y(也就是说最少可以用y个小正方形拼完此

6、时的未覆盖区域)，那么若往下搜，最优值显然刚好为x+y。最小深度为Y那么，若已知y的值，蓝色节点就变为了搜索树中的叶子节点，因为搜到它就可直接回溯了。若求出了大量的节点的y值，就能使许多非叶子节点变为叶子节点，总节点数就会大大减少。这就为进一步增加搜索效率找到了契机。但是，有两个新问题需要解决：问题1、如何求某个节点到目标节点的最优值呢？问题2、应该求哪些节点到目标节点的最优值呢？状态的表示首先，某个节点到目标节点的最优值只与当前未覆盖区域的形状有关，所以只要以未覆盖区域作为当前状态。那么如何描述一个未覆盖区域呢？可用逆序n元组(a1,a2,…,an)，ai≥

7、ai+1,n≥a1表示，其中ai表示第i+n-1行未被覆盖的小格子数目。分析：一个状态需要占用n个字节，空间太多，而且比较两个状态是否相等的时间复杂度为O(n)，速度也是非常慢的。有没有更好的方法呢？优化状态的表示不妨令bi=ai-ai+1(0≤i≤n，这里a0=n，an+1=0)，则有bi≥0，∑bi=n。由组合数学知识可知b的个数为：把n个无标号的小球放入n+1个有标号的盒子中的方案数，等于C2nn，当n=31时也不超过1e18，故可考虑用一个comp类型数对应一个多元组b。而b与a也是一一对应的，所以可用一个comp类型整数直接描述一个状态。如何将a与一

8、个整数互相对应呢？设Toti,j表示：