NOI导刊 深度优先搜索优化——向期中

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

深度优先搜索的优化长郡中学 向期中

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

深度优先搜索

在解决问题的时候，通过一定的顺序，依 次枚举出问题可能存在的方案，并得出其 中最优的方案的方法，被我们称之为搜索。 在由已有的状态拓展出新的状态时，后拓 展出的节点优先拓展的搜索顺序，被称为 深度优先搜索。 相必各位对深度优先搜索都并不陌生，所 以我们今天讨论的重点在于对深度优先搜 索的优化。

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

优化的方向

搜索问题一般求的是所有可行方案中最优的一种方 案，所以我们有两个下手方向： 1)可行：

有很多方案到最后我们才发现是不行的，但是这些方 案在一开始就已经决定的是不行的，所以尽早的判断 出一个方案是否可行，对于问题的优化是很明显的。 在一些情况下，无论之后如何决策，得出的方案都一 定不比当前所得到的最优方案要优，那么这些方案都 没有了访问的必要，可以进行剪枝。

2)最优：

而在大多数情况下，这两种剪枝，都是同时进行的。

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

生日蛋糕小Z的生日就要到了，他的朋友小A想要帮 他制作一个生日蛋糕，根据小Z的喜好，小A对 蛋糕制作师提出了如下要求： 蛋糕由m个圆柱形组成，设从下往上数第 i(1<=i<=m)层蛋糕是半径为Ri, 高度为Hi的圆柱 。 要求当i<m时，满足Ri>Ri+1且Hi>Hi+1。 找出蛋糕的制作方案(适当的Ri和Hi的值 ),使S最小。 (除Q外，以上所有数据皆为正整数)

圆柱公式 V=πR2H S侧=2πRH S底=πR2

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

解析法？ 1 2 3 V ( Ri * Ri * H i )i 1 m

Ri R j Hi H j

and andm

1 i j m 1 i j m

其中，S ( R1 * R1 2 Ri * H i )i 1

Qmin min{ R1 * R1 2 Ri * H i }i 1

m

满足1, 3 2,

2010年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

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

基本算法

确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件 1)是否做到了m层 2)是否最终体积为0 3)是否当前面积最小 若上述条件成立，则保留当前最优值，否则继续 做下一层蛋糕，若重做蛋糕

2010年NOI导刊暑期培训(北京) 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 p (R1*R1) downto m do [ S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) ]

2010年NOI导刊暑期培训(北京) 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’) = Ri+1 * FSi 所以: FSi ≥ 2Vi / Ri+1 因此剪枝条件为： if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

优化？?(2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没

有必要继续往下做了，设， 最m层半径和高都为1,Rm=Hm=1 第m-1层半径和高都为2,Rm-1=Hm-1=2 ………… 第 i +1层半径和高都为i, Ri = Hi = m – i 这样， 余下的m-i层的最小体积为

MIN i k 3k 1

m i

因此,剪枝条件为, if Vi< MINi then exit

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

优化？?(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层的最大体积为MAX i , R , H ( R j j ) 2 * ( H j j )j i M

因此,剪枝条件为, if Vi > MAXi,R,H then exit

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

初始化

计算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 p (R*R) do [ S 0; for i m downto 1 do [ S S +(R-i)*(R-i)*(H-i); MAXi,R,H S ] ]

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

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<m then for Ri + 1 Ri downto i for Hi + 1 min(Vi p (Ri + 1*Ri + 1), Hi) 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) ] Else if Vi =0 then 更新最优值

Problem-Cake 1. 计算MINi和MAXi R,H ; 2. for R1 m to sqrt ( n ) do /*假设 H1=1,只做一层蛋糕 */ 3. for H1 n p (R1*R1) downto m do [ 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. ]

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

小节 最优化剪枝剪枝1: if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit

可行性剪枝剪枝2:if Vi< MINi th

en exit 剪枝3:if Vi > MAXi,R,H then exit

剪枝原则正确、高效

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

深度搜索消耗时间 ≈ 每个节点操作系数 × 节点个数

优化 1)减少节点个数——这就是剪枝优化； 2)减少每个节点的操作系数——即程序操作量。

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

15数码问题

在4×4的棋盘上，摆有15个棋子，每个棋子上标有1至15的某 一数字。棋盘中留有一个空格(空格用0表示)。空格周围的棋子 可以移到空格中。要求解的问题是：给出一种初始布局(初始 状态)和目标面局(目标状态),找到一种最少步骤的移动方 法，实现从初始布局到目标布局的转变。1 5 2 6 3 7 4 8 0 4 1 5 2 6 3 7

9

10 11 12

8

9

10 11

13 14 15 0

12 13 14 15

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

引入

迭代加深算法：从小到大枚举ans,用深搜 判断ans是否可行。 因为ans越小越容易进行可行性剪枝。 因为ans枚举出来了，所以不存在最优性剪 枝。 其实也可以理解成枚举ans,更好地进行最 优性剪枝。 搜索顺序的优化就要根据题目讨论了。

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

估价函数

s——问题的某种状态。 h*(s)——s到目标的实际最短距离。 h(s)——s的估价函数，表示s到目标距离的 下界，h(s)<=h*(s),若h函数是相容的，则 还需要满足h(s1)<=h(s2)+c(s1,s2),其中 c(s1,s2)表示s1转移到s2的距离。 g(s)——到达s状态之前经过的距离。 f(s)——s的启发函数，f(s)=g(s)+h(s),f(s) 单调递增。

2010年NOI导刊暑期培训(北京) NOI导刊 深度优先搜索优化——向期中

估价函数

当估价函数确定以后，我们每到达一个状 态s,可以用f(s)进行最优性剪枝，ans表示 当前最优答案，若f(s)>=ans,则当前状态 舍去，进行最优性剪枝。

本文来源：https://www.bwwdw.com/article/x8iq.html