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

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）组件的后继： 一个组件可以直接影响制约的组件集合称为该组件的后继。,分析,此题初看好像可以用动态规划，但分析一下即知，它显然不符合动态规划的特征：无后效性。因为每张盘不一定放满，且组件于组件之间有制约关系，所以一个组件的选择将影响以后的组件，有明显的后效性； 由于是求最优解，且要输出存放情况，数学方法就不用考虑了。 它的

17、建模不符合任何图论模型。 左思右想，是最优化的序列问题，且数据范围不算太大，最后只有用搜索了。,我们定义如下变量,MaxCap：Longint 每张软盘的最大容量； N：Integer 组件数； MinDisk: array0.MaxN of Integer； 最少的软盘数； Father： array0.MaxN of Integer； FatherI指组件I的所有前趋； Module： array0.MaxN of Integer； ModuleI指第I次选择的软件； ParModule: array0.MaxN of Integer； 存储Module的最优值； ModCap: arra

18、y0.MaxN of Integer； ModCapI指组件I的字节数； Choose: array0.MaxN of Boolean； ChooseI为true表示组件I未选过，false反之； Top: array0.MaxN, 0.MaxN of 0.1； TopI，J是指J对I有影响制约； Next： array0.MaxN, 0.MaxN of Integer； NextI是指I的所有后继。,搜索方式,由于组件有前后制约关系，且软盘数一定小于等于组件数，所以搜索应模拟将组件依次放入软盘中的过程，即当前应选择那个组件，选定后再看它是否能放入当前软盘，不行则加一张软盘，继续放 再从中找出

19、用软盘最少的序列。 这样就很容易用深度优先搜索，只需传几个变量： Order：Integer 搜索的层数，即当前选第Order张软盘； Num：Integer 当前所用的软盘数； Free：Longint 当前这张软盘的剩余空间； LeftModCap：Extended 剩余软盘的总字节；,procedure SENSOR(Order, Num: Integer；Free: Longint； LeftModCap：Extended)； var I, J: Integer； begin if 所有组件搜完then begin if MinDisk Free then SENSOR(Order +

20、 1,Num + 1,MaxCap - ModCapI,LeftModCap - ModCapI)增加一张软盘，继续搜索 else SENSOR(Order + 1,Num,Free - ModCapI,LeftModCap - ModCapI)；继续搜索这张盘 ChooseI := true； ModuleOrder := 0； for J := 1 to NextI,0 do Inc(FatherNextI,J)；还原Choose，Module，Father数组： end； end；,复杂度估计,编程复杂度：为一般搜索，较简单。 空间复杂度：此题的范围较小，数组，邻接表，稀疏矩阵 不必对其

21、做特殊优化。 时间复杂度：此题用搜索，层数为MaxN层，每层的时间复杂度为MaxN，所以程序时间复杂度为MaxN！，即100！。这样的复杂度无论如何是承受不了的。因此，剪枝优化就必不可少了。,分支定界,描述：当你搜索到任意解之后，如果不能很好的利用这一结果就太浪费了。应当如何运用呢？如果以后的搜索中，当前序列如何继续都不可能搜出比当前已经搜到的最优解更好的解（称为劣序）就不必继续了。但如何判断是否为为劣序呢？ 实现：如果已搜到第Order个，没有选的组件的总和为LeftModCap，当前软盘的剩余容量为Free，那么总软件数不可能比P少（P:=LeftModCap div MaxCap；if

22、LeftModCap mod MaxCap Free then P := P + 1）。这样可以免去一些劣序，节省很多时间。,分支定界,证明：设所有组件的字节总和为M，所有软盘的剩余空间总和为Waste（软盘的剩余空间：软盘没有装组件的空间）。软盘数（MWaste）divMaxCap，M与MaxCap是一定的，所以剩余空间最小，软盘数也最少。假设剩余的软盘没有制约关系，且剩余组件可以一个挨一个的放入（在中间不会出现剩余空间，最后可以出现剩余空间），组件所需的软盘一定最少。如果这种理想最少的软盘数已用的软盘数还比已搜索到的软盘最优解还多或等于，就没必要继续了，因为不可能出现比这种情况跟优的情况了

