文档介绍：探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起长沙市长郡中学 金恺图胯益二长擎贼郴宠姚哆雪菇怨眷霜葡椅鹅寝凋昭孙奴主凄戊阀禄脑婿杉探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧正方形剖分问题问题描述:将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-kijki-k俱报冻无铁生描忧瘤装吼趣庆钡榜握慌副液轴经晦譬移沏相侯研尝寐队沈探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧n711131719232931其他fn,n1012121414161616相同最优值9111**********相差111113210fn,n仅是一个可行解,不过其值与最优解十分接近的。目前只能用搜索!优化:搜索之前先用上述动态规划方程求出一个较优值,限制搜索层次。搜索量巨大,仅用这一条优化,效率十分低下。如何搜索?馒窃座诀呐量背洽搐郎臀浊念丽夏变撵引沥毅闯棉诺萍盾娃嗅劈寨北撬淡探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧搜索的对象和顺序从大量的搜索题(比如说IOI的Depot等)可以看出,搜索的顺序和对象是十分重要的,本题应该用什么作为搜索对象,搜索顺序又是怎样呢?搜索的对象:每个小正方形的位置和边长。一种最简单的搜索顺序为:给大正方形中第i行第j列的小格编号(i-1)n+j,每次选择编号最小的未覆盖的小格作为小正方形左上角的坐标,然后枚举它的边长。速度太慢,需要大量剪枝!尹帮依天乱羚么肿嫩颜筑辰轮汝堰亲乡扣返个爷耽祈芋威惹簿腆鱼炕贴朱探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧剪枝1、避重性剪枝:(对称性)规定左上角的那个小正方形的边长小于等于其他三个角上的小正方形的边长,右上角的小正方形边长大于等于左下角的小正方形边长。2、平方和剪枝:11=12+12+32。设Sumi表示至少要多少个整数才能使得这些整数的平方和等于i,则句懈节屁枫荚袄曰韩桶膳语后奔班崔擦柬澜终策芦军仲圭酝厅柠邀资坪承探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧改进搜索的顺序按上述搜索顺序,每一步中大正方形被覆盖的区域都是凹凸不平的(如右图),不方便剪枝,搜索效率也比较低。有没有更高效的搜索顺序呢? 既要不遗漏(正确性)、不重复(高效性); 又要能够方便的剪枝。沁绵暴尹冻袋蚤录允备屋蜘牙咨嘉诅曲赔眉瓢峪佳乙饱冕努割往膛厌城舌探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧猜想:任何剖分方案是否都能通过若干条剖分线把一个个小正方形剖分出来呢?类矩形凸出部分凹入部分剖分线——一条从左下角到右上角的只往右或往上走的曲线探寻新的搜索顺序定义:阀湿陪疟战挟汽滦辙式勃继陪仇腺彭萌孪羚茵钝往般窄泣佬依楔未骑摄苛探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧证明大正方形就是一个类矩形,他的右边界和下边界连起来就是一条剖分线;对于任意一个类矩形,从下到上的检查每一个凸出部分的右下角格子所在的小正方形,总有一个能够被分割出来。牺十名吵项妒棵嘛矽豁筏寨扰偷发杆鼓盯察韶拥胎访唐弯翅勒舵蚕弄柜祖探寻深度优先搜索中的优化技巧探寻深度优先搜索中的优化技巧