搜索的优化
搜索的优化
主讲人:朱全民
条件1:V = nπ
H = m 层
形状:每层都是一个圆柱体。
条件2:
设从下往上数第i(1Ri+1且Hi>Hi+1。
条件3:
表面积Q最小,令Q= Sπ
问题:
给出的n和m,
找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。
(除Q外,以上所有数据皆为正整数)
输入
n (n
≤
Π=
m
i
ii
m
i
ii
ji
ji
m
i
iii
HRRRQ
HRRRS
mjiandHH
mjiandRR
HRRV
解析法?
转变思...
搜索的优化
主讲人:朱全民
条件1:V = nπ
H = m 层
形状:每层都是一个圆柱体。
条件2:
设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri,高度为Hi的圆柱。
当i
Ri+1且Hi>Hi+1。
条件3:
面积Q最小,令Q= Sπ
问题:
给出的n和m,
找出蛋糕的制作(适当的Ri和Hi的值),使S最小。
(除Q外,以上所有数据皆为正整数)
输入
n (n<=10000),
m (m<=20)
输出
S(若无解则S=0)。
生日蛋糕(Cake)(nOI99-3)
圆柱公式
V=πR2H
S侧=2πRH
S底=πR2
( )
( )
( )
321}*2*min{
)*2*(
13
12
)**1
1
11min
1
11
1
,,满足
其中,
∑
∑
∑
=
=
=
+=
+Π=
≤<≤>
≤<≤>
Π=
m
i
ii
m
i
ii
ji
ji
m
i
iii
HRRRQ
HRRRS
mjiandHH
mjiandRR
HRRV
解析法?
转变思路,搜索?
• 数据库
用( 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)是否当前面积最小
• 若上述条件成立,则保留当前最优值,否则继续
做下一层蛋糕,若重做蛋糕
基本算法
• 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)
]
优化??
(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’)
= Ri+1 * FSi
所以:
FSi ≥ 2Vi / Ri+1
因此剪枝条件为:
if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit
优化??
(2)如果剩下的蛋糕材料太少,不能保证做到m层,那么没有
必要继续往下做了,设,
最m层半径和高都为1,Rm=Hm=1
第m-1层半径和高都为2,Rm-1=Hm-1=2
…………
第 i +1层半径和高都为i, Ri = Hi = m – i
这样, 余下的m-i层的最小体积为
∑−
=
=
im
k
i kMIN
1
3
因此,剪枝条件为,
if Vi< MINi then exit
(3)如果剩下的蛋糕材料太多,以最大的方式做完m层, 仍有材
料剩余,那么没有必要继续往下做了,设,
第i+1层半径和高分别为,Ri+1 = Ri – 1, Hi+1 = Hi –1
第i+2层半径和高分别为,Ri+2 = Ri – 2, Hi+2 = Hi –2
…………
第 m层半径和高分别为,Ri+m = Ri –m,Hi+m= Hi –m
这样, 余下的m-i层的最大体积为
)(*)( 2,, jHjRMAX
M
ij
jjHRi −−=∑
=
优化??
因此,剪枝条件为,
if Vi > MAXi,R,H then exit
• 计算MINi
for iÅ1 to n do [
SÅ S + i * i * i;
MINm-iÅ S
]
• 计算MAXi,R,H
for RÅ1 to sqrt(n) do
for HÅ1 to n div (R*R) do [
SÅ 0;
for iÅm downto 1 do [
SÅ S +(R-i)*(R-i)*(H-i);
MAXi,R,HÅ S
]
]
初始化
• Search (i, Ri , Hi , Si , Vi)
{对每层蛋糕进行搜索}
if Si + 2 * Vi / Ri >当前最优值 then exit; {剪枝1}
if Vi < MINi then exit; {剪枝2}
if Vi > MAXi then exit; {剪枝3}
if i当前最优值 then exit
• 剪枝原则
正确、高效
深度搜索消耗时间 ≈ 每个节点操作系数 × 节点个数
优化
1)减少节点个数——这就是剪枝优化;
2)减少每个节点的操作系数——即程序操作量。
彩票问题
已知:
彩票上的数字:1,2,…,M
彩民的选择:A1,A2,…,An,其中Ai属于1,2,…,M
每人只能买一张彩票,每人彩票选择都不同
抽出两个自然数X和Y。
如果1/A1+2/A2+…+1/An= X/Y,则中奖(获取纪念品)。
输入:
N,M,X,Y
输出:
所需准备的纪念品数量
1≤X, Y≤100,1≤N≤10,1≤M≤50。
输入数据保证输出结果不超过105。
分析:对于每个数,有选和不选两种可能性,显然可
以建立如下模型:
x1/1 + x2/2 + x3/3 + … + xm/m = X/Y
其中,xi=0或者1(1<=i<=m)
x1+x2+x3+…+xm=n
•逐个搜索xi
•O(2m)
x1/1 + x2/2 + x3/3 + … + xm/m = X/Y
同时乘以m!*Y通分。
令Ti=m!*Y/i (1<=i<=m), T0=m!*X
则:
T1x1+T2x2+T3x3+…+Tmxm=T0
这就变成了一个01背包问题。
每个包裹的体积是Ti,箱子体积T0
从M个中选N个,填满箱子。
求方案数。
如何优化??
T1x1+T2x2+T3x3+…+Tmxm=T0
如何剪枝?
f[i, T]表示为了满足T1x1+T2x2+…+Tmxm=T,最少要让多少个
xi取1。
f[i, T]=min{f[i-1,T], f[i-1,T-Ti]+1}
按照xm, xm-1, xm-2, …, x1的顺序搜索。
假设xp~xm都已经取定,令S=Tpxp+Tp+1xp+1+…+Tmxm,
L=xp+xp+1+…+xm,如果f[p-1, T-S]+L>N,那么就可以回
溯,不必继续搜索了。
T~O(m!)。太大了!
f数组开不下,时间上也不允许。
动态规划的思想,空间矛盾太
大。
抓住矛盾:解决空间问题!
T太大了,可不可以想办法把它变小呢?
同余
T1x1+T2x2+T3x3+…+Tmxm=T0
f[i, T]表示为了满足T1x1+T2x2+…+Tmxm=T,至少要让
多少个xi取1。
f[i, T]=min{f[i-1,T], f[i-1,T-Ti]+1}
T1x1+T2x2+T3x3+…+Tmxm=T0
f[i, T]表示为了满足(T1x1+T2x2+…+TmXm)mod P=T,至
少要让多少个xi取1。
f[i, T]=min{f[i-1,T], f[i-1,(T-Ti)mod P]+1}
0<=TN,那么就可
以回溯,不必继续搜索了。
剪枝效果有所削弱
但是空间复杂度降到了O(mP),这里P可以任取。
•取P为大质数。(比如<10000的最大质数)
•剪枝效果相当的好。题目给定范围内的数据都在1s内解。
•注意要使用高精度。
1、空间换时间。
2、抓住主要矛盾,用同余法解决空间矛盾。
Amazing Robots: IOI2003
已知条件:
迷宫
i(i=1,2)
(每个不会大于20*20)
守卫
Gi(0<=Gi<=10)
(守卫循环移动进行执勤)
(守卫巡逻的方格数(2..4))
求:
两个机器人都离开迷宫所用的最少指令数目
和离开制指令序列(10000 步以内)。
•每一步可以发出的命令可以是N, E, S, W中的一种,
有4种选择。
•对每一步具体发出哪个命令,直接搜索。
•假设最后结果是T。(也就是最少出宫时间)
•时间复杂度是O(4T)
这种方法时间复杂度太高,绝对不可行!!
•5*4和4*4的迷宫
•第一个机器人的位置是(2,2)
•第二个机器人的位置是(3,2)
•当前时间是0。
•状态((2,2),(3,2),0)
状态表示:
(第一个机器人位置,第二个机器认位置,时间)
E
((2,2),(3,2),0) ((2,3),(3,3),1)
•时间已知,则所有Guard的位置可知。
•Guard、Robot的位置均已知,所以状态可以转移
•设出宫时间是T。
•总共(n*n)*(n*n)*T种状态。
•用BFS实现算法,HASH表判重。
•总的复杂度是O(Tn4)。
T<=10000, n<=20。
时间复杂度太大,不可承受!
0时刻 1时刻 2时刻 3时刻
•0时刻和2时刻是一样的
•1时刻和3时刻是一样的。
•稍加分析:此Guard循环以2为周期循环。
•状态转移,需要的信息是:Robot位置,Guard位置。
•Position of Robot1, 2是的作用就是Robot位置。
•Time的作用就是为了计算Guard的位置
•状态:(position of Robot1, position of Robot2, Time)
•Time<=10000,这是状态数过多的罪魁祸首!
•题目说:Guard巡逻经过的格子数只可能是2, 3, 4。
•也就是说机器人巡逻周期只能是2, 4, 6。
•[2, 4, 6]=12,所以第0时刻、12时刻、24时刻……Guard的
状态完全相同。
•12可以看作Guard的周期。Time只要记录当前是第几个周
期。因为周期确定了,Guard的位置也完全确定了!
0<=Time<=11
•状态数(n*n)*(n*n)*12=12n4。
•用BFS算法,标志数组判重。
•时间复杂度O(12n4)。
n<=20
完全可以承受
智破连环阵(N0I2003)
已知:
M个武器(1 ≤ M≤ 100)
N棵炸弹(1 ≤ N≤ 100)
炸弹爆炸半径(1≤ k≤ 1000)
炸弹消灭半径范围以内的,处于攻击状态的武器
第i号武器被消灭后,第i+1号武器立即处于攻击状态
要求:用最少的炸弹消灭所有的武器
示例图
问题转化
• 设炸弹的攻击的半径为r
• 第i号炸弹的坐标为(u[i],v[i])
• 第j号武器的坐标为(x[j],y[j])
则炸弹i能炸到炸弹j的基本条件是
(u[i]-x[j])2+(v[i]-y[j])2<=r2
我们可以枚举哪些炸弹是否爆炸,使得消灭
所有得武器,时间复杂度为M*2n ,M,N可达到
100,显然此方法时间复杂度巨大。
按武器搜索怎么样?
1)我们必须将武器按它的编号划分成若干段
2)每一段的武器,哪些炸弹能对它们进行销毁,
如下图:
算法
• 将武器根据编号分为x段,[Si,Ti]
(S1=1,Ti>=Si,Ti+1=Si+1)。
• 然后判断是否可以从A国的N颗炸弹中选出
x颗,分别可以炸掉其中的一段。
如何分段:搜索算法
如何分段,理论复杂度为2m ,需要优化,
留给学生思考?
如何选取炸弹:二分图的匹配
子串
• 给定一个由自然数串联而成的无限数列
1234567891011121314……(母串)
• 求任意一个长度不超过200的数列(子串)
在其中最早出现的位置。
分析:
• 首先,由于母串可无限扩充,显然我们不
可能把它全部生成出来。
• 如果边生成母串,边判断所生成的数串是
否包含给定的子串,即使是使用字符串处
理中高效的KMP算法,耗费的工作量也是
巨大的。
1121314
• 先枚举第1位1
• 自然数1之后为2,3,……
• 母串中形如123……
• 与子串从第2位开始不符
• 枚举前2位11
• 自然数11之后为12,13……
• 母串中形如111213……
• 与子串从第3位开始不符
• 考虑第2位开始12
• 自然数12之前为11,
末位与子串第1位相
同,之后为
13,14,……
• 母串中形如
1314……
• 与子串匹配!
如何优化呢?
• 较好的方法是另辟蹊径:
• 刚才我们枚举的是母串的每一位,不妨换
一个角度,从子串着手。
• 先来观察一些片断:
12345678910111213141516……
很自然得到算法:
• 枚举子串所包含第一个完整的数a的位数La。
• 假设a在母串的第k位出现(k<=La)
• 判断接下来由a生成的序列是否与子串吻合。
• 如果吻合,则最优解的判断:
– (1) LaAns_k
• 4.跟据Ans_a及Ans_k计算出位数
• 总时间复杂度约为O(n^3),与之前的不
可估量相比有了本质性提高。
• 第4步可通过多种途径求得,这里不作介
绍。
• 由于其中牵涉到许多高精度的计算及字
符串处理,要求我们细致认真。
• 充分挖掘题目特性是解决本题的关键。
• 得以使枚举这类看似低效率的方法得到较
好的运用。
• 同时细致全面的考虑问题也是必不可少
的。
搜索试题推荐
1)八数码、14数码问题
2)埃及分数问题
3)多个列车轨道的列车调度
4)贴邮票问题
等等
搜索的优化
转变思路,搜索?
基本算法
优化??
优化??
优化??
初始化
小节
智破连环阵(N0I2003)
示例图
问题转化
按武器搜索怎么样?
算法
子串�
分析:
1121314
如何优化呢?
很自然得到算法:
小结
搜索试题推荐
本文档为【搜索的优化】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。