23、。,劣者靠后,描述：劣者靠后，顾名思义就是性质不佳的组件靠后放。当如何定义性质不佳呢？又如何保证不丢失最优解呢？ 实现：如果当前组件放在当前软盘中之后，此张软盘再也不能放其他组件，且这组件无后继，而这个组件又不是可以放在当前软件中的最大的组件，那么它是就劣者，就不应该在当前放入这张软盘。,劣者靠后,证明：可以用假设法证明； 假设命题不成立：即劣者不放在此可能无法形成最优解。 设可以放在当前软件（设为I）中的所需空间最大的组件被编号为K。 按照假设命题叙述，可能最优解是劣者放在此，K放在以后的软盘（设为J）中。但实际上，如果劣者放在此，K放在以后的软盘中可以形成最优解，那么交换二者的位置是另一种

24、最优解(因为I中放劣者或K都是一个，效果一样，而J中放劣者之后，空间更大，而且不会对其他组件产生影响)，所以劣者不放在此肯定可以形成最优解。 所以命题错误。 所以劣者必不放在此。,劣者靠后,其它剪枝,除去可行性剪枝和最优化剪枝之外，还有一些其他的剪枝，他们的效果也都是不错的。 接下来看一道例题。,拓扑排序,描述：再一个软盘中的组件，如果没有制约关系，那么调换其顺序，又将变为另一种方案（此软件有n个组件，就有N！种重复情况），而如果很多软盘都如此，将有许多重复情况，时间复杂度将聚增。如何避免这些情况呢？ 实现：先将所有的组件按拓扑排序（如由多个拓扑排序，任意一个），然后将原顺序变为拓扑序列（按拓

25、扑排序后的序列），然后每张软盘内部组件编号（拓扑排序后的编号）的顺序规定为增序，这样即避免了重复，又不会漏解，一举两得。,拓扑排序,证明：假设有时必须乱序（乱序：不是增序）才可得到最优解。 因为乱序可以得到最优，那么将这些组件按增序也同样可以得到最优（因为将顺序变为增序后，是拓扑序列，所以内部符合制约关系；总字节不变，仍然可以放入此软盘；对下面几张盘的影响制约也不变）。 所以是增序也可得到最优解。 所以假设命题错误。 所以软盘内的组件一定要按增序排列。 （补充：拓扑序列有多种，但任意一种都行，这样应该尽量让后继多的组件在前面，这样有利于搜索，证明略）。,节省空间,描述：由于搜索是枚举每一个组件

26、，所以可能当前软盘下还可放入若干个组件，搜索却选择字节太大而无法放入这张盘的组件放入下一张盘，这张盘的空间又不会再用，所以浪费了空间。 实现：应先看是否有可以放入这张软盘的组件，没有再枚举放如下一张软盘的组件，否则就不用看了。 证明：假设当前软盘I有空间可以放J，却要不放才能得到最有解。 那么将J有后面拿上来，放入I中，不会改变影响制约关系，仍然是最优解。 所以假设命题错误。 有空可以放一定不可空着。,选用慎用,1.提前贪心： 贪出一个较有解，这样有利于分支定界，也可以避免特殊数据的刁难（有时贪心的解就是最优解）。 2.随机化： 由于一般再搜索过程中，枚举找下一个组件时，一般用循环语句for

27、I := 1 to N do ，但有时数据是完全颠倒的，这样将花去太多时间，所以可以采用随机化，确定I是从1枚举到N，还是从N枚举到1，因为是7随机的，所以无论数据如何刁难，平均时间都差不多，不会因为数据的选取而时间复杂度猛增。 3.时间限制： 由于是搜索题，所以无论什么剪枝，都很难保证一定可以再时限内出解，且有 有些数据最优解在时限内已得到，只是不能确定是否为最优，程序没有退出，而导致超时。所以用时间限制可以保证不超时，但不能保证正确。 源程序见目录下software.pas,积木搭建（IOI2000）,单位立方体(unit cube)是一个111的立方体，它的所有角的x,y和z坐标都是整数

28、。我们称两个单位立方体是连通的，当且仅当他们有一个公共的面；一个构形(solid)或者是一个单位立方体，或者是由多个单位立方体组成的连通物体(如图一所示)，它的体积就是它所含的单位立方体的个数。 一块积木(block)是一个体积不超过4的构形。如果两块积木可以平移、旋转(注意，不能成镜像)操作变得完全一样，我们就称它们属于同一类。这样，积木总共有12类(如图2所示)。图2中积木的不同颜色仅仅是为了帮助你看清楚它的结构，并没有其他的含义。 一个构形可以由若干块积木组成。如果用一些积木可以互不重叠的搭建出某个构形，那么就称这些积木是这个构形的一种分解(decomposition)。 你的任务是写一

