《算法合集之由图论问的题目浅析某算法优化》由会员分享，可在线阅读，更多相关《算法合集之由图论问的题目浅析某算法优化（20页珍藏版）》请在金锄头文库上搜索。
1、word由图论问题浅析算法优化武钢三中 贾由 【摘要】论文以图论问题为对象、以算法优化为主题、以分类和举例为根本模式进展了一系列探讨。第一局部引言简单地介绍了图论与信息学竞赛的关系；第二局部分析了算法优化的根本途径：寻找特别之处；第三局部从算法的纠错入手，详细讨论其中的方法，进一步展示了发现问题的特殊点对算法优化的推动作用。【关键字】图论 算法优化 错误分析【正文】一、引言图论是一个十分有趣而且与信息学竞赛联系严密的数学分支。随着图论问题的日渐增多，一些经典图论模型与它们的相关算法已成为竞赛中不可或缺的知识。与此同时，题目也越来越注重模型的转换与算法的优化。这意味着在将知识转变为分数的过程中，
2、我们需要做出更多的努力。本文以其中的算法优化为主题，尝试了一些相关的归纳与讨论。另外，由于黑箱测试的缘故，我们所体验到的信息学可以说是一个以结果论成败的学科。这是很好的，因为结果是对历史的总结。但无论如何，对于一次以优化为主题的讨论来说，得到的最优算法仅仅是用来证明我们的优化过程是切实而有效的。二、寻找特别之处优化的根本途径2.1 介绍每一个让算法更加漂亮的改良都可以称为优化。不过在整体考虑一个问题时，优化的过程应该包括从原始算法到一个优秀算法当中的所有改良。这通常是一个逐步发现并利用问题的特殊之处、使算法更有针对性的过程。做好优化的根本在于找出题目的特别之处。这是一个广泛的想法，没什么步骤和
3、诀窍可言。解决具体问题时，我们只能靠广泛的优化经验、充足的耐心以与一局部的灵感因素。关于经验，之前的几篇论文已经分别就一些有共同特征的题目介绍了深入挖掘信息的具体过程。这一章不再深入探讨某类问题，而是通过一个经典算法对“寻找特别之处作出解释。2.2 例题例 二分图的最大匹配 题目来源：经典问题。图的匹配指图中任何两条边都没有共同顶点的子图，二分图最大匹配问题旨在求出二分图中边数最多的一个匹配。求解这个问题最根本的方法是将它转换成一个网络流模型：为了方便表示，我们将二分图的两个顶点集合成为A和B。在图中参加源点和汇点，从源点向A中的每个点引一条边，容量为1；从B中的每个点向汇点引一条容量同样为1
4、的边。然后将原图中的边作为有向边添加进来，由A指向B，容量为1。新图中用容量限制了每个点最多只能被一条边覆盖、每条边只能被记一次。容易看出，这个图的最大流与最大匹配中的边数相等。通过最大流算法，我们同样可以得到选边的具体方案。最显然的一个优化是不记录容量，所有边的容量都是一。其次，这个网络中的可增广链很特别，它一定由源点开始，在点集A和点集B之间做假设干次往返，再由B到达汇点的。搜索时可以不考虑第一条与源点连接的边和最后一条与汇点连接的边，直接从点集A中的一个未匹配点开始到点集B中的一个未匹配点完毕。可以想象，在广搜的目标路径中减少两条边对于需要扩展的结点数的影响是巨大的。这就是匈牙利算法的根
5、本思想。根本的网络流算法与匈牙利算法的时间复杂度其实没有区别 都是O(M*N)，更快的算法可以参考2。，但是后者在所需空间、编写难度以与实际的运行时间上都拥有绝对的优势。几乎可以肯定匈牙利算法最初不是由上面这样的优化得到的，但这两种优化手段在网络流算法的设计中是很实用的：根据图的特殊性简化存储方式、量身定制搜索可增广链的方法。例 牧场规划 题目来源：2003年某某省省选。小可可的好朋友Sealock最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验。他以网格的方式，非常规整地把牧场分割成M*N个矩形区域(M*N5000)，由于各个区域中地水面、沼泽面积各不一样，因此各区域地实际可种植面积也
6、各不一样，区域(i,j)地可种面积使A(i,j)。每个区域种最多只能种植一个品种地花生。可种植面积为零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做相邻。小可可准备帮助Sealock规划一下如何选择种植区域，才能使得实际可种植面积总和最大。对应选择方案与网络的割建立方案与网络的割之间一一对应关系的方法在4中曾有所描述，我们根据这道题再回顾一遍。S T图1 建立网络将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通过对原图的黑白染色
7、，可以把其中的一局部称为白点、另一局部称为黑点。由二分图建立网络：参加源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。方案对应的割：将方案中所选的白点和未选的黑点再加上源点划为一个集合，其它点划到另一个几何，就得到了一个割。直接把这个过程反过来，我们很容易由割得到一个方案。在这个对应中：一、不合法方案对应的割均为正无穷；二、在合法方案对应的割中，割上的点代表了方案没有取到的边。所以当割的容量最小时、方案选取的面积最大，而根据最大流最小割定理，我们可以通过求网络最大流
8、得到它的最小割。广搜可增广链这同样是由二分图转换来的网络，但是边的容量一般化了。我们仍然可以不搜索首尾两条边，不同的是以某一个“新源点原可增广链上的第二个点为起点的广搜可能要进展屡次，次数最多等于源点到它的边的容量；同理，一个“新汇点可以容纳多个可增广链。另外，为白点和黑点分别设计扩展过程也可以大大提高算法的效率。三、改良错误算法更灵活的优化3.1 介绍我们常说的算法优化有四个方向：时间复杂度的优化、空间复杂度的优化、编写难度的优化以与思维难度的优化。但是正如标题所表达的，这一局部的内容是如何提高算法的正确率。纠错也算是优化吗？如果你也有同样的疑问，那你一定是想到代码的查错上去了。提高算法的正
9、确率当然是对算法的优化。甚至，算法的错误常常也是由于对题目信息的不充分利用导致的，只不过除此之外还有很多别的原因，我们一会儿就会进一步分析到它们。应对错误需要有一套方法。首先，我们总会希望错误不要出现，比如思维严谨一点、看问题全面一点。当问题不可防止地出现时，处理方法一定要视情况而定：如果考试的时间已经不多，可以通过一些简单的处理适当地提高正确率；如果还不紧X，就应该仔细地分析分析错误；实在无能为力的话，放弃已有的算法另寻他解也是一个明智的选择。应急时的简单处理虽是无奈之举，却也值得一提。最直接的方法是参加额外的判断过程，尽量把想到的反例都包括进去，但在问题比拟复杂时，这通常是一件让人头疼而且
10、收获不大的工作。另一方面，随机化加重复求解的处理操作简单、效果惊人，更能为人们所承受。对于最优化问题，取屡次运算得到的最优解即可；判定性问题稍麻烦些，原算法还得满足下面两个前提中的至少一个：一、它的正确率高于50%，于是我们可以采用得出次数较多的那个结果；二、它可以准确判断“是、“否中的一个方面，假设被判断为“是时一定正确，那么就把剩下得到的全是“否的输入判为“否。应对具体错误时还能找出许多小技巧，这儿就不再列举了。下面我将通过分类举例来讲述我对如何仔细分析错误的理解。导致我们设计出一个错误算法的原因大致有三类：一、误解模型的性质。其中的模型指所有的数学模型，之前所说的信息利用不充分也属于这一
11、类。这是一个主流原因，更深入的讨论见下一节中古老的渔网问题。二、猜测错误。不知如何将模型与算法联系起来时，我们常提倡大胆去猜测。但猜测难免出错，如何处理这类错误至关重要。在奶牛航班的分析过程中出现了这个问题。三、不了解算法细节。需要适当改良一个经典算法时，如果我们对这个算法的掌握不够透彻，很容易出现问题。下面的例子，可疑的斑点，不是图论问题，但很有代表性，它主要涉与KMP算法。3.2 例题例 奶牛航班 题目来源：USACO 2005年十月竞赛，Flying Right。约翰的奶牛们开通了一条飞机航线，专门为奶牛服务。每天早上，她们沿着密歇根湖的西岸，从线路的最北端出发飞到最南端，全程经过N个机
12、场包括头尾两个。到了下午，她们又会沿着同样的路线飞回最北端。每天都会有数目不同的K群奶牛要求乘坐飞机，一群牛会在某一个机场等待，并希望飞到另外一个特定的机场。飞机上只能同时容纳C头奶牛乘客，航班的负责牛希望知道在这一天中她们最多可以满足多少头奶牛的要求。飞机可以只将一群牛中的一局部带到目的地。约定：1N10,000，1K50,000，1C100。初步分析飞机的一去一回很明显是两个一样的问题。而且如果一头奶牛非要绕一次折返点的话，它会在原来的根底上再多在飞机上坐一段路，这并不划算。于是这两个子问题互不干扰，可以单独处理，我们接下来只需考虑一个方向上的事情。还有一个问题是我们不必多考虑的，那就是飞
13、机在途中的哪些机场着陆。我们可以认为它在每个机场都做停留这并不耽误什么，或者干脆把它当作一辆长途汽车。题目给人的第一感觉是动态规划：将机场看作点、牛的飞行路线看作边，那么算法将为每个点记录下从起点飞到这里最多能服务多少头奶牛，并通过边进展状态转移。联系到这一题的实际情况，我们会很快发现这是很荒谬的。在这样的动态规划得到的方案中，肯定不会出现有重叠关系的边，但是我们的飞机完全有可能同时满足两头路线重叠的牛的飞行要求。看来这不是一个常规的动态规划题，我们只好先把动态规划的思路搁在一边。最小费用流模型数据规模的约定提醒了我们要好好利用飞机上座位不多最多100个这个条件。一个座位一个座位地考虑，最直接
14、的方法莫过于网络流了。容量网络的建立并不复杂：仍然以机场为点，牛群的飞行线路为边。每条边的容量赋为牛群中的牛数Mi，权值都是1。代表这个牛群最多可以“容纳Mi个座位，每当一个座位选择了这个群，就相应的得到1点权值。再从每个点除最后一个向它的后一个点连一条容量无穷大、权值为0的边，代表座位在这一段可以是空闲的。总的来说，模型中的一个单位流就代表了一个座位。为了防止最大费用流这个怪异的名词，在实现时把权值改为-1即可。最小费用流的算法中，用Bellman-Ford算法求一次最短路需要O(K*N)，最大流量等于座位数C，所以算法的总复杂度是O(K*N*C)，无法承受题目给出的数据规模。参加贪心思想给
15、这个特殊的图套上最小费用流算法确实有点浪费，时间复杂度高是必然的结果。那么如何利用这些特殊点优化算法呢？费用流算法中，每次找到一条最短路径权和最小的路径进展扩展。扩展时为了可能的改动，我们会给扩展边的反向边扩大容量，这个处理解决了后效性的问题。仔细想想，在这个问题中或许根本就不存在后效性，我们能不能放弃对反向边的处理？不处理反向边使算法有了本质上的改变。它所做的相当于：逐一安排每一个座位，使每个座位在当前情况下全程载牛数最大。对此，我们不必再用B-F算法，动态规划可以在O(K)时间内得出答案。这样，总时间复杂度降到了O(K*C)，足以满足题目所给的数据规模。但是这个算法存在反例：图2 反例的图示起点终点路线A路线B路线C路线D如图2，假设这4条路线中都只有1头牛，那么一架配有两个空位的飞机就可以为所有的4头牛服务。但是以上的贪心算法很有可能会为第一个座位安排A、D中的两头牛，因为不存在一个3头牛的安排方案。这样一来，第二个座位无论如何都只能将一头牛带到目的地了。算法确实只能保证结果是很不错的，不一定最优。即使这样，这仍然是一个正确率较高的算法。在实际测试中，它通过了官方16组测试数据中的15组。深入判断边与边的关系继续分析上一个
