《探寻深度优先搜索中的优化技巧综述》由会员分享，可在线阅读，更多相关《探寻深度优先搜索中的优化技巧综述（27页珍藏版）》请在金锄头文库上搜索。
1、探寻深度优先搜索中的优化技巧 从正方形剖分问题谈起 长沙市长郡中学金恺 正方形剖分问题 问题描述： 将n n 个小格组成的大正方形分割成若干个较小的整数 边长的正方形，要求分成的小正方形数目最小。 范围：1n32。 编程环境：FreePascal。可用64MB空间 n=7时的一个最小数目的剖分方案， 需要9个小正方形。 分析 当n为偶数时最少需要4个小正方形： 12 34 n/2 n/2 n/2n/2 当n为奇数时，很难发现有什么数学规律。 设fi,j表示一个ij的矩形最少可以被剖分成多少个小正方 形: n=7时，求出结果为10，并不是最优值。原因：最优 方案不一定能被某条直线分割。 i j
2、kj-k i j k i-k n711131719232931其他 fn,n1012121414161616 相同最优值911111313131415 相差111113210 fn,n仅是一个可行解，不过其值与最优解十分接近的。 目前只能用搜索！ 优化：搜索之前先用上述动态规划方程求出一个较优值 ，限制搜索层次。 搜索量巨大，仅用这一条优化，效率十分低下。 如何搜索？ 搜索的对象和顺序 从大量的搜索题(比如说IOI的Depot等)可以看出， 搜索的顺序和对象是十分重要的，本题应该用什么作为 搜索对象，搜索顺序又是怎样呢？ 搜索的对象：每个小正方形的位置和边长。 一种最简单的搜索顺序为：给大正方
3、形中第i行第j列 的小格编号(i-1)n+j，每次选择编号最小的未覆盖的小格 作为小正方形左上角的坐标，然后枚举它的边长。 速度太慢，需要大量剪枝! 剪枝 1、避重性剪枝：(对称性)规定左上角的那个小正方形的 边长小于等于其他三个角上的小正方形的边长，右上角的 小正方形边长大于等于左下角的小正方形边长。 2、平方和剪枝：11=12+12+32。 设Sumi表示至少要多少个整数才能使得这些整数的平方 和等于i,则 改进搜索的顺序 按上述搜索顺序，每一步 中大正方形被覆盖的区域 都是凹凸不平的(如右图) ，不方便剪枝，搜索效率 也比较低。 有没有更高效的搜索顺序呢？ 既要不遗漏(正确性) 、不重复
4、(高效性)； 又要能够方便的剪枝。 猜想：任何剖分方 案是否都能通过若 干条剖分线把一个 个小正方形剖分出 来呢？ 类矩形 凸出部分 凹入部分 剖分线 一条从左下角到 右上角的只往右 或往上走的曲线 探寻新的搜索顺序 定义： 证明 大正方形就是一个类矩形，他的右边界 和下边界连起来就是一条剖分线； 对于任意一个 类矩形，从下 到上的检查每 一个凸出部分 的右下角格子 所在的小正方 形，总有一个 能够被分割出 来。 新的搜索顺序 搜索时每次选择一个凹入部分的左上角作为小正方形的 左上角，小正方形的边长小于等于这个凹入部分的宽，就能 够保证在任何时候已覆盖区域为一个类矩形。 缺点：相同的剖 分方案
5、可能会被 搜索多次。 12 3 13 2 规定前一个小正方形不完全处于后一个的上部。 新增剪枝 1、一个类矩形若包含x个凸出部分，则它至少要x个小正 方形才能拼出，因为每个凸出部分右下角的小格都要属 于不同的小正方形中。 实践证明：大多数情况下这个下界比Sumi要精确得多。 2、对右图所示的两种 情况：它们沿“左上右 下”对角线是对称的，可 以只搜它们中的任一种 情况。 搜索效率：在最慢时(n=31)只要20s左右就能够出解 了。(测试环境 (R)4 CPU 1.7GHz) 还有什么方法能够使搜索效率再大幅提高呢？ 看下边这棵搜索树： 当搜到蓝色结点时，若已 经使用了x个小正方形, 而 这个节
6、点到目标结点的最小 深度为y (也就是说最少可 以用y个小正方形拼完此时 的未覆盖区域)，那么若往 下搜，最优值显然刚好为 x+y。 最小 深度 为Y 那么，若已知y的值，蓝色 节点就变为了搜索树中的叶 子节点，因为搜到它就可直 接回溯了。 若求出了大量的节点的y值 ，就能使许多非叶子节点变 为叶子节点，总节点数就会 大大减少。 这就为进一步增加搜索效率找到了契机。 但是，有两个新问题需要解决： 问题1、如何求某个节点到目标节点的最优值呢？ 问题2、应该求哪些节点到目标节点的最优值呢？ 状态的表示 首先，某个节点到目标节点的最优值只与当前未覆盖区 域的形状有关，所以只要以未覆盖区域作为当前状态
7、。 那么如何描述一个未覆盖区域呢？ 可用逆序n元组(a1,a2,an)，aiai+1 , na1表示，其中ai表 示第i+n-1行未被覆盖的小格子数目。 分析：一个状态需要占用n个字节，空间太多，而且比 较两个状态是否相等的时间复杂度为O(n)，速度也是非常 慢的。 有没有更好的方法呢？ 优化状态的表示 不妨令bi=ai-ai +1(0in，这里a0=n，an+1=0)，则有bi0 ，bi=n。由组合数学知识可知b的个数为：把n个无标号 的小球放入n+1个有标号的盒子中的方案数，等于C2nn，当 n=31时也不超过1e18，故可考虑用一个comp类型数对应 一个多元组b。 而b与a也是一一对应
8、的，所以可用一个comp类型整数 直接描述一个状态。 如何将a与一个整数互相对应呢？ 设Toti,j表示：满足jaiai+1an0的序列ak(ikn的 个数。 状态的对应的实现 将n元组a转化为整数s s 0; for i 1 to n do s s + Toti, ai - 1; 将整数s转化为n元祖a： a0 n; for i 1 to n do ai ai - 1; while s Toti, ai - 1 do ai ai - 1 s s - Toti, ai - 1; 动态规划 由于优化了状态的表示，它可用一个整数方便的描 述，而且问题很明显满足最优性和无后效性，所以很 快就会想到用
9、动态规划来求状态的最优值： 设fi表示整数i所对应的未覆盖区域至少需要多少个 小正方形拼成： 要求解的剖分线： i=1时对应的剖分线： 状态数太 大了！ 显然无法求出所有的状态的fi值，但是我们只需求出其 中的若干个就足够了。当然应该尽量多求一些，因为求出 的状态越多搜索的效率就会越高。 观察上面的动态规划方程，假如把将每个状态看作一个 点，若状态i添加一个小正方形能变成状态j就连一条有向 边ij，那么fi就是点1到点i的最短距离。由于每条边长度 都为1，可以从点1开始广搜，不断扩展直到产生出足够多 的状态。 实现方法 为了搜索时查找方便，每扩展出一个节点，就将它放入 Hash表中。 搜索时，
10、每搜到一个节点，就查找当前的状态i是否在 表中，如果找到了相应的fi值就可改进当前最优值然后直 接回溯。 查找的复杂度仅为常数（9） 算法缺陷：每搜索一个节点时都要进行一次查找，在多 数情况下其实是找不到的，白白浪费了大量的时间。 实现方法 优化：只计算fi小于c(自定的常数)的状态。搜索时，若 已经使用了x个小正方形，且x+c+1当前最优解，那么就查 找未覆盖区域对应的fi值： 1、若未找到，说明少于c+1个小正方形不能拼成未覆盖 区域，也就是说搜下去的话最少也要x+c+1个，不比当前最 优值更优； 2、如果找到了，那么搜下去的最优值显然为x+fi，就可 直接令当前最优值=min当前最优值，
11、x+fi； 这样一来，避免了无谓的查找，效率大大提高。 实现方法 经过以上的优化过程，搜索的层次能够减少了c层， 效率得到了大大的提高。 如果结合各种各样剪枝条件，最大数据(n =31)也仅要 4秒多。 搜索效率 n运行时间n运行时间 =170.00s250.22s 190.11s270.38s 210.11s292.86s 230.44s314.12s 至此，已圆满解决了本题。 回顾解决本题的步骤 1、简单的动态规划Fi,j，求较优解； 2、根据本题“剖分的对称性”等特点设计了一些简单的剪 枝； 3、通过合理的划分剖分方案，得到新的搜索顺序，找 到了新的剪枝方法； 4、通过将每个状态对应于一
12、个整数，方便的借助高效 的动态规划算法来求某些状态值，从而降低了搜索的层数 。 经过以上这4步，搜索的效率逐步提高！特别是第3步和 第4步效率提高得十分明显。 搜索，因其时间效率的 “先天不足”，人们有针对性的研 究出了很多优化技巧。 一、搜索的对象和顺序是优化中非常重要的一个环节， 好的顺序往往是高效率的前提。但是，它也仅仅是一个前 提，要保障高效率仅仅靠它是不够的； 二、“剪枝”是最常见的优化方法，几乎可以说，只要用 搜索解决问题，就必须考虑剪枝优化。但是，无论剪枝多 么巧妙，都不能从本质上降低搜索算法的时间复杂度。 总结 三、预求某些状态的最优值，降低搜索的层数。它能够 起到降低搜索复杂度的功效。 由于FreePascal的开发使用，使得空间上的限制放松了 上百倍，而题目对运行时间的限制历来都是十分苛刻的， 这使得我们想到用牺牲空间的代价来换取更多的时间。若 把它利用到搜索中来，就产生以上这种优化方法。 这一优化中最重要的一步就是状态的表示。 算法的优化是永无止境的，搜索的优化更是如此，需要 我们具体问题具体分析，充分发挥思维的灵活性。只有积 累了足够的经验，才能够熟练的应用各种优化技巧。 总结 n132329 Fn,n121415 最优值111314