29、个程序,对于给定的一组积木种类和一个构形S,求出境可能少的积木个数,使得他们能够搭建出构形S。你只需给出这个最少的积木个数，以及这些积木各自所属的种类，而不必给出具体的搭建方案。,数据结构,为描述清楚，先列出数据结构： TPoint = record 空间中的一个单位立方体 x,y,z: Shortint; end; Tar： array1.50 of TPoint; 目标形状 TCube = array1.4 of TPoint; 一个积木 Cube: array1.most of TCube; 所有的状态,分析,看到这个题目，就会想到搜索。这是一道有一定难度的题目，盲目的搜索是不行的，因为

30、题目中说明了每种积木都可以经过翻转和平移，然而，只要得到了平移或翻转后的积木，我们就只需要一个一个的往构形里面填，直到填满，这显然是一个深度优先搜索。然而对于这道题目来说，除了搜索之外，还有一个难点，就是生成所有的翻转或平移后的积木状态。 我们考虑用一个三员组表示空间中的1*1*1的立方体(单位立方体)，三员组(x,y,z)表示空间(x,y,z)处有一个单位立方体。这样我们就有三种数据结构： TPoint = record一个点 x,y,z: Shortint; end； TCube = array1.4 of TPoint;一个积木 TBlock = array1.50 of TPoint;

31、给定的三维形状,怎样生成所有状态？,首先，题目中指出：可以平移，翻转，但不可以成镜像。如何处理平移？我们只要保存一个积木中四个顶点的相对位置，在搜索的时候自然就可以完成平移，在此我们规定一个积木的一个单位立方体为(0,0,0)，则其余三个可以用相对于这个单位立方体的位置来表示。如何处理翻转？由于题目规定不可以成镜像，所以，我们在生成所有状态时的翻转过程中，必成偶数次镜像(因为：成偶数次镜像等于没成镜像)。由于旋转积木很难理解，也有可能会遗漏一些情况，我们采用的是旋转坐标轴的方法。 可以这么理解旋转坐标轴法：,旋转坐标轴法,可以这么理解旋转坐标轴法： 顾名思义，就是要在三维空间中，将坐标轴旋转，

32、当然，旋转后的坐标要两两垂直，在满足这个条件的情况下，用temp:TCube表示某积木cube Tcube经过某种旋转后所得的状态。设func(temp)表示有几条坐标线(射线)所在直线和原来这条坐标线所在直线的不重合的。考虑func(temp)的不同值：设f(temp)表示在func(temp)的基础上得到的表示temp性质的函数:,对于某一条特定的坐标，如果规定一个方向为正方向，则可以用g(temp)表示旋转后的新坐标线中方向和原来方向不同的条数。(注：这里的方向并非表示三维空间中的方向，只表示正负)。易得：若f(temp)+g(temp)为偶数，则temp是符合题意，即成偶数次镜像的。

33、搜索的时候，另需一个数组space:array1.7,1.7,1.7 of byte; spacex,y,z=1表示此处未放, spacex,y,z=0表示放了。 procedure search(u,dep,left: integer); var i: integer; begin if left = 0 then begin 修改;退出 end; 若(left 1) DIV 4 + 1 = min then Exit;分支定界 找到一个space taru,1,taru,2,taru,30的u;tar是目标形状 若不存在则退出; repeat 找到一个可以放置且覆盖(taru,1,taru

34、,2,taru,3)的积木; 若找到则: begin 放下; search(u+1,dep+1,left-counti);counti是第I个积木的体积 end; until 找不到; end;,分析,值得注意的是, 找一个可放置的积木时,我们不仅要枚举积木，而且要枚举点(taru,1,taru,2,taru,3)在积木中的位置。如下面的图形:我们要枚举点(taru,1,taru,2,taru,3)在积木中的四中位置情况,然后递归搜索，这样才能够全面。 至此，这道题目可以说是得到比较圆满解决了，按照这种方法便出来的程序速度是比较快的，能够对一半左右的测试数据。而接下来我们要做的，就是进行优化。

35、,优化,这里讲的优化，主要是针对搜索时的一些技巧来讲的。 在搜索的过程中，我们发现：我们的目的实际上就是要把一些积木放到构形里面去，不妨换个角度，把一个构形看成由许多单位立方体构成的，同样的，一个积木也是由许多单位立方体构成。我们把这个构形拆开承单个的单位立方体，每次从里面去出成分和某一块积木陈分相同一些单位立方体。因此，不妨令这些单位立方体是有序的，同样，积木的描述也是有序的。搜索时，由小到大去填充构形的某一个单位立方体，如果轮到填充构形中的某一个单位立方体时，我们就必须让它成为某一个积木描述中最靠前(最”小”)的那一部分，因为如果不这样，这个单位立方体就再不可能被覆盖了。这样就免去了上面所

