NOI导刊 搜索顺序的选取与剪枝策略.ppt

1、A,1,搜索的剪枝 策略与 搜索对象、搜索顺序的选择,长沙市雅礼中学 朱全民,A,2,条件1：V = n H = m 层 形状：每层都是一个圆柱体。 条件2： 设从下往上数第i(1Ri+1且HiHi+1。 条件3： 表面积Q最小，令Q= S 问题： 给出的n和m， 找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 (除Q外，以上所有数据皆为正整数) 输入 n (n Hi+1 （3） Vi+1 = Vi - Ri+1* Ri+1* Hi+1 （4） Si+1 = Si + 2 * Ri+1* Hi+1,A,5,确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件

2、 1）是否做到了m层 2）是否最终体积为0 3）是否当前面积最小 若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕,基本算法,A,6,Search (i, Ri , Hi , Si , Vi) 对每层蛋糕进行搜索 if (i=m) and (Vi =0) then 更新最优值 else for Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si

3、+ 1,Vi + 1) Problem-Cake 枚举所有的初始状态 - 第一层蛋糕的大小 for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ for H1n div (R1*R1) downto m do S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) ,A,7,优化？,（1）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积, 这样我们可以就加入如下剪枝条件: if 当前的表面积 + 余下的側面积 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层

4、, Si：为第i层蛋糕的侧面积, FSi：余下的侧面积,怎么求FSi ? 因为: 2Vi= 2Ri+1 * Ri+1 * Hi+1 + .+ 2Rm * Rm * Hm = Ri+1 * Si+! + .+ Rm * Sm Ri+1 * (Si+1+ .+ Sm) = Ri+1 * FSi 所以: FSi 2Vi / Ri+1 因此剪枝条件为： if Si-1 + 2 * Vi-1 / Ri 当前最优值 then exit,A,8,优化？,(2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设， 最m层半径和高都为1，Rm=Hm=1 第m-1层半径和高都为2，Rm-1=H

5、m-1=2 第 i +1层半径和高都为i, Ri = Hi = m i 这样， 余下的m-i层的最小体积为,因此,剪枝条件为, if Vi当前最优值 then exit; 剪枝1 if Vi MINi then exit; 剪枝2 if Vi MAXi then exit; 剪枝3 if im then for Ri + 1 Ri downto i for Hi + 1min(Vi div (Ri + 1*Ri + 1), Hi) downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search (

6、i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Else if Vi =0 then 更新最优值 Problem-Cake 1. 计算MINi和MAXi R,H ; 2. for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ 3. for H1n div (R1*R1) downto m do 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. ,A,12,小节,可行性剪枝,剪枝2：if Vi当前最优值 then exit,剪枝

7、原则,正确、高效,A,13,埃及分数,在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/1

8、8比1/180,1/45,1/30,1/180都大。 给出a,b(0ab1000),编程计算最好的表达方式。 输入：a b 输出：若干个数，自小到大排列，依次是单位分数的分母。 例如： 输入：19 45 输出：5 6 18,A,14,分析,1.节点类型 是一个K元组（a1,a2,.ak）, 代表当前解中的分母a1,a2.ak. 2.节点扩展方法 按照a1a2a3.dk-1) then a整除b的情况 3. dk:=b; 4. if not found or (dkTime3 Timen（Timei表示第i台处理机的处理时间）,从而可以设定槛值：如当前处理机的处理时间=目前最佳解，或剩下的处理机

9、台数上一台处理机的处理时间剩余的作业需要的处理时间，则回溯。因为在前面的约束条件下，已经不可能有解。 因此，从上面的比较来看，第二种方法显然是比第一种要好的。下面就针对第二种方法更深一层的进行探讨。 对于任务一，首先可以用贪心求出Time1的上界。然后，还可以Time1的下界，UP（作业总时间/处理机台数）。（UP表示大于等于该小数的最小整数）。搜索便从上界开始，找到一个解后，若等于下界即可停止搜索。 对于任务二，可采用深度+可变下界。下界为：UP（作业总时间/限定时间），即至少需要的处理机台数。并设定Time1的上界为T。,A,27,【间隔排列】问题,有2N个木块，每个木块标上1到N的自然数

10、中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比如说N=3的情况，下面就是一个可行的排列： 3，1，2，1，3，2。 编程实现，对给定的N(n=40)，求出一个可行排列。,A,28,运行效果比较,A,29,选择搜索顺序的基本原则,1、取值范围小的搜索元素先搜索。 2、一个搜索元素确定以后对其它搜索元素取值范围的影响称为制约力。制约力较大的搜索元素先搜索。 3、先搜索对解影响较大的元素可以使剪枝时的估价函数更准确，使剪枝更加有效。,A,30,【算符破译】（NOI2000）,题意简述：古梅算符由小写字母a到m组成，分别对应于现代算符中的

11、0,1,2,3,4,5,6,7,8,9,+,*,=中的一个。给出一组古梅算符表示的等式，若存在满足等式的对应关系，则输出所有能够确定的古梅算符和现代算符的对应关系；否则输出noway。 INPUT OUPUT 2 a6 abcdec b* cdefe d= f+ 在上例中，可能对应的现代表达式为6*2=12，2=1+1，6*4=24，4=2+2，6*8=48，8=4+4。可见，能够确定的对应关系只有a对应6，b对应*，d对应=，f对应+，应该输出；,A,31,三个最特殊的元素,本题中有三个算符最特殊：= 、* 、+，它们要满足以下条件： 1、这三个算符不能出现在等式的最左端和最右端。 2、这三

12、个算符两两不能相邻。 3、，这是最特殊的算符，它在任何一个等式中必须出现且仅出现一次。,A,32,确定搜索顺序,从取值范围方面考虑，*的取值范围在所有算符中是最小的；从制约力方面考虑，和，*的制约力无疑都强于0到9这十个数字；从对剪枝有利的角度考虑，这三个算符对解的影响最大，因此，*这三个算符应当放在搜索序列的前面。对于这三个算符，由于受到的限制更多，取值范围更小，所以应当优先搜索。 由此得出的最优搜索顺序：先搜索，其次是，*，最后是10个数字。,A,33,静态优化搜索顺序,在一些问题中，搜索元素的制约力和取值范围在搜索过程中变化不大，或变化对搜索效率影响不大。如果要动态判断元素的取值范围和制

13、约力需要花费较大的代价，而且优化效果不好。在这种情况下只需在搜索开始前确定搜索顺序，而不必在搜索过程中再改变搜索顺序。,A,34,动态调整搜索顺序,有时在搜索过程中元素的取值范围和制约力会有较大的变化，而且这些变化直接影响到搜索树的规模,因此需要动态的调整搜索顺序，也就是启发式搜索。启发式搜索继承了回溯法占用空间少，编程简单的优点，而启发式搜索的最大优点是可以在较短的时间内找到一组可行解，这最适合解决一类只需要求出一组可行解的搜索问题。,A,35,【质数方阵】（IOI94）,题意简述：在一个5*5的方阵中填入数字，使得沿行，沿列及两个对角线的5个数字都能构成一个5位质数（5位质数的首位不为0）

14、。所有质数的各位数字之和必须等于一个常数。这个常数和方阵左上角中的数字预先给出。若存在多个解，必须全部得出。 input 11 1 output,A,36,搜索元素的性质,1、最后一行和最后一列：可以填的数字只有1，3，7，9。 2、两条对角线：与方阵中的所有五位素数有关。 3、其他行列：特殊性取决于行列中已经确定的格子个数。,A,37,根据元素取值范围和制约力确定搜索顺序,1、最后一行和最后一列是取值范围最小的搜索元素，而且它们对其他所有的元素都有一定的制约力，因此要放在搜索序列的最前面。 2、两条对角线同样影响到其他所有的搜索元素，制约力在剩下的格子中是最大的，因此也应当优先搜索。 3、剩

15、下的行列依据它们取值范围的大小确定搜索顺序。,A,38,【篮球锦标赛】（BOI98）,题意简述：有5支球队参加一次篮球锦标赛。比赛采用单循环，每两支球队比赛一次。已知每个队最终的获胜场次数，失败场次数，总得分以及总失分，并给出所有场次得分的列表，要求出可能的比赛的情况。（每一队每场比赛的得分组成的战绩表）。,A,39,动态调整搜索顺序的依据,搜索元素（即每场的比分）之间的制约力大小很难确定。 本题中，元素的取值范围定义为某一场中一个队的比分可以有几种可能的取值。由于比分的取值范围在搜索中会有较大的变化，而且这种变化直接影响到搜索树的规模，因此改变搜索顺序的主要依据就是每一个比分取值范围的大小。,A,40,动态判断元素取值范围的方法,首先，我们要进行一次预处理，求出所有n次得分的总和等于m的情况（可以用HASH表存储以提高检索效率）。在搜索的每一步中，根据已经填过的比分，我们可以判断出剩余的比分中哪些是不能填在某个位置的。 此外，在已知i和j比赛的输赢情况和I在这场比赛中得到的分数，则这场比赛中j对i赢的比分也要受到限制。 由此，可以确定出每一个元素的取值范围。,A,