《深度优先搜索优化——向期中概要》由会员分享，可在线阅读，更多相关《深度优先搜索优化——向期中概要（66页珍藏版）》请在金锄头文库上搜索。
1、深度优先搜索的优化,长郡中学 向期中,深度优先搜索,在解决问题的时候，通过一定的顺序，依次枚举出问题可能存在的方案，并得出其中最优的方案的方法，被我们称之为搜索。 在由已有的状态拓展出新的状态时，后拓展出的节点优先拓展的搜索顺序，被称为深度优先搜索。 相必各位对深度优先搜索都并不陌生，所以我们今天讨论的重点在于对深度优先搜索的优化。,优化的方向,搜索问题一般求的是所有可行方案中最优的一种方案，所以我们有两个下手方向： 1）可行： 有很多方案到最后我们才发现是不行的，但是这些方案在一开始就已经决定的是不行的，所以尽早的判断出一个方案是否可行，对于问题的优化是很明显的。 2）最优： 在一些情况下，
2、无论之后如何决策，得出的方案都一定不比当前所得到的最优方案要优，那么这些方案都没有了访问的必要，可以进行剪枝。 而在大多数情况下，这两种剪枝，都是同时进行的。,小Z的生日就要到了，他的朋友小A想要帮他制作一个生日蛋糕，根据小Z的喜好，小A对蛋糕制作师提出了如下要求： 蛋糕由m个圆柱形组成，设从下往上数第i(1Ri+1且HiHi+1。 找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 (除Q外，以上所有数据皆为正整数),圆柱公式 V=R2H S侧=2RH S底=R2,生日蛋糕,解析法？,转变思路，搜索？,数据库 用( i , Ri , Hi , Vi , Si )表示第i层蛋糕的一个状态。
3、其中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 * R
4、i+1* Hi+1,确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件 1）是否做到了m层 2）是否最终体积为0 3）是否当前面积最小 若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕,基本算法,Search (i, Ri , Hi , Si , Vi) 对每层蛋糕进行搜索 if (i=m) and (Vi =0) then 更新最优值 else for Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri
5、 + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Problem-Cake 枚举所有的初始状态 - 第一层蛋糕的大小 for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ for H1n 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 当前的表面积 +
6、 余下的側面积 当前最优值 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层,那么没有必要继续往下做了，设，
7、最m层半径和高都为1，Rm=Hm=1 第m-1层半径和高都为2，Rm-1=Hm-1=2 第 i +1层半径和高都为i, Ri = Hi = m i 这样， 余下的m-i层的最小体积为,因此,剪枝条件为, 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 第 层半径和高分别为，Ri+m = Ri m ，Hi+m= Hi m 这样， 余下的m-i层的最大
8、体积为,优化？,因此,剪枝条件为, if Vi MAXi,R,H then exit,计算MINi for i1 to n do S S + i * i * i; MINm-i S 计算MAXi,R,H for R1 to sqrt(n) do for H1 to n div (R*R) do S 0; for im 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 M
9、INi then exit; 剪枝2 if Vi MAXi then exit; 剪枝3 if im then for Ri + 1 Ri downto i for Hi + 1min(Vi div (Ri + 1*Ri + 1), Hi) downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - 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.
10、 for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ 3. for H1n div (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. ,小节,可行性剪枝,剪枝2：if Vi MINi then exit,剪枝3：if Vi MAXi,R,H then exit,最优化剪枝,剪枝1： if Si-1 + 2 * Vi-1 / Ri 当前最优值 then exit,剪枝原则,正确、高效,深度搜索消耗时间 每个节点
11、操作系数 节点个数,优化 1）减少节点个数这就是剪枝优化； 2）减少每个节点的操作系数即程序操作量。,15数码问题,在44的棋盘上，摆有15个棋子，每个棋子上标有1至15的某一数字。棋盘中留有一个空格(空格用0表示)。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标面局（目标状态），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。,引入,迭代加深算法：从小到大枚举ans，用深搜判断ans是否可行。 因为ans越小越容易进行可行性剪枝。 因为ans枚举出来了，所以不存在最优性剪枝。 其实也可以理解成枚举ans，更好地进行最优性剪枝。 搜索顺序的优化就要
12、根据题目讨论了。,估价函数,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)单调递增。,估价函数,当估价函数确定以后，我们每到达一个状态s，可以用f(s)进行最优性剪枝，ans表示当前最优答案，若f(s)=ans，则当前状态舍去，进行最优性剪枝。,本题的估价函数,考虑到每次移动时除0以外的其他数最多有一个向
13、目标位置靠近一格。 所以h(s)=d(k,k) 1=k=15 h(s)满足两个条件 h(s)=h*(s) h(s1)=h(s2)+c(s1,s2),A*算法与IDA*算法,将估价函数运用到广搜的算法称为A*算法，需用堆来实现。 A*算法是理论上时间最优的算法，但所需空间太大。 为了解决A*算法的空间问题，IDA*算法被提出，它是将估价函数与迭代加深算法结合起来的算法。 所以此题用深搜，通过IDA*算法进行优化即可。,IDA*算法练习题,给你一个1n的任意排列，你需要进行最少的操作将它变成从小到大的排列。 一次操作是指将排列中的任一段剪贴出来并粘贴到任意位置。 如123764598，将其中的45
14、取出来，放到3的后面，则变为123457698,分析,这是一道IDA*的练习题，我们直接分析估计函数，搜索部分因为比较基础，这里略过。 首先很容易想到h(s)=后继正确的个数。 但这样h(s)并不满足相容性，考虑到我们一次操作会改变3个数的后继，所以将h(s)/3即可。,软件安装（NOI98）,软件安装通常是一件令人头疼的事。软件一般都包括若干个相对独立的部分（称为“组件”），在安装的时候由用户决定安装哪些部分。并且，这些相对独立的组件之间在安装时有一定的先后顺序要求。 由于当代的个人计算普遍安装了软盘驱动器，所以软件的最流行的载体形式是软盘。然而，由于软盘的容量有限，稍大一些的软件就无法用一
15、张软盘装下。这时，这些软件往往要用很多张软盘来存储。每张软盘上存储了软件的一个或多个组件。这些软盘成为软件的安装盘。,软件安装（NOI98）,由于软件的各个组件分散在不同的软盘上，而在安装时又有一定的先后顺序要求，所以很容易发生要求用户反复换盘的情况。而计算机用户在安装软件的时候，最反感的就是反复在软盘之间切换：找盘，插盘，取盘，找盘，插盘，取盘 一切都显得那么琐碎和无序，因此，有必要对软件安装盘的制作提出下述要求： 永远不要让用户将一张软盘插入两次。更精确的，要求对安装盘从1开始顺序编号，使得安装的时候，用户只要按顺序插入磁盘即可。 出于经济的考虑，通常要求安装盘的总数最少。写一个程序，对于
16、给定的软件，制定最优的安装盘方案。,分析,基本概念： （1）组件的前趋： 一个组件安装前应预先安装的组件集合称为该组件的前趋，而这个组件前趋的前趋不算这个组件的前趋。例如：1是2的前趋，2是3的前趋，但1不是3的前趋。 （2）影响制约： I对J有影响制约是指I是J的前趋。 （3）组件的后继： 一个组件可以直接影响制约的组件集合称为该组件的后继。,分析,此题初看好像可以用动态规划，但分析一下即知，它显然不符合动态规划的特征：无后效性。因为每张盘不一定放满，且组件于组件之间有制约关系，所以一个组件的选择将影响以后的组件，有明显的后效性； 由于是求最优解，且要输出存放情况，数学方法就不用考虑了。 它的建模不符合任何图论模型。 左思右想，
