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

搜索的剪枝策略与

搜索对象、搜索顺序的选择长沙市雅礼中学朱全民条件1：V=nπH=m层形状：每层都是一个圆柱体。条件2：设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<m时，要求Ri>Ri+1且Hi>Hi+1。条件3：外表积Q最小，令Q=Sπ问题：给出的n和m，找出蛋糕的制作方案〔适当的Ri和Hi的值〕，使S最小。(除Q外，以上所有数据皆为正整数)输入n(n<=10000)，m(m<=20)输出S〔假设无解那么S=0〕。圆柱公式

V=πR2HS侧=2πRHS底=πR2生日蛋糕〔NOI99〕解析法？

转变思路，搜索？数据库 用(i,Ri,Hi,Vi,Si)表示第i层蛋糕的一个状态。其中Ri,Hi分别为第i层蛋糕的半径和高，Vi,Si分别表示做完第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〕是否最终体积为03〕是否当前面积最小假设上述条件成立，那么保存当前最优值，否那么继续做下一层蛋糕，假设重做蛋糕根本算法Search(i,Ri,Hi,Si,Vi){对每层蛋糕进行搜索}if(i=m)and(Vi=0)then更新最优值else forRi+1

Ri-1downtoi forHi+1

Hi-1downtoi[ Si+1

Si+2*Ri+1*Hi+1 Vi+1

Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]Problem-Cake {枚举所有的初始状态-----第一层蛋糕的大小}forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/ forH1ndiv(R1*R1)downtomdo[ S1=2*R1*H1+R1*R1 V1=n-R1*R1*H1 Search(1,R1,H1,S1,V1) ]优化？？〔1〕因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就参加如下剪枝条件:if当前的外表积+余下的側面积>当前最优值thenexit设已经做了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≥2Vi/Ri+1因此剪枝条件为：ifSi-1+2*Vi-1/Ri>当前最优值thenexit优化？？(2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设， 最m层半径和高都为1，Rm=Hm=1

第m-1层半径和高都为2，Rm-1=Hm-1=2…………

第i+1层半径和高都为i,Ri=Hi=m–i

这样，余下的m-i层的最小体积为

因此,剪枝条件为,ifVi<MINithenexit(3)如果剩下的蛋糕材料太多，以最大的方式做完m层,仍有材料剩余,那么没有必要继续往下做了，设， 第i+1层半径和高分别为，Ri+1=Ri–

1

，Hi+1=Hi–1

第i+2层半径和高分别为，Ri+2=Ri–2

，Hi+2=Hi–2

…………

第ｍ层半径和高分别为，Ri+m=Ri–m

，Hi+m=Hi–m

这样，余下的m-i层的最大体积为优化？？因此,剪枝条件为,ifVi＞MAXi,R,Hthenexit计算MINifori1tondo[S

S+i*i*i;

MINm-i

S

]计算MAXi,R,HforR

1tosqrt(n)doforH

1tondiv(R*R)do[

S

0;forimdownto1do[

S

S+(R-i)*(R-i)*(H-i);

MAXi,R,H

S ] ]初始化Search(i,Ri,Hi,Si,Vi){对每层蛋糕进行搜索}

ifSi+2*Vi/Ri>当前最优值thenexit;{剪枝1}ifVi<MINithenexit;{剪枝2}ifVi

＞MAXithenexit;{剪枝3}ifi<mthen forRi+1

Ridowntoi forHi+1min(Vidiv(Ri+1*Ri+1),Hi)downtoi[ Si+1

Si+2*Ri+1*Hi+1 Vi+1

Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]ElseifVi=0then更新最优值Problem-Cake1.计算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/3.forH1ndiv(R1*R1)downtomdo[4.S1=2*R1*H1+R1*R15. V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.]小节可行性剪枝剪枝2：ifVi<MINithenexit剪枝3：ifVi＞MAXi,R,Hthenexit最优化剪枝剪枝1：ifSi-1+2*Vi-1/Ri>当前最优值thenexit剪枝原那么正确、高效埃及分数在古埃及，人们使用单位分数的和(形如1/a的,a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数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(0<a<b<1000),编程计算最好的表达方式。输入：ab输出：假设干个数，自小到大排列，依次是单位分数的分母。例如：输入：1945输出：5618分析1.节点类型是一个K元组〔a1,a2,...ak〕,代表当前解中的分母a1,a2..ak.2.节点扩展方法按照a1<a2<a3..<ak的顺序扩展,扩展第k层节点的时候，最简单的方法就是从a[k-1]+1开始枚举a[k],一直到预先确定的最大值。但是这个最大值怎么确定呢？直观的讲，a[k]总不能太大，因为如果a[k]太大，1/a[k]就很小，1/a[k+1]..1/a[k+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项,加起来才差不多够a/b。可变深度的搜索算法PROCEDURESearch(k,a,b);{决定第k个分母d[k]}1.

Ifk=depth+1thenexit{depth需要进行枚举}2.

elseif(a=1)and(b>d[k-1])then[

｛a整除b的情况｝3.

d[k]:=b;4.

ifnotfoundor(d[k]<answer[k])then更新解;5.

]6.

else[7.

s:=max{bdiva,d[k-1]+1};{确定d[k]的上下界s,t;}t:=(depth-k+1)*bdiva

8.

fori:=stotdo[9.

d[k]:=i;10.m:=gcd(a,b);｛a,b的最大公约数为m｝11.

search(k+1,(i*a-b)divm,(b*i)divm);12.

]13.

]

0143142551321线路一线路二线路三0351314142125间隔为14间隔为11间隔为8汽车到站情况例如图：同一条线路上的公共汽车以相同的时间间隔到站时间单位用“分”表示，从0到59。每条公共汽车线路至少有两辆车到达本站。公共汽车线路数K一定≤17，汽车数目N一定小于300。来自不同线路的公共汽车可能在同一时刻到达本站。不同公共汽车线路的车首次到站时间和到站的时间间隔都有可能相同。目标：编一个调度表，公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。问题要素时间车辆路线题目要求的是车和线路的关系，时间在其中起的是描述作用和条件制约作用，搜索对象应该是车或线路这两个关键要素。以车辆为搜索对象搜索策略是：按到达的时间顺序，看车辆是属于哪条线路。1〕某车属于新线路的第一辆车2〕属于已有线路的第二辆车,此时确定了一条路线以车辆为搜索对象扩展的搜索树以线路为搜索对象搜索策略是：枚举每条线路包含哪些车，确定该线路,搜索每层都要确定一条路线。1〕将未确定归属路线的到达时间最小的车固定为新路线的第一辆车。2〕其后枚举这条路线的第二辆车，从而确定该路线。以线路为搜索对象扩展的搜索树策略比较

1〕谁易于优化剪枝

可行性剪枝〔方法1好〕

与最优解比较剪枝〔方法1好〕

排除重复剪枝〔差不多〕

2〕谁的操作量小

主递归程序的枚举循环〔17<60〕

剪枝函数消耗时间〔差不多〕两种搜索方法的实际比较多处理机调度问题设定有假设干台相同的处理机P1,P2Pn,和m个独立的作业J1,J2jm,处理机以互不相关的方式处理作业，现约定任何作业可以在任何一台处理机上运行，但未完工之前不允许中断作业，作业也不能拆分成更小的作业，作业Ji需要处理机处理的时间为Ti〔i=1,2m〕。编程完成以下两个任务：任务一：假设有n台处理机和m个作业及其每一个作业所需处理的时间Ti存放在文件中，求解一个最正确调度方案，使得完成这m个作业的总工时最少并输出最少工时。任务二：假设给定作业时间表和限定完工时间Ｔ于文件中，求解在限定时间Ｔ内完成这批作业所需要最少处理机台数和调度方案。搜索对象选取方法一：按顺序搜索每个作业。当搜索一个作业时，将其放在每台处理机搜索一次。方法二：按顺序搜索每台处理机。当搜索一台处理机时，将每个作业放在上面搜索一次。优劣性分析对于方法一：只能根据目前已确定的需时最长的处理机的耗时与目前最正确解比较。对于方法二：可约定Time[1]>Time[2]>Time[3]>>Time[n]〔Time[i]表示第i台处理机的处理时间〕,从而可以设定槛值：如当前处理机的处理时间>=目前最正确解，或剩下的处理机台数×上一台处理机的处理时间<剩余的作业需要的处理时间，那么回溯。因为在前面的约束条件下，已经不可能有解。因此，从上面的比较来看，第二种方法显然是比第一种要好的。下面就针对第二种方法更深一层的进行探讨。对于任务一，首先可以用贪心求出Time[1]的上界。然后，还可以Time[1]的下界，UP〔作业总时间/处理机台数〕。〔UP表示大于等于该小数的最小整数〕。搜索便从上界开始，找到一个解后，假设等于下界即可停止搜索。对于任务二，可采用深度+可变下界。下界为：UP〔作业总时间/限定时间〕，即至少需要的处理机台数。并设定Time[1]的上界为T。【间隔排列】问题 有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比方说N=3的情况，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N(n<=40)，求出一个可行排列。运行效果比较N从大到小搜索从小到大搜索110.00sec0.00sec150.00sec0.11sec200.00sec36.32sec320.00sec超时400.00sec超时选择搜索顺序的根本原那么1、取值范围小的搜索元素先搜索。2、一个搜索元素确定以后对其它搜索元素取值范围的影响称为制约力。制约力较大的搜索元素先搜索。

3、先搜索对解影响较大的元素可以使剪枝时的估价函数更准确，使剪枝更加有效。【算符破译】〔NOI2000〕

题意简述：古梅算符由小写字母a到m组成，分别对应于现代算符中的0,1,2,3,4,5,6,7,8,9,+,*,=中的一个。给出一组古梅算符表示的等式，假设存在满足等式的对应关系，那么输出所有能够确定的古梅算符和现代算符的对应关系；否那么输出‘noway’。INPUTOUPUT2a6abcdecb*cdefed=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’这十个数字；从对剪枝有利的角度考虑，这三个算符对解的影响最大，因此‘＝’，‘＋’，‘*’这三个算符应当放在搜索序列的前面。对于这三个算符，由于‘＝’受到的限制更多，取值范围更小，所以应当优先搜索。由此得出的最优搜索顺序：先搜索‘＝’，其次是‘＋’，‘*’，最后是10个数字。静态优化搜索顺序

在一些问题中，搜索元素的制约力和取值范围在搜索过程中变化不大，或变化对搜索效率影响不大。如果要动态判断元素的取值范围和制约力需要花费较大的代价，而且优化效果不好。在这种情况下只需在搜索开始前确定搜索顺序，而不必在搜索过程中再改变搜索顺序。动态调整搜索顺序

有时在搜索过程中元素的取值范围和制约力会有较大的变化，而且这些变化直接影响到搜索树的规模,因此需要动态的调整搜索顺序，也就是启发式搜索。启发式搜索继承了回溯法占用空间少，编程简单的优点，而启发式搜索的最大优点是可以在较短的时间内找到一组可行解，这最适合解决一类只需要求出一组可行解的搜索问题。【质数方阵】〔IOI94〕题意简述：在一个5*5的方阵中填入数字，使得沿行，沿列及两个对角线的5个数字都能构成一个5位质数〔5位质数的首位不为0〕。所有质数的各位数字之和必须等于一个常数。这个常数和方阵左上角中的数字预先给出。假设存在多个解，必须全部得出。input111output113511403330323532011331311351332033032314033333111331313043323035023113331搜索元素的性质1、最后一行和最后一列：可以填的数字只有{1，3，7，9}。2、两条对角线：与方阵中的所有五位素数有关。3、其他行列：特殊性取决于行列中已经确定的格子个数。根据元素取值范围和制约力确定搜索顺序

1、最后一行和最后一列是取值范围最小的搜索元素，而且它们对其他所有的元素都有一定的制约力，因此要放在搜索序列的最前面。2、两条对角线同样影响到其他所有的搜索元素，制约力在剩下的格子中是最大