深索优化〔生日蛋糕〕.ppt

生日蛋糕 7月17日是Mr．W的生日，ACM-THU为此要制作一个体积为n的m层生日每层都是一个圆柱体。设从下往上数第i(1≤i≤m)层蛋糕是半径为Ri， 高度为hi的圆柱。当im时，要求RiRi+1且hihi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小(令Q= Sπ)。 请编程对给出的n和m，找出蛋糕的制作方案（适当的ri和hi的值），使S最小。（除Q外，以上所有数据皆为正整数） 数据库 用( 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）是否最终体积为0 3）是否当前面积最小 若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕 Problem-Cake {枚举所有的初始状态 ----- 第一层蛋糕的大小} for R1?m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ for H1?n div (R1*R1) downto m do begin S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) end; Search (i, Ri , Hi , Si , Vi) {对每层蛋糕进行搜索} if (i=m) and (Vi =0) then begin 计算面积s; if smin then min:=s; end else for Ri + 1?Ri -1 downto m-i+1 for Hi + 1?Hi -1 downto m-i+1 begin 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) end; 最优化剪枝 如果目前搜索的面积smin,则无论如何都找不到一个优于min的解. 因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件: if 当前的表面积 + 余下的側面积 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层, Si’：为第i层蛋糕的侧面积, FSi：余下的侧面积,怎么求FSi ? 因为: 2Vi= 2Ri+1 * Ri+1 * Hi+1 + ...+ 2Rm * Rm * Hm = Ri+1 * Si+1’ + ...+ Rm * Sm’ ≤ Ri+1 * (Si+1’+ ...+ Sm’) = Ri+1 * FSi 所以: FSi ≥ 2Vi / Ri+1 因此剪枝条件为： if Si-1 + 2 * Vi-1 / Ri 当前最优值 then exit 可行性剪枝 可行性剪枝 如果剩下的蛋糕材料太多，以最大的方式做完m层, 仍有材料剩余,那么没有必要继续往下做了，设， 第i+1层半径和高分别为，Ri+1 = Ri – 1 ， Hi+1 = Hi –1 第i+2层半径和高分别为，Ri+2 = Ri –