算法合集之《由图论问题浅析算法优化》

《算法合集之《由图论问题浅析算法优化》》由会员分享，可在线阅读，更多相关《算法合集之《由图论问题浅析算法优化》（20页珍藏版）》请在金锄头文库上搜索。

1、2006 年全国信息学冬令营讲座 第 1 页 共 20 页 由图论问题浅析算法优化 武钢三中 贾由 【摘要】 论文以图论问题为对象、以算法优化为主题、以分类和举例为基本模式进 行了一系列探讨。第一部分引言简单地介绍了图论与信息学竞赛的关系；第二 部分分析了算法优化的根本途径：寻找特别之处；第三部分从算法的纠错入手， 详细讨论其中的方法，进一步展示了发现问题的特殊点对算法优化的推动作用。 【关键字】 图论 算法优化 错误分析 【正文】 一、引言 图论是一个十分有趣而且与信息学竞赛联系紧密的数学分支。随着图论问题的日渐增 多，一些经典图论模型与它们的相关算法已成为竞赛中不可或缺的知识。与此同时，题

2、目 也越来越注重模型的转换与算法的优化。这意味着在将知识转变为分数的过程中，我们需 要做出更多的努力。本文以其中的算法优化为主题，尝试了一些相关的归纳与讨论。 另外，由于黑箱测试的缘故，我们所体验到的信息学可以说是一个以结果论成败的学 科。这是很好的，因为结果是对历史的总结。但无论如何，对于一次以优化为主题的讨论 来说，得到的最优算法仅仅是用来证明我们的优化过程是切实而有效的。 二、寻找特别之处优化的根本途径 2.1 介绍 每一个让算法更加漂亮的改进都可以称为优化。不过在整体考虑一个问题时，优化的 过程应该包括从原始算法到一个优秀算法当中的所有改进。这通常是一个逐步发现并利用 问题的特殊之处、

3、使算法更有针对性的过程。 做好优化的根本在于找出题目的特别之处。这是一个宽泛的想法，没什么步骤和诀窍 可言。解决具体问题时，我们只能靠广泛的优化经验、充足的耐心以及一部分的灵感因素。 关于经验，之前的几篇论文已经分别就一些有共同特征的题目介绍了深入挖掘信息的具体 过程。这一章不再深入探讨某类问题，而是通过一个经典算法对“寻找特别之处”作出解 释。2006 年全国信息学冬令营讲座 第 2 页 共 20 页 2.2 例题 例 二分图的最大匹配 1 图的匹配指图中任何两条边都没有共同顶点的子图，二分图最大匹配问题旨在求出二 分图中边数最多的一个匹配。求解这个问题最基本的方法是将它转换成一个网络流模型

4、： 为了方便叙述，我们将二分图的两个顶点集合成为A 和B。在图中加入源点和汇点， 从源点向A 中的每个点引一条边，容量为1；从B 中的每个点向汇点引一条容量同样为1 的边。然后将原图中的边作为有向边添加进来，由A 指向B，容量为1。新图中用容量限 制了每个点最多只能被一条边覆盖、每条边只能被记一次。容易看出，这个图的最大流与 最大匹配中的边数相等。通过最大流算法，我们同样可以得到选边的具体方案。 最显然的一个优化是不记录容量，所有边的容量都是一。其次，这个网络中的可增广 链很特别，它一定由源点开始，在点集A 和点集B 之间做若干次往返，再由B 到达汇点的。 搜索时可以不考虑第一条与源点连接的边

5、和最后一条与汇点连接的边，直接从点集A 中的 一个未匹配点开始到点集B 中的一个未匹配点结束。可以想象，在广搜的目标路径中减少 两条边对于需要扩展的结点数的影响是巨大的。这就是匈牙利算法的基本思想。 基本的网络流算法与匈牙利算法的时间复杂度其实没有区别 2 ，但是后者在所需空间、 编写难度以及实际的运行时间上都拥有绝对的优势。 几乎可以肯定匈牙利算法最初不是由上面这样的优化得到的，但这两种优化手段在网 络流算法的设计中是很实用的：根据图的特殊性简化存储方式、量身定制搜索可增广链的 方法。 例 牧场规划 3 小可可的好朋友Sealock 最喜欢吃花生了，于是借用了小可可的牧场从事花生选种 试验。

