深度优先搜索优化——向期中.ppt

《深度优先搜索优化——向期中.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、深度优先搜索的优化长郡中学向期中深度优先搜索在解决问题的时候，通过一定的顺序，依次枚举出问题可能存在的方案，并得出其中最优的方案的方法，被我们称之为搜索。在由已有的状态拓展出新的状态时，后拓展出的节点优先拓展的搜索顺序，被称为深度优先搜索。相必各位对深度优先搜索都并不陌生，所以我们今天讨论的重点在于对深度优先搜索的优化。优化的方向搜索问题一般求的是所有可行方案中最优的一种方案，所以我们有两个下手方向：1）可行：有很多方案到最后我们才发现是不行的，但是这些方案在一开始就已经决定的是不行的，所以尽早的判断出一个方案是否可行，对于问题的优化是很明

2、显的。2）最优：在一些情况下，无论之后如何决策，得出的方案都一定不比当前所得到的最优方案要优，那么这些方案都没有了访问的必要，可以进行剪枝。而在大多数情况下，这两种剪枝，都是同时进行的。小Z的生日就要到了，他的朋友小A想要帮他制作一个生日蛋糕，根据小Z的喜好，小A对蛋糕制作师提出了如下要求：蛋糕由m个圆柱形组成，设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri,高度为Hi的圆柱。要求当iRi+1且Hi>Hi+1。找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。(除Q外，以上所有数据皆为正整数)圆柱公式V=πR2H

3、S侧=2πRHS底=πR2生日蛋糕解析法？转变思路，搜索？数据库用(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（

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

5、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）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件:if当前的表面积+余下的側面积

6、>当前最优值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层

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

8、,Hthenexit计算MINifori1tondo[SS+i*i*i;MINm-iS]计算MAXi,R,HforR1tosqrt(n)doforH1tondiv(R*