算法合集之平衡规划

《算法合集之平衡规划》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、浅析一类平衡思想在信息学竞赛中的应用平衡规划——浅析一类平衡思想在信息学竞赛中的应用福建省福州市第八中学郑暾【目录】l摘要2l关键字2l正文2u引言2u应用平衡思想的几类问题3l经典算法的非典型实现3n例题一、警卫安排问题3n例题二、Jackpot6l效果优秀的非完美算法8n例题三、追捕盗贼8l复杂问题的简单化构造12n例题四、数列维护12n例题五、树的维护14u总结17l感谢18l参考文献18l附录1826浅析一类平衡思想在信息学竞赛中的应用【摘要】应用计算机解题的核心是算法设计。但算法设计方面涉及的领域十分丰富。我们不能奢求

2、能完美地应用所有的算法，所以我们关注的通常是如何合理运用已学知识，并在所掌握算法间构建一种平衡，在限定的时间内尽可能多地解决问题。本文尝试讨论一类平衡思想应用于算法构造、算法实现的模式。【关键字】平衡思想、平衡点、时空效率、编程复杂度【正文】一、引言平衡通常指物体或系统的一种状态。处于平衡状态的物体或系统，除非受到外界的影响，它本身不会有任何自发的变化。多种状态达到平衡通常是我们所追求的目标。平衡思想是一种奇妙的思想，它的应用十分广泛。在算法设计，数据结构设计甚至程序设计中都能发现它的身影。计算机竞赛就是一场博弈，寻找这场博弈中

3、的平衡点，合理应用平衡思想辅助算法设计与程序实现，往往能起到化腐朽为神奇的作用。在信息学竞赛中，平衡思想通常有以下几个方面的运用：1、博弈问题。有许多博弈类问题都可以转化成寻找平衡点的问题。2、数据结构的构建。每种数据结构都能以优秀的性能支持某些操作，合理选择应用数据结构，往往能通过略微提高一些操作的复杂度，降低大多数操作的复杂度，在不同操作的效率之间构建一种平衡，以达到优化的目的。3、时间效率vs空间效率。这类问题是我们经常遇到的问题。这类问题通常有这样的特性，我们能找到时间效率（或空间效率）十分优秀的算法，但代价是空间效率（

4、或时间效率）极端低下。如何合理设计算法，组织数据，平衡二者的关系是解决这类问题的重点。4、时空效率vs26浅析一类平衡思想在信息学竞赛中的应用其他。如果面对难题难以设计出优美的算法，又或者设计了优秀效率的算法，却无法实现或难以实现，就会出现非常尴尬的局面。合理应用平衡规划解决这类问题，往往能收到意想不到的效果。而这类问题也正是本文所要重点探讨的问题。下文将试图论述运用平衡思想解决这类问题中的三种常见模式：经典算法的非典型实现，效果优秀的非完美算法，以及复杂问题的简单化构造。二、应用平衡思想的几类问题1、经典算法的非典型实现。大多

5、数经典算法通常是为很多人所熟知，并且能够熟悉运用。经典算法通常也有很多不同的实现方法。例如拓扑排序，如果数据范围比较大，通常使用算法复杂度为O(n)的程序，但是如果范围比较小，一个不超过10行的的程序可以使代码看起来更为简洁。而不同的实现方法中，哪怕只是细微的不同，实现后的性能与效率也可能有很大的差别。更进一步，有些算法虽然堪称经典，但是无论是思考复杂度还是实现复杂度都相对颇高，在考场上来说，使用一些相对简单实用的方法无疑是一种不错的选择。例题一、警卫安排问题(ural1099)题目描述：给定若干警卫间搭档关系，要求成对给警卫安

6、排保卫工作，求能够安排警卫的最大值。（警卫人数不超过222）初步分析：题目描述很简单，稍加分析后我们很容易看出来，这题的本质其实是要求我们求出任意图的最大匹配。任意图的最大匹配的经典算法是应用带花匈牙利树，时间复杂度为，对付这道题来说是绰绰有余的。但是带花树本身比较复杂，思维复杂度与编程复杂度较高，而且实现起来很容易退化，考场上有限的时间内难以完成。于是我们尝试考虑替代算法予以解决。解法分析：26浅析一类平衡思想在信息学竞赛中的应用解决二分图最大匹配的时候，主要过程是不断寻找交错增广树来调整。那么这么做对于任意图是否可行？答案是

7、否定的。考察右边这张图（图一）。图中粗线表示当前状态下已匹配边，虚线表示未匹配边。若我们当前找的增广树如图二所示，那么我们就无法找到一条增广路。但实际上，存这样的一条增广路：。为了找到增广路，我们可以采用搜索的方法，但这样寻找增广路复杂度过高。3452167图二34521678图一我们注意到，采用调整增广轨的方法，如果一个点之前已经被匹配到，则之后无论如何调整，这个点始终能被匹配到。因此，对于一个待匹配点，是否能找到一条以它为起点的增广路是优化解的关键。而是否能找到一棵增广树又很大程度上依赖于之前找寻的情况，若要设计数据使得无法

8、找到增广树通常又依赖于特定的扩展顺序。这启发我们采用随机扩展顺序的方法来尽量避免形成类似图一的特殊局面。笔者的程序中生成了两个随机序列，一个作为点的初次访问序，一个作为点的拓展顺序，然后直接使用一开始所说的寻找交错树的方法来扩展。同时，采用多次随机运行的方法提高