6、他以网格的方式，非常规整地把牧场分割成M*N 个矩形区域(M*N5000)，由于 各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知 区域(i,j)地可种面积使A(i,j)。 每个区域种最多只能种植一个品种地花生。可种植面积为零地区域不能被选择用来从 事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区 域都不可以同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个 区域不算做相邻。 小可可准备帮助Sealock 规划一下如何选择种植区域，才能使得实际可种植面积总 和最大。 对应选择方案与网络的割 建立方案与网络的割之间一一

7、对应关系的方法在4中曾有所描述，我们根据这道题 再回顾一遍。 1题目来源：经典问题。 2都是O(M*N)，更快的算法可以参考2。 3题目来源：2003 年安徽省省选。2006 年全国信息学冬令营讲座 第 3 页 共 20 页 S T 图1 建立网络 将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通 过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由二分图建立 网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从 每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边， 由白点指向黑点，容量为正无穷。

8、方案对应的割：将方案中所选的白点和未选的黑点再加上源点划为一个集合，其它点 划到另一个几何，就得到了一个割。直接把这个过程反过来，我们很容易由割得到一个方 案。在这个对应中：一、不合法方案对应的割均为正无穷；二、在合法方案对应的割中， 割上的点代表了方案没有取到的边。所以当割的容量最小时、方案选取的面积最大，而根 据最大流最小割定理，我们可以通过求网络最大流得到它的最小割。 广搜可增广链 这同样是由二分图转换来的网络，但是边的容量一般化了。我们仍然可以不搜索首尾 两条边，不同的是以某一个“新源点” （原可增广链上的第二个点）为起点的广搜可能要进 行多次，次数最多等于源点到它的边的容量；同理，一

9、个“新汇点”可以容纳多个可增广 链。另外，为白点和黑点分别设计扩展过程也可以大大提高算法的效率。 三、改进错误算法更灵活的优化 3.1 介绍 我们常说的算法优化有四个方向：时间复杂度的优化、空间复杂度的优化、编写难度 的优化以及思维难度的优化。但是正如标题所表达的，这一部分的内容是如何提高算法的 正确率。 纠错也算是优化吗？如果你也有同样的疑问，那你一定是想到代码的查错上去了。提 高算法的正确率当然是对算法的优化。甚至，算法的错误常常也是由于对题目信息的不充 分利用导致的，只不过除此之外还有很多别的原因，我们一会儿就会进一步分析到它们。 应对错误需要有一套方法。首先，我们总会希望错误不要出现，

10、比如思维严谨一点、 看问题全面一点。当问题不可避免地出现时，处理方法一定要视情况而定：如果考试的时 间已经不多，可以通过一些简单的处理适当地提高正确率；如果还不紧张，就应该仔细地 分析分析错误；实在无能为力的话，放弃已有的算法另寻他解也是一个明智的选择。2006 年全国信息学冬令营讲座 第 4 页 共 20 页 应急时的简单处理虽是无奈之举，却也值得一提。最直接的办法是加入额外的判断过 程，尽量把想到的反例都包括进去，但在问题比较复杂时，这通常是一件让人头疼而且收 获不大的工作。另一方面，随机化加重复求解的处理操作简单、效果惊人，更能为人们所 接受。对于最优化问题，取多次运算得到的最优解即可；

11、判定性问题稍麻烦些，原算法还 得满足下面两个前提中的至少一个：一、它的正确率高于50%，于是我们可以采用得出次 数较多的那个结果；二、它可以准确判断“是” 、 “否”中的一个方面，假如被判断为“是” 时一定正确，那么就把剩下得到的全是“否”的输入判为“否” 。应对具体错误时还能找出 许多小技巧，这儿就不再列举了。 下面我将通过分类举例来讲述我对如何仔细分析错误的理解。 导致我们设计出一个错误算法的原因大致有三类： 一、误解模型的性质。其中的模型指所有的数学模型，之前所说的信息利用不充分也 属于这一类。这是一个主流原因，更深入的讨论见下一节中古老的渔网问题。 二、猜想错误。不知如何将模型与算法联

