算法合集之《搜索方法中的剪枝优化》

搜索方法中的剪枝优化南开中学 齐鑫【关键字】搜索、优化、剪枝【摘要】本文讨论了搜索方法中最常见的一种优化技巧剪枝，而且主要以剪枝判断方法的设计为核心。文章首先借助搜索树，形象的阐明了什么是剪枝；然后分析了设计剪枝判断方法的三个原则：正确、准确、高效，本文将常见的设计剪枝判断的思路分成可行性剪枝和最优性剪枝两大类，并结合上述三个原则分别以一道竞赛题为例作了说明；文章最后对剪枝方法作了一些总结一、 引子搜索是人工智能中的一种基本方法，也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的时候，首要的问题不外乎两个：1. 建立算法结构。2. 选择适当的数据结构。然而众所周知的是，搜索方法的时间复杂度大多是指数级的，简单的不加优化的搜索，其时间效率往往低的不能忍受，更是难以应付信息学竞赛严格的运行时间限制。本文所讨论的主要内容就是在建立算法的结构之后，对程序进行优化的一种基本方法剪枝。图1 搜索树首先应当明确的是，“剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。我们在编写搜索程序的时候，一般都要考虑到剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。设计出好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，也可能适得其反。那么，我们就应当首先分析一下设计剪枝判断方法的时候，需要遵循的一些原则。二、 剪枝的原则原则之一：正确性。我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了）。原则之二：准确性。在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。因此，准确性可以说是剪枝优化的生命。当然，为了提高剪枝判断的准确性，我们就必须对题目的特点进行全面而细致的分析，力求发现题目的本质，从而设计出优秀的剪枝判断方案。原则之三：高效性。一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。当然，我们在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类：1. 可行性剪枝。2. 最优性剪枝（上下界剪枝）。 下面，我们就结合上述的三个原则，分别对这两种剪枝判断方法进行一些讨论。三、可行性剪枝我们已经知道，搜索过程可以看作是对一棵树的遍历。在很多情况下，并不是搜索树中的所有枝条都能通向我们需要的结果，很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候，就能够判断出来并立即剪枝，程序的效率往往会得到提高。而所谓可行性剪枝，正是基于这样一种考虑。下面我们举一个例子Betsy的旅行(USACO)。题目简述：一个正方形的小镇被分成N2个小方格，Betsy要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目。我们用深度优先的回溯方法来解决这个问题：Betsy从左上角出发，每一步可以从一个格子移动到相邻的没有到过的格子中，遇到死胡同则回溯，当移动了N2-1步并达到左下角时，即得到了一条新的路径，继续回溯搜索，直至遍历完所有道路。但是，仅仅依照上述算法框架编程，时间效率极低，对N=6的情况无法很好的解决，所以，优化势在必行。对本题优化的关键就在于当搜索到某一个步骤时，能够提前判断出在后面的搜索过程中是否一定会遇到死胡同，而可行性剪枝正可以在这里派上用场。我们首先从“必要条件”，即合法的解所应当具备的特征的角度分析剪枝的方法，主要有两个方向：1. 对于一条合法的路径，除出发点和目标格子外，每一个中间格子都必然有“一进一出”的过程。所以在搜索过程中，必须保证每个尚未经过的格子都与至少两个尚未经过的格子相邻（除非当时Betsy就在它旁边）。这里，我们是从微观的角度分析问题。2. 在第一个条件的基础上，我们还可以从宏观的角度分析，进一步提高剪枝判断的准确性。显然，在一个合法的移动方案的任何时刻，都不可能有孤立的区域存在。虽然孤立区域中的每一个格子也可能都有至少两个相邻的空的格子，但它们作为一个整体，Betsy已经不能达到。我们也应当及时判断出这种情况，并避免之。以上两个剪枝判断条件都是正确的，其准确度也比较高。但是，仅仅满足这两点还不够，剪枝判断的操作过程还必须力求高效。假如我们在每次剪枝判断时，都简单的对N2个格子进行一遍扫描，其效率的低下可想而知。因此，我们必须尽可能的简化判断的过程。实际上，由于Betsy的每一次移动，只会影响到附近的格子，所以每次执行剪枝判断时，应当只对她附近的格子进行检查：对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy每次移动到一个新位置，都只会使与之相邻的至多4个格子的标志值发生变化，只要检查它们的标志值即可。 已经到过的格子 尚未到过的格子 Betsy的移动方向 Betsy的位置图2 剪枝原理示意图而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对Betsy附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理：上图给出了可以剪枝的三种情况。由于Betsy到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。经过上述的优化，程序的时间效率有了很大的提高（参见附录）。一般说来，可行性剪枝多用于路径搜索类的问题。除本例外，如Prime Circle (ACM Asian Regional 96)等问题，也都可以使用这种剪枝方法。在应用可行性剪枝的时候，首先要多角度全面分析问题的特点（本题就是从微观和宏观两个角度设计剪枝方法），找到尽可能多的可以剪枝的情况；同时，还必须注意提高剪枝的时间效率，所以我们使用了“局部判断”的方法，特别是在处理第二个剪枝条件时，更是通过局部判断来体现整体性质（是否有孤立区域），这一技巧不仅在设计剪枝方法的时候能够发挥作用，在其他方面也有着极为广泛的应用。三、 最优性剪枝在我们平时遇到的问题中，有一大类是所谓最优化问题，即所要求的结果是最优解。如果我们使用搜索方法来解决这类问题，那么，最优性剪枝是一定要考虑到的。为了表述的统一，首先要作一些说明：我们知道，解的优劣一般是通过一个评价函数来评判的。这里定义一个抽象的评价函数“优度”，它的值越大，对应的解也就越优（对于具体的问题，我们可以认为“优度”代表正的收益或负的代价等）。然后，我们再来回顾一下搜索最优解的过程：一般情况下，我们需要保存一个“当前最优解”，实际上就是保存解的优度的一个下界。在遍历到搜索树的叶子节点的时候，我们就能得到一个新的解，当然也就得到了它的评价函数值，与保存的优度的下界作比较，如果新解的优度值更大，则这个优度值就成为新的下界。搜索结束后，所保存的解就是最优解。那么，最优性剪枝又是如何进行的呢？当我们处在搜索树的枝条上时，可以通过某种方法估算出该枝条上的所有解的评价函数的上界，即所谓估价函数。显然，大于当前保存的优度的下界，是该枝条上存在最优解的必要条件，否则就一定可以剪枝。所以，最优性剪枝也可以称为“上下界剪枝”。同时，我们也可以看到，最优性剪枝的核心问题就是估价函数的建立。下面举一个应用最优性剪枝的典型例题最少乘法次数。题目简述：由开始，通过最少的乘法次数得出，其中为输入数据。（参见参考书目1）因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列，满足要求，并且使最小。我们选择回溯法作为本程序的主体结构：当搜索到第层时，的取值范围在到之间，为了尽快接近目标，应当从开始从大到小为取值，当然，选取的数都不能大于。当搜索到出现时，就得到了一个解，与当前保存的解比较取优。最终搜索结束之后，即得到最终的最优解。如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化：优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是，即当前搜索深度为）：然而，这个估价函数的准确性太差，特别是当大于时，只能等于1，根本不能发挥剪枝的作用。因此，无论是深度优先的回溯法还是宽度优先的A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。下面，我们再讨论一些进一步的优化手段优化之二：着眼于估价函数的“生命”准确性。我们可以利用加法在奇偶性上的特点的推广，使估价函数在某些情况下的准确性得到一定的提高（具体改进请参见附录）。优化之三：我们新建立的这个估价函数虽然准确性稍有提高，但时间复杂度也相应提高。为了提高剪枝的效率，我们可以使用一种“逐步细化”的技巧，即先使用一次原先的估价函数（快而不准）进行“过滤”，再使用新的估价函数（稍准但较慢）减少“漏网之鱼”，以求准确性和运行效率的平衡。优化之四：我们可以在搜索之前将分解质因数，对每个质因数先使用上述搜索方法求解（如某个质因数仍太大，还可以将其减1，再分解），即相当于将构造数列的过程，划分成若干阶段处理。这样得到的结果虽然不一定是全局的最优解，却可以作为初始设定的优度下界，使后面的全局搜索少走很多弯路。事实上，该估计方法相当准确，在很多情况下都能直接得到最优解，使程序效率得到极大提高。优化之五：当数列中的当前最大数超过后，原估价函数就难以发挥作用了。但是，此后的最优方案，实际上就等价于从到这个数中，选出尽可能少的数（可重复），使它们的和等于。这个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。这道题中所体现的最优性剪枝技巧是很多的，它们的优化效果也是非常显著的（优化效果的分析请参见附录）。由本题，并结合以前的经验，我们可以简单的总结一些在应用最优性剪枝时需注意的问题：1. 估价函数的设计当然首先得满足正确的原则，即使用“必要条件”来剪枝。在此基础上，就要注意提高估价的准确性。本题的优化之二就是为了这个目的。2. 与其他剪枝判断操作一样，最优性剪枝的估价函数在提高准确性的同时，也必须注意使计算过程尽量高效的原则。由于剪枝判断在运行时执行极为频繁，所以对其算法进行精雕细琢是相当必要的，有时甚至还可以使用一些非常手法，如前述的“逐步细化”技巧，就是一种寻求时间效率和精确度相平衡的方法。3. 在使用最优性剪枝时，一个好的初始“优度”下界往往是非常重要的。在搜索开始之前，我们可以使用某种高效方法（如贪心法等）求出一个较优解，作为初始下界，经常可以剪去大量明显不可能的枝条。本题使用划分阶段的搜索方法进行初始定界，就带来了大幅度的优化。4. 本节所举的是在深度优先搜索中应用最优性剪枝的例子。当然，在广度优先搜索中，也是可以使用最优性剪枝的，也就是我们常说的分枝定界方法。本题也可以使用分枝定界结合A*算法的方法来解决（用改进的估价函数作为优度上界估计，即h*函数；前述的动态规划方法可以作为优度下界估计），但时间效率和空间效率都要差一些。不过，在有些问题中，分枝定界和A*算法的结合以其较好的稳定性，还是有用武之地的。四、 总结搜索方法，因其在时间效率方面“先天不足”，所以人们才有针对性的研究出了很多优化技巧。本文所论述的“剪枝”就是最常见的优化方法之一，几乎可以说，只要想使用搜索算法来解决问题，就必须考虑到剪枝优化。另外需要说明的是，本文所介绍的可行性和最优性两种剪枝判断，其分类只是依据其不同的应用对象，而前面阐述的剪枝方法的三个原则正确、准确和高效，才是贯穿于始终的灵魂。本文还介绍了一些剪枝中的常用技巧，如“局部分析”、“逐步细化”等。恰当的使用它们，也能够使程序的效率（主要是时间效率）得到相当的提高。但是，剪枝方法无论多么巧妙，都不能从本质上降低搜索算法的时间复杂度，这是不争的事实。因此，我们在动手设计一个搜索算法之前，不妨先考虑一下是否存在着更为有效的方法。而且，在信息学竞赛中，还有一个编程复杂度的问题。我们对一个搜索算法使用了很多优化技巧，虽然可能使程序的时间效率得到一定的提高，但却往往要消耗大量的编程时间，很容易造成“拣了芝麻，丢了西瓜”的结果。总之，我们在实际设计程序的过程中，不能钻牛角尖，而更应当充分发挥思维的灵活性，坚持“具体问题具体分析”的思想方法。【参考书目】1. 青少年国际信息学（计算机）奥林匹克竞赛指导人工智能搜索与程序设计刘福生 王建德 编著2. Informatics Olympic【附录】一、 “Betsy的旅行”的测试情况：（单位：秒）N值路径数程序运行时间无剪枝第一种剪枝第二种剪枝两种剪枝210.010.010.010.01320.010.010.010.01480.010.010.010.01586 0.170.010.010.016177041.25 0.44 0.33 0.11788418Very long28.0626.86 8.51（测试环境：Pentium II 266MHz/64MB）可见，使用前述的可行性剪枝判断方法，能够使程序的时间效率得到相当大的提高。二、“最少乘法次数”的估价函数的改进：最初的估价函数的设计思路实际上是在当前数列的基础上理想化的构造，当时，原估价方法认为只需再进行一次加法，即找一个数与相加就够了。然而，这只是保证了能够得到大于等于的数，并不一定恰好得到。我们可以作如下分析：首先，任何一个自然数都可以表示成的形式，我们可以设表示一个自然数所对应的值。显然，对于任何两个自然数和，都有（我们由此可以很容易的联想到“奇+奇=偶，偶+偶=偶，奇+偶=奇”的性质）。然后，我们再研究前述估价时所构造的数列： （其中，）在应用新的剪枝判断之前，我们应当先检验，这个条件可以保证只有构造上述数列才是最优的。若存在自然数，使得，由，则有 （是的必要条件）即中的任何一个数与相加都不可能得到。所以，如果，则在得到后，至少还需要再进行两次加法才有可能得到。虽然上述改进可以使估价函数在某些情况下的准确性略有提高，但是其本身的时间效率却比较差，这是因为新的估价函数不但包括了原先的估价函数（构造数列），而且还增加了诸如求这样的操作。因此，尽管新的估价函数只是原估价函数的改进，而不象在“Betsy的旅行”中那样是互相补充的两个方面，但在实际的程序中，仍然要连续调用两个估价函数，即使用前文所述的“逐步细化”技巧。最后需要说明的是，本文所提及的估价函数中所有使用对数运算的部分在实际的程序中都必须改用循环累加的方式来实现。这是因为实数函数在计算机内部是通过级数展开式计算的，实际上也是循环结构，而且更为复杂低效。当然，实际的程序中，也还有其他的一些细节上的优化。三、“最少乘法次数”的测试情况及分析：部分测试数据的运行时间：（单位：秒）N值乘法次数运行时间程序1程序2程序3程序4程序5程序6程序712710 0.22 0.22 0.05 0.06 0.060.01 0.1619111 3.52 3.90 0.83 0.55 0.55 0.27 1.753821113.0213.29 1.05 0.94 0.66 0.33 2.6951112Very longVery long 0.82 5.66 0.33 0.27 1.816351346.9640.3720.6519.6110.06 8.13Overflow7191345.5939.1145.6413.4539.11 6.6427.3510021311.8110.65 2.74 3.46 1.10 0.99 6.26102313Very longVery long 2.66Very long 1.04 0.88 6.15135713 9.51 6.98 5.93 5.44 3.40 2.7413.3518941444.8737.2413.8915.49 6.37 4.6123.68（测试环境：Pentium Pro 233MHz/64MB）当n在1000以内的时候，程序6的运行时间都不超过10秒，其中只有十几个测试数据的运行时间在5秒以上。程序说明：程序编号程序特征要点简单的剪枝判断改进的剪枝判断初始定界(分段搜索)动态规划的结合使用A*算法结合分枝定界1323333343353336333373测试结果分析：首先，我们比较一下三个主要的优化点改进的剪枝判断（逐步细化）、初始定界和结合动态规划单独应用的优化效果：1. 单纯加入改进的剪枝判断方法（程序2），程序时间效率的提高不大，这主要是因为新的估价函数的准确性只是稍有提高，而其本身的时间效率却比较低，这在一定程度上抵消了估价准确性提高所能带来的优化效果。2. 本题的初始定界方法（程序3），由于准确性非常高（经常能直接得到最优解），所以能够使程序的效率得到比较明显的改善，在前四个程序中，只有它能够在一分钟以内完成表中所列出的每个测试数据，特别是n=1023时，效果尤为显著。但是，如果初始定界的准确性稍有下降，则程序的优化效果就会极不明显（如n=719）。3. 加入动态规划后的程序（程序4），实际上使得搜索过程主要集中在n/2以下，在相当程度上避免了对n/2到n的估价函数几乎没有作用的部分的搜索，所以程序4几乎在每个测试点上都比较明显的优于程序1。然后，我们再来看看程序5，由于使用了初始定界，使搜索前就已经有了比较准确的优度下界，所以新的准确性较高的估价函数发挥作用的概率就比较高，因此优化效果相当明显。与程序3一样，在初始定界不甚准确的时候（n=719），优化效果大打折扣。这7个程序中最好的当然是程序6，由于综合了各种优化方法，使它们优势互补，所以获得了最稳定的优化效果。最后，我们还可以看到，在本题的特定情况下，经过充分优化的深度优先的回溯法搜索无论是在时间上，还是在空间上都明显优于A*算法（程序7使用保护模式编译，除了A*算法外，还结合使用了分枝定界的方法，否则时空效率更差）。【程序】一、“Betsy的旅行”的程序（使用两种剪枝）：$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 65520,0,655360program Betsy;IOI99集训队 论文例题1：Betsy的旅行说明: 1.为了便于测试计时，本程序采用命令行输入的方式。 2.为了处理的方便，程序中在地图的最外层补了一圈标志格。 3.程序中，将逻辑上相对独立的程序段用空行分开。const max=7;本程序所能处理的最大的数据规模 delta:array1.4,1.2of shortint=(-1,0),(0,1),(1,0),(0,-1);方向增量var map:array0.max+1,0.max+1of integer; 用于标记Betsy的移动路线的地图： 没有到过的位置标记-1， 最外层的标志格标记0， 其它格子标记Betsy到达该格子时的移动步数 left:array0.max+1,0.max+1of shortint; 标志数组：记录每个格子相邻的四个格子中尚未被Betsy经过的格子的数目 n:1.max;地图边长 n2:integer;N*N s:longint;累加器,记录Betsy的移动路线的总数procedure init;读入数据，初始化 var i:integer;循环变量 temp:integer;临时变量 begin val(paramstr(1),n,temp);从命令行读入n n2:=n*n; fillchar(map,sizeof(map),255); for i:=0 to n+1 do begin map0,i:=0; mapi,0:=0; mapn+1,i:=0; mapi,n+1:=0; end; map1,1:=1; 以上程序段为对地图的初始化 fillchar(left,sizeof(left),4); for i:=2 to n-1 do begin left1,i:=3;leftn,i:=3; lefti,1:=3;lefti,n:=3; end; left1,1:=2;left1,n:=2;leftn,1:=3;leftn,n:=2; dec(left1,2);dec(left2,1); 以上程序段是对标志数组的初始化 s:=0;累加器清零 end;procedure change(x,y,dt:integer);给(x,y)相邻的四个格子的left标志值加上dt设标志时，dt取-1；回溯时，dt取1 var k:integer;循环变量 a,b:integer;临时坐标变量 begin for k:=1 to 4 do begin a:=x+deltak,1;b:=y+deltak,2; inc(lefta,b,dt); end; end;procedure expand(step,x,y:integer);搜索主过程：搜索第step步，扩展出发位置(x,y) var nx,ny:integer;Betsy的新位置 dir:byte;Betsy的移动方向 function able(x,y:integer):boolean;判断Betsy是否可以进入(x,y) begin able:=not(mapx,y-1)or(stepn2)and(x=n)and(y=1); end; function cut1:boolean;剪枝判断1 var i:integer;循环变量 a,b:integer;临时坐标变量 begin for i:=1 to 4 do begin a:=x+deltai,1;b:=y+deltai,2; if (mapa,b=-1)and(anx)or(bny)and(lefta,b=1) then begin cut1:=true; exit; end; end; cut1:=false; end; function cut2:boolean;剪枝判断2 var d1,d2:integer;相对于当前移动方向的左右两个方向 fx,fy:integer;Betsy由当前位置，沿原方向，再向前移动一步的位置 begin if (dir=2)or(dir=4) then begin d1:=1;d2:=3; end else begin d1:=2;d2:=4; end; fx:=nx+deltadir,1;fy:=ny+deltadir,2; if (mapfx,fy-1)and(mapnx+deltad1,1,ny+deltad1,2=-1) and(mapnx+deltad2,1,ny+deltad2,2=-1) then begin cut2:=true; exit; end; if (mapfx+deltad1,1,fy+deltad1,2-1)and(mapnx+deltad1,1,ny+deltad1,2=-1) and(mapfx,fy=-1) then begin cut2:=true; exit; end; if (mapfx+deltad2,1,fy+deltad2,2-1)and(mapnx+deltad2,1,ny+deltad2,2=-1) and(mapfx,fy=-1) then begin cut2:=true; exit; end; 以上程序段中的三个条件判断分别对应论文剪枝原理图中所列的三种情况 cut2:=false; end; beginExpand if (stepn2)and(x=n)and(y=1) then begin搜索到最底层,累加器加1 inc(s); exit; end; for dir:=1 to 4 do begin循环尝试4个移动方向 nx:=x+deltadir,1;ny:=y+deltadir,2; if able(nx,ny) then begin if cut1 then continue;调用剪枝判断1 if cut2 then continue;调用剪枝判断2 change(nx,ny,-1); mapnx,ny:=step; expand(step+1,nx,ny);递归调用下一层搜索 mapnx,ny:=-1; change(nx,ny,1); end; end; end;begin主程序 init;初始化 expand(2,1,1);调用搜索过程 writeln(The number of tours is ,s);输出结果end.二、“最少乘法次数”的程序（即附录中的程序6）：$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 65520,0,655360program LeastMultiply;IOI99集训队 论文例题2：最少乘法次数说明: 1.为了测试计时的方便,本程序从命令行读入n值。 2.程序结束后，在output.txt中给出执行乘法的方式，并给出总的乘法次数。 3.在搜索过程中，由于与动态规划结合，所以在没有搜索到底层的时候，就可以得到最优解的数列长度(但此时没有得到完整的最优幂次数列)，所以在搜索结束后，程序中调用formkeep过程在keep中生成完整的构造数列。 4.由于程序中的搜索过程生成的是最优幂次数列，而没有直接给出乘法的进行方式，所以在输出结果的过程output中，对其进行了转换。5.为了尽可能的提高程序的时间效率，程序中有几处细节上的优化，请参见程序内的注释。6.程序中，逻辑上相对独立的程序段用空行分开。const max=20;数列最大长度 maxr=2000;动态规划计数数组的最大长度(输入的n不能超过maxr的2倍) mp=100;预处理估价时,可以直接搜索处理的数的范围上限 power2:array0.12of integer= (1,2,4,8,16,32,64,128,256,512,1024,2048,4096); 2的方幂type atype=array0.maxof integer;用于记录构造的幂次数列的数组类型，0号元素记录数列长度var n:integer;读入的目标数字 time:array0.maxrof integer; 动态规划计数数组，timei表示在当前构造数列的基础上，组成数i至少需要的加数个数 range:integer;使用动态规划处理的范围：range=n/2 a:atype;搜索中记录数列 kp:atype;预处理估界时，记录结果数列的临时数组 keep:atype;记录最优结果数列的数组 best:integer;当前最优解 f:text;输出文件procedure init;初始化 var temp:integer;临时变量 begin val(paramstr(1),n,temp);从命令行读入n keep0:=1; keep1:=1; best:=maxint;最优数列长度的初值 assign(f,output.txt);连接输出文件 end;procedure search(n:integer;var best:integer;var keep:atype);搜索主过程搜索之前，给出的搜索目标为n； 在best中存放搜索前已经给出的优度下界； 在keep中存放初始优度下界对应的最优幂次数列。 搜索结束之后，在best中给出的是构造的最优幂次数列的长度,即最少乘法次数加1； 在keep中给出所构造的最优幂次数列。 var kn:integer;n所含的2的方幂的次数 i:integer;循环变量 function getk(num:integer):integer;求num所含的2的方幂次数,即论文中所设的k(num) var i:integer;循环变量 begin i:=0; while not odd(num) do begin num:=num shr 1; inc(i); end; getk:=i-1; end; procedure find(step:integer);递归搜索过程 var i:integer;循环变量 k:integer;本层搜索的循环范围上限 function ok(num:integer):boolean;判断数num能否在当前被构造出来 为了提高程序的效率，这里利用了动态规划的结果 var i,j:integer;循环变量 begin if num=range then begin待判断数num在n/2以内 ok:=(timenum=2);直接利用最少需要的加数是否为2来判断 exit; end; for i:=step-1 downto 1 do begin if ai+airange then p:=range; for i:=astep-1+1 to p do begin timei:=timei-astep-1+1;目标函数赋初值 for j:=step-2 downto 2 do决策枚举 if timei-aj+1timei then timei:=timei-aj+1; end; end; function h(num:integer):byte;最初的简单估价函数h var i:integer;循环计数变量 begin i:=0; while num=best then cut1:=true else cut1:=false; end; function cut2:boolean;使用改进的估价函数的剪枝判断 var pt:integer;k(astep)的值，即astep中所含的2的幂的次数 rest:integer;新构造的数列中，满足k(rest)=k(n)的数 i:integer;循环计数变量 begin if h(astep+astep-1)+step+1kn then rest:=astep-1 else if pt=kn then rest:=astep else rest:=maxint; 给rest赋初值，以防新构造的数列中的所有数的k值都小于k(n) i:=0; repeat astep+i+1:=astep+i shl 1; inc(i); if pt+i=kn then rest:=astep+i; until astep+in; dec(i); 以上程序段为构造数列的过程 if (n-astep+irest)and(step+i+2=best) then cut2:=true else cut2:=false;剪枝判断 end; beginFind if astep-1+astep-1=n then begin 数列中的当前最大数已经超过n/2，则直接引用动态规划的结果 if timen-astep-1+step-1best then begin判断出解 best:=timen-astep-1+step-1; keep:=a; end; exit; end; k:=astep-1+astep-1;计算astep的可选范围的上限 evltime;调用动态规划子过程 inc(a0); for i:=k downto astep-1+1 do if ok(i) then begin if in/2则直接引用动态规划的结果，所以最优结果数列的最后一 部分实际上并未得到，所以需要在本过程中将其补充完整。 这里还需要使用递归和回溯（实际上就是一个小规模的搜索），不过，由于动态规划给出的结 果表示的是从已有数列中，选出最少的数求和而得到n，所以对这些数是可以定序的。 var found:boolean;找到最优数列的标志 procedure check(from,left:integer);回溯法生成最优数列的最后一部分from表示当前层内循环的上界(用于定序)，left表示剩余的需要通过求和而得到的数 var i:integer;循环变量 begin if keep0=best then begin if left=0 then found:=true;找到最优数列 exit; end; inc(keep0); for i:=from downto 1 do循环枚举数列中的数 if keepi=left then begin keepkeep0:=keepkeep0-1+keepi; check(i,left-keepi);调用下一层搜索，但所使用的数不能再超过keepi(定序) if found then exit; end; dec(keep0); end; beginFromKeep found:=false; check(keep0,n-keepkeep0);调用搜索过程 end; beginSearch kn:=getk(n);计算k(n) time0:=0; time1:=1; a0:=1; a1:=1; range:=n div 2; 以上程序段为搜索前的初始化 find(2);调用搜索过程 formkeep;搜索结束后，在keep中生成完整的构造数列 end;function guess(n:integer):integer;递归方式实现的预处理估界说明： 1.子程序guess运行结束后，返回的值即为对n估价的结果；同时，在keep数组中得到对应的数列。 2.为了能够使估价尽可能准确，guess中同时考虑了两种分解策略，即使用了回溯结构。 3.由于每次递归调用guess，其最终结果都必须记入keep数组，所以每次guess运行都只操作keep数组的一部分，同时还要借助于kp,kpt等临时数组。 var num:integer;将n中的所有2的因子都提出后剩下的数 pfact:integer;表示num的素因子的变量 best:integer;向下调用时记录返回的估价值 b2:integer;记录num中的2的因子的数目 s:integer;对n的估价步数 i:integer;循环变量 sq:integer;num的平方根的整数部分，分解素因子时作为上界 s1,k2,k:integer;临时变量 kpt:atype;临时记录最优结果数列 begin num:=n; b2:=0; while not odd(num) do begin num:=num div 2; inc(b2); inc(keep0); keepkeep0:=power2b2; end; s:=b2+1; k2:=keep0; 以上程序段的作用是将n中所含的2的因子全部提出，剩下的部分即num if num=mp then begin如果num足够小(小于等于mp)，则直接调用搜索过程处理 best:=maxint; search(num,best,kp);对n调用搜索过程，得到的数列存放在kp中 inc(s,best-1); for i:=2 to best do keepi+keep0-1:=kpi; inc(keep0,best-1); end else begin使用估价方法处理 k:=keep0; best:=guess(num-1);递归调用guess keepkeep0+1:=keepkeep0+1; inc(keep0); inc(s,best); 以上程序段为估价的第一种策略：将num减1后，对num-1进行估价 sq:=trunc(sqrt(num); pfact:=3; while (pfact0) do inc(pfact,2);