文档介绍：探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起长沙市长郡中学金恺分析当n为偶数时最少需要 4个小正方形: 1234 n/2 n/2 n/2 n/2 当n为奇数时,很难发现有什么数学规律。????????????????????????????0,0 )0( )0( min ,1 00 0 ,, ,, , jiNjijijkff ikff Niji ji f kjiki jkijk ji或或设f i,j表示一个 i×j的矩形最少可以被剖分成多少个小正方形: n=7 时,求出结果为 10 ,并不是最优值。原因:最优方案不一定能被某条直线分割。 ij k j-k ij k i-k 012311111 相差 15 16 31 14 16 29 13 16 23 13 14 19 13 14 17 11 12 13 11 12 11 9 10 7相同其他最优值 f n,nnf n,n仅是一个可行解,不过其值与最优解十分接近的。目前只能用搜索! 优化:搜索之前先用上述动态规划方程求出一个较优值,限制搜索层次。搜索量巨大,仅用这一条优化,效率十分低下。如何搜索? 搜索的对象和顺序从大量的搜索题( 比如说 IOI 的 Depot 等) 可以看出, 搜索的顺序和对象是十分重要的,本题应该用什么作为搜索对象,搜索顺序又是怎样呢? 搜索的对象:每个小正方形的位置和边长。一种最简单的搜索顺序为:给大正方形中第 i 行第 j列的小格编号(i-1)n+j ,每次选择编号最小的未覆盖的小格作为小正方形左上角的坐标,然后枚举它的边长。速度太慢,需要大量剪枝! ???????????0)(1} min{ 00 2iij Sum i Sum ji i剪枝 1、避重性剪枝: (对称性)规定左上角的那个小正方形的边长小于等于其他三个角上的小正方形的边长,右上角的小正方形边长大于等于左下角的小正方形边长。 2、平方和剪枝: 11=1 2 +1 2 +3 2。设 Sum i表示至少要多少个整数才能使得这些整数的平方和等于 i,则改进搜索的顺序按上述搜索顺序,每一步中大正方形被覆盖的区域都是凹凸不平的(如右图),不方便剪枝,搜索效率也比较低。有没有更高效的搜索顺序呢? 既要不遗漏(正确性) 、不重复(高效性); 又要能够方便的剪枝。猜想:任何剖分方案是否都能通过若干条剖分线把一个个小正方形剖分出来呢? 类矩形凸出部分凹入部分剖分线——一条从左下角到右上角的只往右或往上走的曲线探寻新的搜索顺序定义: 证明大正方形就是一个类矩形,他的右边界和下边界连起来就是一条剖分线; 对于任意一个类矩形,从下到上的检查每一个凸出部分的右下角格子所在的小正方形,总有一个能够被分割出来。