12、系起来时，我们常提倡大胆去猜想。但猜想 难免出错，如何处理这类错误至关重要。在奶牛航班的分析过程中出现了这个问题。 三、不了解算法细节。需要适当改进一个经典算法时，如果我们对这个算法的掌握不 够透彻，很容易出现问题。下面的例子， 可疑的斑点 ，不是图论问题，但很有代表性， 它主要涉及KMP 算法。 3.2 例题 例 奶牛航班 1 约翰的奶牛们开通了一条飞机航线，专门为奶牛服务。每天早上，她们沿着密歇根湖 的西岸，从线路的最北端出发飞到最南端，全程经过N 个机场（包括头尾两个） 。到了下 午，她们又会沿着同样的路线飞回最北端。每天都会有数目不同的K 群奶牛要求乘坐飞机， 一群牛会在某一个机场等待

13、，并希望飞到另外一个特定的机场。 飞机上只能同时容纳C 头奶牛乘客，航班的负责牛希望知道在这一天中她们最多可以 满足多少头奶牛的要求。飞机可以只将一群牛中的一部分带到目的地。 约定：1N10,000，1K50,000，1C100。 初步分析 飞机的一去一回很明显是两个相同的问题。而且如果一头奶牛非要绕一次折返点的话， 它会在原来的基础上再多在飞机上坐一段路，这并不划算。于是这两个子问题互不干扰， 可以单独处理，我们接下来只需考虑一个方向上的事情。还有一个问题是我们不必多考虑 的，那就是飞机在途中的哪些机场着陆。我们可以认为它在每个机场都做停留（这并不耽 误什么） ，或者干脆把它当作一辆长途汽车

14、。 题目给人的第一感觉是动态规划：将机场看作点、牛的飞行路线看作边，那么算法将 为每个点记录下从起点飞到这里最多能服务多少头奶牛，并通过边进行状态转移。 联系到这一题的实际情况，我们会很快发现这是很荒谬的。在这样的动态规划得到的 方案中，肯定不会出现有重叠关系的边，但是我们的飞机完全有可能同时满足两头路线重 叠的牛的飞行要求。 看来这不是一个常规的动态规划题，我们只好先把动态规划的思路搁在一边。 最小费用流模型 数据规模的约定提醒了我们要好好利用飞机上座位不多（最多100 个）这个条件。一 1题目来源：USACO 2005 年十月竞赛，Flying Right。2006 年全国信息学冬令营讲座

15、 第 5 页 共 20 页 个座位一个座位地考虑，最直接的方法莫过于网络流了。 容量网络的建立并不复杂：仍然以机场为点，牛群的飞行线路为边。每条边的容量赋 为牛群中的牛数M i ，权值都是1。代表这个牛群最多可以“容纳”M i 个座位，每当一个座 位选择了这个群，就相应的得到1 点权值。再从每个点（除最后一个）向它的后一个点连 一条容量无穷大、权值为0 的边，代表座位在这一段可以是空闲的。总的来说，模型中的 一个单位流就代表了一个座位。 为了避免最大费用流这个怪异的名词，在实现时把权值改为-1 即可。最小费用流的算 法中，用Bellman-Ford 算法求一次最短路需要O(K*N)，最大流量等

16、于座位数C，所以 算法的总复杂度是O(K*N*C)，无法承受题目给出的数据规模。 加入贪心思想 给这个特殊的图套上最小费用流算法的确有点浪费，时间复杂度高是必然的结果。那 么如何利用这些特殊点优化算法呢？ 费用流算法中，每次找到一条最短路径（权和最小的路径）进行扩展。扩展时为了可 能的改动，我们会给扩展边的反向边扩大容量，这个处理解决了后效性的问题。仔细想想， 在这个问题中或许根本就不存在后效性，我们能不能放弃对反向边的处理？ 不处理反向边使算法有了本质上的改变。它所做的相当于：逐一安排每一个座位，使 每个座位在当前情况下全程载牛数最大。对此，我们不必再用B-F 算法，动态规划可以在 O(K)时间内得出答案。这样，总时间复杂度降到了O(K*C)，足以满足题目所给的数据规 模。 但是这个算法存在反例： 图2 反例的图示 起点 起点 终点 终点 路线A 路线B 路线C 路线D 如图2，假设这4 条路线中都只有1 头牛，那么一架配有两个空位的飞机就可以为所 有的4 头牛服务。但是以上的