《NOI导刊搜索顺序的选取与剪枝策略.ppt》由会员分享，可在线阅读，更多相关《NOI导刊搜索顺序的选取与剪枝策略.ppt（43页珍藏版）》请在三一办公上搜索。
1、搜索的剪枝 策略与搜索对象、搜索顺序的选择,长沙市雅礼中学 朱全民,条件1：V=n H=m 层 形状：每层都是一个圆柱体。条件2：设从下往上数第i(1Ri+1且HiHi+1。条件3：表面积Q最小，令Q=S问题：给出的n和m，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。(除Q外，以上所有数据皆为正整数)输入 n(n=10000)，m(m=20)输出 S（若无解则S=0）。,圆柱公式 V=R2H S侧=2RH S底=R2,生日蛋糕（NOI99）,解析法？,转变思路，搜索？,数据库用(i,Ri,Hi,Vi,Si)表示第i层蛋糕的一个状态。其中Ri,Hi分别为第i层蛋糕的半径和高，Vi,Si
2、分别表示做完第i层蛋糕后剩下的蛋糕体积和当前蛋糕的表面积。可见，初始状态：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)目标状态：(m,Rm,Hm,0,Sm)于是，我们的目标是找到一条从初始状态到任意目标状态的路径，并且Sm最小.扩展的规则(i,Ri,Hi,Vi,Si)(i+1,Ri+1,Hi+1,Vi+1,Si+1)满足:（1）Ri Ri+1（2）Hi Hi+1（3）Vi+1=Vi-Ri+1*Ri+1*Hi+1（4）Si+1=Si+2*Ri+1*Hi+1,确定第一层蛋糕的大小根据上一层蛋糕的大小确定下一层蛋糕该怎么做看是否符合条件 1）是否做到了m层 2）是否最终体积为
3、0 3）是否当前面积最小若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕,基本算法,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+1,Vi+1)Problem-Cake枚举所有的初始状态-第一层蛋糕的大小 for R1m to sqrt(n)do/*假设 H1=1，只做一层蛋糕*/for
4、 H1n div(R1*R1)downto m do S1=2*R1*H1+R1*R1 V1=n-R1*R1*H1 Search(1,R1,H1,S1,V1),优化？,（1）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件:if 当前的表面积+余下的側面积 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层,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 2
5、Vi/Ri+1 因此剪枝条件为：if Si-1+2*Vi-1/Ri 当前最优值 then exit,优化？,(2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设，最m层半径和高都为1，Rm=Hm=1第m-1层半径和高都为2，Rm-1=Hm-1=2 第 i+1层半径和高都为i,Ri=Hi=m i 这样，余下的m-i层的最小体积为,因此,剪枝条件为,if Vi MINi then exit,(3)如果剩下的蛋糕材料太多，以最大的方式做完m层,仍有材料剩余,那么没有必要继续往下做了，设，第i+1层半径和高分别为，Ri+1=Ri 1，Hi+1=Hi 1第i+2层半径和高分别为，
6、Ri+2=Ri 2，Hi+2=Hi 2 第 层半径和高分别为，Ri+m=Ri m，Hi+m=Hi m 这样，余下的m-i层的最大体积为,优化？,因此,剪枝条件为,if Vi MAXi,R,H then exit,计算MINi for i1 to n do S S+i*i*i;MINm-i S 计算MAXi,R,H for R1 to sqrt(n)do for H1 to n div(R*R)do S 0;for im downto 1 do S S+(R-i)*(R-i)*(H-i);MAXi,R,H S,初始化,Search(i,Ri,Hi,Si,Vi)对每层蛋糕进行搜索 if Si+2*
7、Vi/Ri 当前最优值 then exit;剪枝1 if Vi MINi then exit;剪枝2 if Vi MAXi then exit;剪枝3 if im then for Ri+1 Ri downto ifor 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(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/*假
8、设 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.,小节,可行性剪枝,剪枝2：if Vi MINi then exit,剪枝3：if Vi MAXi,R,H then exit,最优化剪枝,剪枝1：if Si-1+2*Vi-1/Ri 当前最优值 then exit,剪枝原则,正确、高效,埃及分数,在古埃及，人们使用单位分数的和(形如1/a的,a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为
9、加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：19/45=1/3+1/12+1/18019/45=1/3+1/15+1/4519/45=1/3+1/18+1/30,19/45=1/4+1/6+1/18019/45=1/5+1/6+1/18.最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。给出a,b(0ab1000),编程计算最好的表达方式。输入：a b输出：若干个数，自小到大排列，依次是单位分数的分母。例如：输入：19 45输出：5 6 18,分析,1.节点类型 是
10、一个K元组（a1,a2,.ak）,代表当前解中的分母a1,a2.ak.2.节点扩展方法 按照a1a2a3.ak的顺序扩展,扩展第k层节点的时候，最简单的办法就是从ak-1+1开始枚举ak,一直到预先确定的最大值。但是这个最大值怎么确定呢？直观的讲，ak总不能太大，因为如果ak太大，1/ak就很小，1/ak+1.1/ak+2.就更小，那么，尽管加了很多项，还可能不够a/b.例如：例如已经扩展到 19/45=1/5+?如果第二项是1/100,那么由于19/45-1/5=2/9=0.22222.那么接下来至少要0.2222/(1/100)=22项加起来才足够2/9,所以继续 扩展下去至少还要扩展22
11、项,加起来才差不多够a/b。,可变深度的搜索算法,PROCEDURE Search(k,a,b);决定第k个分母dk1.If k=depth+1 then exit depth需要进行枚举2.else if(a=1)and(bdk-1)then a整除b的情况3.dk:=b;4.if not found or(dkanswerk)then 更新解;5.6.else 7.s:=max b div a,dk-1+1;确定dk的上下界s,t;t:=(depth-k+1)*b div a 8.for i:=s to t do 9.dk:=i;10.m:=gcd(a,b);a,b的最大公约数为m11.s
12、earch(k+1,(i*a-b)div m,(b*i)div m);12.13.,汽车到站情况示例图：,同一条线路上的公共汽车以相同的时间间隔到站 时间单位用“分”表示，从0 到59。每条公共汽车线路至少有两辆车到达本站。公共汽车线路数K一定17，汽车数目N一定小于300。来自不同线路的公共汽车可能在同一时刻到达本站。不同公共汽车线路的车首次到站时间和到站的时间间隔都有可能相同。,目标：编一个调度表，公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。,问题要素,时间,车辆,路线,题目要求的是车和线路的关系，时间在其中起的是描述作用和条件制约作用，搜索对象应该是车或线路
13、这两个关键要素。,以车辆为搜索对象,搜索策略是：按到达的时间顺序，看车辆是属于哪条线路。1）某车属于新线路的第一辆车 2）属于已有线路的第二辆车,此时确定了一条路线,以车辆为搜索对象扩展的搜索树,以线路为搜索对象,搜索策略是：枚举每条线路包含哪些车，确定该线路,搜索每层都要确定一条路线。1）将未确定归属路线的到达时间最小的车固定为 新路线的第一辆车。2）其后枚举这条路线的第二辆车，从而确定该路线。,以线路为搜索对象扩展的搜索树,策略比较,1）谁易于优化剪枝 可行性剪枝（方法1好）与已知最优解比较剪枝（方法1好）排除重复剪枝（差不多）,2）谁的操作量小 主递归程序的枚举循环（1760）剪枝函数消
14、耗时间（差不多）,两种搜索方法的实际比较,多处理机调度问题,设定有若干台相同的处理机P1,P2Pn,和m个独立的作业J1,J2jm,处理机以互不相关的方式处理作业，现约定任何作业可以在任何一台处理机上运行，但未完工之前不允许中断作业，作业也不能拆分成更小的作业，已知作业Ji需要处理机处理的时间为Ti（i=1,2m）。编程完成以下两个任务：任务一：假设有n台处理机和m个作业及其每一个作业所需处理的时间Ti存放在文件中，求解一个最佳调度方案，使得完成这m个作业的总工时最少并输出最少工时。任务二：假设给定作业时间表和限定完工时间于文件中，求解在限定时间内完成这批作业所需要最少处理机台数和调度方案。,
15、搜索对象选取,方法一：按顺序搜索每个作业。当搜索一个作业时，将其放在每台处理机搜索一次。方法二：按顺序搜索每台处理机。当搜索一台处理机时，将每个作业放在上面搜索一次。,优劣性分析,对于方法一：只能根据目前已确定的需时最长的处理机的耗时与目前最佳解比较。对于方法二：可约定Time1Time2Time3 Timen（Timei表示第i台处理机的处理时间）,从而可以设定槛值：如当前处理机的处理时间=目前最佳解，或剩下的处理机台数上一台处理机的处理时间剩余的作业需要的处理时间，则回溯。因为在前面的约束条件下，已经不可能有解。因此，从上面的比较来看，第二种方法显然是比第一种要好的。下面就针对第二种方法更
16、深一层的进行探讨。对于任务一，首先可以用贪心求出Time1的上界。然后，还可以Time1的下界，UP（作业总时间/处理机台数）。（UP表示大于等于该小数的最小整数）。搜索便从上界开始，找到一个解后，若等于下界即可停止搜索。对于任务二，可采用深度+可变下界。下界为：UP（作业总时间/限定时间），即至少需要的处理机台数。并设定Time1的上界为T。,【间隔排列】问题,有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比如说N=3的情况，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的
17、N(n=40)，求出一个可行排列。,运行效果比较,选择搜索顺序的基本原则,1、取值范围小的搜索元素先搜索。2、一个搜索元素确定以后对其它搜索元素取值范围的影响称为制约力。制约力较大的搜索元素先搜索。3、先搜索对解影响较大的元素可以使剪枝时的估价函数更准确，使剪枝更加有效。,【算符破译】（NOI2000）,题意简述：古梅算符由小写字母a到m组成，分别对应于现代算符中的0,1,2,3,4,5,6,7,8,9,+,*,=中的一个。给出一组古梅算符表示的等式，若存在满足等式的对应关系，则输出所有能够确定的古梅算符和现代算符的对应关系；否则输出noway。INPUT OUPUT2 a6abcdec b*
18、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对应+，应该输出；,三个最特殊的元素,本题中有三个算符最特殊：=、*、+，它们要满足以下条件：1、这三个算符不能出现在等式的最左端和最右端。2、这三个算符两两不能相邻。3、，这是最特殊的算符，它在任何一个等式中必须出现且仅出现一次。,确定搜索顺序,从取值范围方面考虑，*的取值范围在所有算符中是最小的；从制约力方面考虑，和，*的制约力无疑都强于0到9这十个数字；从对剪枝有利的角度考虑，这三个算符对解的影响最大
19、，因此，*这三个算符应当放在搜索序列的前面。对于这三个算符，由于受到的限制更多，取值范围更小，所以应当优先搜索。由此得出的最优搜索顺序：先搜索，其次是，*，最后是10个数字。,静态优化搜索顺序,在一些问题中，搜索元素的制约力和取值范围在搜索过程中变化不大，或变化对搜索效率影响不大。如果要动态判断元素的取值范围和制约力需要花费较大的代价，而且优化效果不好。在这种情况下只需在搜索开始前确定搜索顺序，而不必在搜索过程中再改变搜索顺序。,动态调整搜索顺序,有时在搜索过程中元素的取值范围和制约力会有较大的变化，而且这些变化直接影响到搜索树的规模,因此需要动态的调整搜索顺序，也就是启发式搜索。启发式搜索继
20、承了回溯法占用空间少，编程简单的优点，而启发式搜索的最大优点是可以在较短的时间内找到一组可行解，这最适合解决一类只需要求出一组可行解的搜索问题。,【质数方阵】（IOI94）,题意简述：在一个5*5的方阵中填入数字，使得沿行，沿列及两个对角线的5个数字都能构成一个5位质数（5位质数的首位不为0）。所有质数的各位数字之和必须等于一个常数。这个常数和方阵左上角中的数字预先给出。若存在多个解，必须全部得出。input111output,搜索元素的性质,1、最后一行和最后一列：可以填的数字只有1，3，7，9。2、两条对角线：与方阵中的所有五位素数有关。3、其他行列：特殊性取决于行列中已经确定的格子个数。
21、,根据元素取值范围和制约力确定搜索顺序,1、最后一行和最后一列是取值范围最小的搜索元素，而且它们对其他所有的元素都有一定的制约力，因此要放在搜索序列的最前面。2、两条对角线同样影响到其他所有的搜索元素，制约力在剩下的格子中是最大的，因此也应当优先搜索。3、剩下的行列依据它们取值范围的大小确定搜索顺序。,【篮球锦标赛】（BOI98）,题意简述：有5支球队参加一次篮球锦标赛。比赛采用单循环，每两支球队比赛一次。已知每个队最终的获胜场次数，失败场次数，总得分以及总失分，并给出所有场次得分的列表，要求出可能的比赛的情况。（每一队每场比赛的得分组成的战绩表）。,动态调整搜索顺序的依据,搜索元素（即每场的
22、比分）之间的制约力大小很难确定。本题中，元素的取值范围定义为某一场中一个队的比分可以有几种可能的取值。由于比分的取值范围在搜索中会有较大的变化，而且这种变化直接影响到搜索树的规模，因此改变搜索顺序的主要依据就是每一个比分取值范围的大小。,动态判断元素取值范围的方法,首先，我们要进行一次预处理，求出所有n次得分的总和等于m的情况（可以用HASH表存储以提高检索效率）。在搜索的每一步中，根据已经填过的比分，我们可以判断出剩余的比分中哪些是不能填在某个位置的。此外，在已知i和j比赛的输赢情况和I在这场比赛中得到的分数，则这场比赛中j对i赢的比分也要受到限制。由此，可以确定出每一个元素的取值范围。,运行情况比较,智慧珠游戏(NOI2005),智慧珠游戏拼盘由一个三角形盘件（如右下图所示）和12个形态各异的零件（如左下图所示组成。,12种零件,智慧珠游戏(NOI2005),对于由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且尺寸合适，所有的零件都允许旋转(0、90、180、270)和翻转(水平、竖直)。现给出一个盘件的初始布局（有一些零件已经摆放在盘件中了），求一种可行的智慧珠摆放方案，使所有的零件都能放进盘件中。数据保证最多只有一组解。,
