深度优先搜索优化——向期中

深度优先搜索的优化长郡中学向期中深度优先搜索在解决问题的时候，通过一定的顺序，依次枚举出问题可能存在的方案，并得出其中最优的方案的方法，被我们称之为搜索。在由已有的状态拓展出新的状态时，后拓展出的节点优先拓展的搜索顺序，被称为深度优先搜索。相必各位对深度优先搜索都并不陌生，所以我们今天讨论的重点在于对深度优先搜索的优化。优化的方向搜索问题一般求的是所有可行方案中最优的一种方案，所以我们有两个下手方向：1）可行：有很多方案到最后我们才发现是不行的，但是这些方案在一开始就已经决定的是不行的，所以尽早的判断出一个方案是否可行，对于问题的优化是很明显的。2）最优：在一些情况下，无论之后如何决策，得出的方案都一定不比当前所得到的最优方案要优，那么这些方案都没有了访问的必要，可以进行剪枝。而在大多数情况下，这两种剪枝，都是同时进行的。小Z的生日就要到了，他的朋友小A想要帮他制作一个生日蛋糕，根据小Z的喜好，小A对蛋糕制作师提出了如下要求：蛋糕由m个圆柱形组成，设从下往上数第i(1=i=m)层蛋糕是半径为Ri,高度为Hi的圆柱。要求当im时，满足RiRi+1且HiHi+1。找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。(除Q外，以上所有数据皆为正整数)圆柱公式V=πR2HS侧=2πRHS底=πR2生日蛋糕321}*2*min{)*2*(1312)**(1111min1111，，满足其中，miiimiiijijimiiiiHRRRQHRRRSmjiandHHmjiandRRHRRV解析法？转变思路，搜索？数据库用(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）RiRi+1（2）HiHi+1（3）Vi+1=Vi-Ri+1*Ri+1*Hi+1（4）Si+1=Si+2*Ri+1*Hi+1确定第一层蛋糕的大小根据上一层蛋糕的大小确定下一层蛋糕该怎么做看是否符合条件1）是否做到了m层2）是否最终体积为03）是否当前面积最小若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕基本算法Search(i,Ri,Hi,Si,Vi){对每层蛋糕进行搜索}if(i=m)and(Vi=0)then更新最优值elseforRi+1Ri-1downtoiforHi+1Hi-1downtoi[Si+1Si+2*Ri+1*Hi+1Vi+1Vi-Ri+1*Ri+1*Hi+1Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]Problem-Cake{枚举所有的初始状态-----第一层蛋糕的大小}forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/forH1ndiv(R1*R1)downtomdo[S1=2*R1*H1+R1*R1V1=n-R1*R1*H1Search(1,R1,H1,S1,V1)]优化？？（1）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件:if当前的表面积+余下的側面积当前最优值thenexit设已经做了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因此剪枝条件为：ifSi-1+2*Vi-1/Ri当前最优值thenexit优化？？(2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设，最m层半径和高都为1，Rm=Hm=1第m-1层半径和高都为2，Rm-1=Hm-1=2…………第i+1层半径和高都为i,Ri=Hi=m–i这样，余下的m-i层的最小体积为imkikMIN13因此,剪枝条件为,ifViMINithenexit(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层的最大体积为优化？？)(*)(2,,jHjRMAXMijjjHRi因此,剪枝条件为,ifVi＞MAXi,R,Hthenexit计算MINifori1tondo[SS+i*i*i;MINm-iS]计算MAXi,R,HforR1tosqrt(n)doforH1tondiv(R*R)do[S0;forimdownto1do[SS+(R-i)*(R-i)*(H-i);MAXi,R,HS]]初始化Search(i,Ri,Hi,Si,Vi){对每层蛋糕进行搜索}ifSi+2*Vi/Ri当前最优值thenexit;{剪枝1}ifViMINithenexit;{剪枝2}ifVi＞MAXithenexit;{剪枝3}ifimthenforRi+1RidowntoiforHi+1min(Vidiv(Ri+1*Ri+1),Hi)downtoi[Si+1Si+2*Ri+1*Hi+1Vi+1Vi-Ri+1*Ri+1*Hi+1Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]ElseifVi=0then更新最优值Problem-Cake1.计算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/3.forH1ndiv(R1*R1)downtomdo[4.S1=2*R1*H1+R1*R15.V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.]小节可行性剪枝剪枝2：ifViMINithenexit剪枝3：ifVi＞MAXi,R,Hthenexit最优化剪枝剪枝1：ifSi-1+2*Vi-1/Ri当前最优值thenexit剪枝原则正确、高效深度搜索消耗时间≈每个节点操作系数×节点个数优化1）减少节点个数——这就是剪枝优化；2）减少每个节点的操作系数——即程序操作量。15数码问题在4×4的棋盘上，摆有15个棋子，每个棋子上标有1至15的某一数字。棋盘中留有一个空格(空格用0表示)。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标面局（目标状态），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。12345678910111213141500123456789101112131415引入迭代加深算法：从小到大枚举ans，用深搜判断ans是否可行。因为ans越小越容易进行可行性剪枝。因为ans枚举出来了，所以不存在最优性剪枝。其实也可以理解成枚举ans，更好地进行最优性剪枝。搜索顺序的优化就要根据题目讨论了。估价函数•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以外的其他数最多有一个向目标位置靠近一格。所以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*算法练习题给你一个1~n的任意排列，你需要进行最少的操作将它变成从小到大的排列。一次操作是指将排列中的任一段剪贴出来并粘贴到任意位置。如123764598，将其中的45取出来，放到3的后面，则变为123457698分析这是一道IDA*的练习题，我们直接分析估计函数，搜索部分因为比较基础，这里略过。首先很容易想到h(s)=后继正确的个数。但这样h(s)并不满足相容性，考虑到我们一次操作会改变3个数的后继，所以将h(s)/3即可。软件安装（NOI98）软件安装通常是一件令人头疼的事。软件一般都包括若干个相对独立的部分（称为“组件”），在安装的时候由用户决定安装哪些部分。并且，这些相对独立的组件之间在安装时有一定的先后顺序要求。由于当代的个人计算普遍安装了软盘驱动器，所以软件的最流行的载体形式是软盘。然而，由于软盘的容量有限，稍大一些的软件就无法用一张软盘装下。这时，这些软件往往要用很多张软盘来存储。每张软盘上存储了软件的一个或多个组件。这些软盘成为软件的安装盘。软件安装（NOI98）由于软件的各个组件分散在不同的软盘上，而在安装时又有一定的先后顺序要求，所以很容易发生要求用户反复换盘的情况。而计算机用户在安装软件的时候，最反感的就是反复在软盘之间切换：找盘，插盘，取盘，找盘，插盘，取盘……一切都显得那么琐碎和无序，因此，有必要对软件安装盘的制作提出下述要求：永远不要让用户将一张软盘插入两次。更精确的，要求对安装盘从1开始顺序编号，使得安装的时候，用户只要按顺序插入磁盘即可。出于经济的考虑，通常要求安装盘的总数最少。写一个程序，对于给定的软件，制定最优的安装盘方案。分析基本概念：（1）组件的前趋：一个组件安装前应预先安装的组件集合称为该组件的前趋，而这个组件前趋的前趋不算这个组件的前趋。例如：1是2的前趋，2是3的前趋，但1不是3的前趋。（2）影响制约：I对J有影响制约是指I是J的前趋。（3）组件的后继：一个组件可以直接影响制约的组件集合称为该组件的后继。分析此题初看好像可以用动态规划，但分析一下即知，它显然不符合动态规划的特征：无后效性。因为每张盘不一定放满，且组件于组件之间有制约关系，所以一个组件的选择将影响以后的组件，有明显的后效性；由于是求最优解，且要输出存放情况，数学方法就不用考虑了。它的建模不符合任何图论模型。左思右想，是最优化的序列问题，且数据范围不算太大，最后只有用搜索了。我们定义如下变量MaxCap：Longint每张软盘的最大容量；N：Integer组件数；MinDisk:array[0..MaxN]ofInteger；最少的软盘数；Father：array[0..MaxN]ofInteger；Father[I]指组件I的所有前趋；Module：array[0..MaxN]ofInteger；Module[I]指第I次选择的软件；ParModule:array[0..MaxN]ofInteger；存储Module的最优值；ModCap:array[0..MaxN]ofInteger；ModCap[I]指组件I的字节数；Choose:array[0..MaxN]ofBoo