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

《NOI导刊搜索顺序的选取与剪枝策略分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索的剪枝策略与搜索对象、搜索顺序的选择长沙市雅礼中学朱全民条件1：V=nπH=m层形状：每层都是一个圆柱体。条件2：设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri,高度为Hi的圆柱。当iRi+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）解析法

2、？转变思路，搜索？数据库用(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+

3、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更新最优值elseforRi+1Ri-1downtoiforHi+1Hi-1downtoi[Si+1Si+2

4、*Ri+1*Hi+1Vi+1Vi-Ri+1*Ri+1*Hi+1Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]Problem-Cake{枚举所有的初始状态-----第一层蛋糕的大小}forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/forH1ndiv(R1*R1)downtomdo[S1=2*R1*H1+R1*R1V1=n-R1*R1*H1Search(1,R1,H1,S1,V1)]优化？？（1）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件

5、: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层,那么没有必要继续往下

6、做了，设，最m层半径和高都为1，Rm=Hm=1第m-1层半径和高都为2，Rm-1=Hm-1=2…………第i+1层半径和高都为i,Ri=Hi=m–i这样，余下的m-i层的最小体积为因此,剪枝条件为,ifVi

7、这样，余下的m-i层的最大体积为优化？？因此,剪枝条件为,ifVi＞MAXi,R,Hthenexit计算MINifori1tondo[SS+i*i*i;MINm-iS]计算MAXi,R,HforR1tosqrt(n)doforH1tondiv(R*R)do[S0;forimdownto1do[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

8、INithenexit;{剪枝2}ifVi＞MAXithenexit;{剪枝3}ifi