国家集训队论文杨培论文

IOI2000集训队论文：非最优化算法初探1非最优化算法初探北京四中杨培【关键字】贪心、随机化、最优化、局部搜索【摘要】本文介绍了非最优化算法的基本理论，总结了贪心算法的适用条件和部分使用技巧。并在此基础上介绍了禁忌搜索算法及其应用实例。指出了随机化方法的若干适用范围。总结了非最优化算法的优越性。概论现代信息学问题分为两类：一类是存在有效算法的所谓P类问题，另一类是目前尚未找到有效算法的所谓NPC问题。为了解决后一类问题，我们引进了非最优化算法的概念。本节将对NPC的概念和提出非最优化算法的必要性等问题进行阐述。一．引言信息学是20世纪后半叶诞生的一门崭新的学科。数学、物理学、化学等学科的诞生是建立在一些科学家纯粹兴趣的研究基础上，其初期，科学家们的工作是纯理论性的。而信息学与他们的最大不同之处在于：自诞生之日起，它就与实际应用紧密地结合在一起了。每一个算法的提出，都有它广泛的应用背景。国际信息学奥林匹克竞赛（IOI）自1989年创办以来，已经举行了11届，其间题目的风格经过了一个曲折的发展过程。但我们应该看到，总的趋势是：向实际靠拢，每个题目都有一个实际背景，考察选手从实际问题中抽象出数学模型的能力。但是，在众多的实际问题中，真正存在有效算法的P问题是少数，而大多数也是困扰人们的是NPC问题。在没有有效算法的情况下，要解决NPC问题，只能用一些非最优化算法在可接受的时间复杂度内求得一些近似解。因此为了考察选手在解决这方面题目的能力，在近年来的竞赛中，分段计分等非正常计分的题目逐渐增多。另外，在竞赛过程中，对于一些暂时想不出有效算法或实现有效算法比较困难的题目，使用非最优化算法可以得到不错的效果。（见表一）由上面两个原因可以看出，今后非最优化算法还是大有用武之地的，对非最优化算法的研究、总结是必要的。IOI2000集训队论文：非最优化算法初探2年份比赛题目较好的算法题目类型1997IOI火星探测车贪心最大流问题地图标签贪心/随机化NPC问题集装箱概率+贪心随机规划千足虫构造近似算法HEX游戏构造近似算法博弈1998NOI并行计算贪心+随机化大规模搜索1999冬令营迷宫改造贪心+随机化动态规划NOI01串随机化最长路径国家队作业保卫地球——邵铮随机化NPC问题IOI地下城市贪心均分纸牌贪心/随机化表格1应用非最优算法效果较好的题目二．基本概念可行性问题和最优性问题的关系应用非最优化算法的题目可简单的分为两类：可行性问题和最优性问题。虽然在选择具体算法时，要对这两种问题加以区分、分别对待，但这两种问题在本质上是统一的，都可以划归为如下的判定问题。定义1.2.1：如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题。可行性问题可直接转化为“是否存在解”的判定问题。而对于最优性问题，可转化为若干个“是否存在比当前解更优的解”的判定问题。从这种意义上讲，可行性问题最优性问题，我们只需重点研究后者。临域概念定义1.2.2：对于一个最优性问题，它的所有可行解的集合D上的一个映射：N：S∈D→N(S)∈2^D称为一个临域映射，其中2^D表示D的所有子集组成的集合，N(S)称为S的临域，S’∈N(S)称为S的一个邻居。事实上，传统的简单算法如爬山法、贪心法都是建立在对临域的搜索基础上的。显然，上面的方法只能得到问题局部最优解，不能保证得到全局最优解。而非最优算法的目的之一就是用较小的代价跳出局部最优点，从而尽可能接近全局最优点。三．非最优化算法分类非最优化算法可简单的分为两类：一步算法和改进算法。IOI2000集训队论文：非最优化算法初探3一步算法该算法的特点是：不在两个可行解之间选择，在未终止的迭代中，又可能不是一个可行解，算法结束时得到一个可行解。这种算法的时间复杂度是容易接受的。该算法的典型例子是火星探测器问题的贪心算法，每一辆车选一条可装矿石最多的路线，直到分配完所有车的路线。该算法没有在两个可行解之间比较选择，算法结束时得到一可行解。应当注意的是：在解决可行性问题的时候，在算法运行中可能发现无法得到最终的一可行解，这就需要进行简单的回溯或者干脆推翻了重来（如果使用了随机化方法）。例子是NOI’99的“01串”问题。改进算法改进算法的迭代过程是从一个可行解到另一个可行解，通常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直到满足一定的要求为止。该算法一般应用于最优性问题。例如局部搜索算法或爬山法，都是改进算法的一种。另外，在使用随机化方法时，例如迷宫改造，需要反复随机求得可行解，最后选出其中最优的。这也可以说是一种改进算法。四．非最优化算法的性能分析虽然非最优化算法由许多优点，但最大的缺陷是不能保证得到全局最优解，所以对算法的评价就显得十分重要。评价一个非最优化算法需要两条标准：一是看它的解与最优解的接近性，这是根本条件。如果算法得出的解与最优解的差距较大，按目前已有的计分方法，得分会相当低，更不要说应用在求最优解的题目上了。其二是考察算法的稳定性，这也是十分必要的。下面介绍了几种测试算法的简单方法。最坏情况分析对于任何算法，都要考察它在最坏情况的时间复杂度和空间复杂度，但对于非最优化算法，还需要考察它的最坏情况解的效果。通过最坏情况分析来评价算法的效果，其指标是计算解的值同最优解的值之间的差距，差距越小说明算法越好。但是，最坏情况分析不能全面地评价算法的好坏，某些算法在小规模时效果很差，但不能说这个算法一定很差。（例如，集装箱问题中钱文杰的算法）另外，找到一个算法的最坏情况并不容易，它需要很多数学技巧，这也限制了这种分析方法的应用。概率分析概率统计分析的方法是从理论上考虑的，它假设实例的数据服从一定的概率分布。在这个数据概率分布的假设下，研究其算法或解的平均效果。这种分析方法对于估计随机化算法的可行性是十分重要的。例如，对于随机化的素数判定算IOI2000集训队论文：非最优化算法初探4法，概率分析为算法的稳定性提供了理论基础。但是概率分析是一种理论分析方法，它需要对问题本身有较深入的理解，并且掌握概率模型的建立和概率理论，要求有较强的数学基础。对于一些较复杂的问题，在考场上无法完成分析，因此，它有较大的局限性。大规模计算分析大规模计算分析就是常说的用测试数据测试的方法。它可对多个算法进行评价，比较分析不同算法的效果。可根据各个算法的计算结果，采用简单或统计的方法比较不同算法的性能，而不需要预先得到每个实例的最优解。用这种方法分析算法时，需要产生一些具有代表性的测试数据。关于如何使测试数据全面、准确，请参阅杨帆的《准确性、全面性、美观性——测试数据设计中的三要素》一文。非最优化算法初探一．贪心算法1．概念贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。这时就得到了问题的一个解，但不能保证求得的最后解是最优的。在改进算法中，贪心算法演化为爬山法。2．特点及使用范围贪心算法的优点在于时间复杂度极底。贪心算法与其他最优化算法的区别在于：它具有不可后撤性，可以有后效性，一般情况下不满足最优化原理。贪心算法的特点就决定了它的适用范围，他一般不适用于解决可行性问题，仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是：当前的策略选择後，不会或极少使后面出现无解的情况。另外，对于近年来出现的交互性题目，贪心算法是一个较好的选择。这是因为，在题目中，一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提供较优的初始界值。3．使用贪心算法的技巧贪心与最优化算法的结合尽管贪心算法有一定的优越性，但它毕竟在一般情况下得不到最优解。因此，为了尽量减小贪心算法带来的副作用，使得最后得到的解更接近最优解，应该在算法尽可能多的地方使用有效的最优化算法（如动态规划）。例如，在火星探测器这道题中，当我们找不到有效的算法使探测器之间互相帮助，综合分配任务时，就只能使用贪心算法。让每辆探测器独自运行找一条可使自己得到矿石最多的路线。在这一过程中，我们可以使用动态规划算法来保证每辆探测器走的是当前最优的路线。虽然每个局部的最优解加在一起不等于全局IOI2000集训队论文：非最优化算法初探5最优解，但也很大程度上弥补了全局上使用贪心算法的弊端。（详见文献[1]Vol.1No.1）而在邵铮的《保卫地球》一题中，对于用有限个导弹将舰队的战斗力降至最低的子问题，使用了贪心的算法。但在分配打击每个舰队的导弹数时，使用了动态规划算法。这样在局部使用贪心，在总体上用“最优”的算法，得到的效果也适当好的。（详见文献[7]邵铮的解题报告）贪心算法中权值的选择贪心算法的核心是在所选择的策略中，选一个权值最优的策略作为当前策略。因此贪心算法的好坏主要决定于权值的确定。权值的确定算法应遵循两个原则：1．尽可能的包含一些选择这一策略後对整个问题的影响的信息。显然，如果包含的信息越多，权值越接近于这个策略的真正价值，这使得到的最后结果越接近最优解。如果权值包含了选择这一策略後对整个问题的全部影响，则算法退化为搜索算法。2．计算权值的计算复杂度不能太高，否则将丧失贪心算法的唯一优点。可以看出，以上两个标准是矛盾的，我们的目标就是在这对矛盾中找到平衡点。4．贪心算法的改进贪心算法的缺点在于解的效果比较差，而最大优势在于极低的时间复杂度，而且往往时间复杂度远远低于题目的限制。那么，我们为什么不再花一部分时间来提高目标解的效果呢？这就是对贪心算法改进必要性，在这里我们讨论一种贪心算法与搜索策略相结合的算法。局部搜索算法首先回顾一下爬山算法，即纯粹的局部搜索策略。算法2.4.1局部搜索算法：STEP1：选定一个初始可行解0x；记录当前最优解0:xxbest，令)(bestxNP；STEP2：当P时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从)(bestxN中选一集合S，得到S中的最优解nowx；若)()(bestnowxfxf，则nowbestxx:，)(:bestxNP；否则，SPP:；重复STEP2。在局部搜索算法中，STEP1的初始可行解可采用贪心算法或其他算法求得。这种算法的效果取决于S的大小。禁忌搜索的一个例子下面我们引入一种禁忌搜索的算法来对局部搜索算法进行改进，它的一个重要思想是标记已得到的局部最优解，并在进一步的迭代中避开这些局部最优解。IOI2000集训队论文：非最优化算法初探6首先看一个例子。例2.4：NOI99“01串”问题。先定义一个目标函数)(xf：),(0ixg为解x中从第i个字符开始连续L0个字符中“0”的个数。),(1ixg为解x中从第i个字符开始连续L1个字符中“1”的个数。1111111111111110000000000010),(),(),(0),(),(),(),(),(0),(),()(LNiLNiAixgixgABixgABixgBixgAixgixgABixgABixgBixgxf显然，我们的任务是求一个解x’，使得0)'(xf。在求解的过程中，目标是寻找f(x)尽可能小的解“x”。用一个实例求解的过程来举例：N=10,A0=1,B0=2,L0=3,A1=1,B1=1,L1=3。假设：初始解)1111111111(0x，临域映射为对某一个位置进行取反操作，目标值24)(0xf。第1步：候选集操作12345678910评价值222018★18181818182022禁忌长度0000000000此处评价值为目标值。从候选集中选一个最好的操作——对位置3取反，用★标记入选的操作。目标值由24下降为18，有所改善。第2步：)1101111111(1x，18)(1xf操作12345678910评价值171624T141312★12121416禁忌长度0030000000由于第1步中选择了对位置3取反，于是，我