NOI导刊搜索顺序的选取和剪枝策略讲义.ppt

条件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=πR2H
S侧=2πRH
S底=πR2
生日蛋糕（NOI99）
*
NOI导刊搜索顺序的选取和剪枝策略
*
解析法？
*
NOI导刊搜索顺序的选取和剪枝策略
*
转变思路，搜索？
数据库
用( 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
*
NOI导刊搜索顺序的选取和剪枝策略
*
确定第一层蛋糕的大小
根据上一层蛋糕的大小确定下一层蛋糕该怎么做
看是否符合条件
1）是否做到了m层
2）是否最终体积为0
3）是否当前面积最小
若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕
基本算法
*
NOI导刊搜索顺序的选取和剪枝策略
*
Search (i, Ri , Hi , Si , Vi)
{对每层蛋糕进行搜索}
if (i=m) and (Vi =0) then 更新最优值
else
for Ri + 1Ri -1 downto i
for Hi + 1Hi -1 downto i [
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
{枚举所有的初始状态 ----- 第一层蛋糕的大小}
for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */
for H1n div (R1*R1) downto m do
[
S1=2 * R1* H1+ R1* R1
V1=n - R1* R1 * H1
Search (1, R1, H1, S1, V1)
]
*
NOI导刊搜索顺序的选取和剪枝策略
*
优化？？
（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’)