36、说的确定这个单位立方体中相对位置的过程，效率有很大的提高。然而，我们需要一个标准来衡量一个单位立方体的“大小”，这很简单，就先以x为关键字排序；在x相同的前提下，以y为关键字排序；在x,y都相同的前提下，以z为关键字排序。,优化,在程序开始时可以得到一个最优值best=(n 1) DIV 4 + 1;一旦搜索到的解达到了这个值就可以中止程序。 因为各种积木的第一个单位立方体都是(0,0,0)，保存各种状态时只需用三个TPoint，虽然这对于空间存储来说并不是问题。 此外,搜索的顺序对于时间效率很重要，在编程当中，我们可以发现，若把较为平直的积木放在cube数组的前面，这样，循环时先找到的就是较

37、平直的，事实证明，用这样的方法，很多的数据都有明显的超时，这可能是由于平直的积木不利于剪枝而造成的。我们可以同样考虑将积木按体积从达到小排序，这样，即容易出解也利于剪枝。,优化,如下表，给出了某一组数据的出解时间： 空间上：有用状态数不是很多，105种，而且目标形状的体积也不是很大，所以空间上是完全承受的了的。 时间上：由于有很多的状态是不能被放置的，所以有了上面的分支定界和剪枝，应该可以在规定时间内出解。 预处理程序见目录下：preparation.pas 解题程序见目录下：block.pas,道路,n(n=10)个点的有向完全图，每条边都有一个实数权值，现在我们要找一条长度为n的路使得路上

38、的边权和最接近一个数x。 注意：每个点都有自环。 自环指的是对于一个点，存在一条边，从这个点出发，指向这个点本身。 这条路径允许经过重复的点和重复的边。,分析,考虑搜索状态：将所有的路径都搜索出来。 状态量：当n=10时，状态量高达1010，所以广搜是不行的。 那么考虑进行深搜，考虑深搜的剪枝 搜索顺序（无关紧要） 可行性剪枝（不行，每条路径都可行） 最优性剪枝（有可能，但效果可能不明显）,经典剪枝（二分法）,这种剪枝方法基于将问题缩小规模的思想。 我们可以将一条路径分两次搜索，每次搜一半。 先搜出所有的长度为n/2的路径，并存下来，当做路径的前半段。 用fij数组存下所有以i结尾的长度为n/

39、2的路径权值和，并将j这一维按权值和排序。即fi1表示所有路径中权值和最大的， fi2表示权值和第二大的，以此类推。 然后搜后半段路径，每搜出一条路径，若这条路径以i开头，权值和为y，则在fi中二分查找一个离x-y最近的权值和，构成完整的路径。 Noi2001方程的解数也是用这个方法。,算符破译（NOI2000）,考古学发现，几千年前古梅文明时期的数学非常的发达，他们懂得多位数的加法和乘法，其表达式和运算规则等都与现在通常所用的方式完全相同（如整数是十进制，左边是高位，最高位不能为零；表达式为中缀运算，先乘后加等），唯一的区别是其符号的写法与现在不同。有充分的证据表明，古梅文明的数学文字一共有

40、13个符号，与 0,1,2,3,4,5,6,7,8,9,+,*,= 这13个数字和符号（称为现代算符）一一对应。为了便于标记，我们用13个小写英文字母a,b,m代替这些符号（称为古梅算符）。但是，还没有人知道这些古梅算符和现代算符之间的具体对应关系。,在一个石壁上，考古学家发现了一组用古梅算符表示的等式，根据推断，每行有且仅有一个等号，等号左右两边为运算表达式（只含有数字和符号），并且等号两边的计算结果相等。 假设这组等式是成立的，请编程序破译古梅算符和现代算符之间的对应关系。 输入文件 输入文件的第一行为等式的个数N（1=N=1000），以下N行每行为一个等式。 每个等式的长度为5个字符到11个字符。,输出文件 如果不存在对应关系能够满足这组等式，输出“noway”和一个换行/回车符。 如果有对应关系能够满足这组等式，输出所有能够确定的古梅算符和现代算符的对应关系。每一行有两个字符，其中第一个字符是古梅算符，第二个字符是对应的现代算符。输出按照字典顺序排序。,样例： 输入： 输出： 2 a6 abcdec b* cdefe d= f+ 样例说明: 在上例中，可能对应的现代表达式为6*2=12，2=1+1，6*4=24，4=2+2，6*8=48，8=4+4。可见，能够确定的对应关系只有a对应6，b对应*，d对应=，f对应+，应该输出；而c,e虽