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

2006年全国信息学冬令营讲座由图论问题浅析算法优化武钢三中 贾由 【摘要】 论文以图论问题为对象、以算法优化为主题、以分类和举例为基本模式进行了一系列探讨第一部分引言简单地介绍了图论与信息学竞赛的关系；第二部分分析了算法优化的根本途径：寻找特别之处；第三部分从算法的纠错入手，详细讨论其中的方法，进一步展示了发现问题的特殊点对算法优化的推动作用关键字】 图论 算法优化 错误分析【正文】一、引言 图论是一个十分有趣而且与信息学竞赛联系紧密的数学分支随着图论问题的日渐增多，一些经典图论模型与它们的相关算法已成为竞赛中不可或缺的知识与此同时，题目也越来越注重模型的转换与算法的优化这意味着在将知识转变为分数的过程中，我们需要做出更多的努力本文以其中的算法优化为主题，尝试了一些相关的归纳与讨论 另外，由于黑箱测试的缘故，我们所体验到的信息学可以说是一个以结果论成败的学科这是很好的，因为结果是对历史的总结但无论如何，对于一次以优化为主题的讨论来说，得到的最优算法仅仅是用来证明我们的优化过程是切实而有效的二、寻找特别之处——优化的根本途径2.1 介绍 每一个让算法更加漂亮的改进都可以称为优化不过在整体考虑一个问题时，优化的过程应该包括从原始算法到一个优秀算法当中的所有改进。

这通常是一个逐步发现并利用问题的特殊之处、使算法更有针对性的过程 做好优化的根本在于找出题目的特别之处这是一个宽泛的想法，没什么步骤和诀窍可言解决具体问题时，我们只能靠广泛的优化经验、充足的耐心以及一部分的灵感因素关于经验，之前的几篇论文已经分别就一些有共同特征的题目介绍了深入挖掘信息的具体过程这一章不再深入探讨某类问题，而是通过一个经典算法对“寻找特别之处”作出解释2.2 例题[例] 二分图的最大匹配 题目来源：经典问题 图的匹配指图中任何两条边都没有共同顶点的子图，二分图最大匹配问题旨在求出二分图中边数最多的一个匹配求解这个问题最基本的方法是将它转换成一个网络流模型： 为了方便叙述，我们将二分图的两个顶点集合成为A和B在图中加入源点和汇点，从源点向A中的每个点引一条边，容量为1；从B中的每个点向汇点引一条容量同样为1的边然后将原图中的边作为有向边添加进来，由A指向B，容量为1新图中用容量限制了每个点最多只能被一条边覆盖、每条边只能被记一次容易看出，这个图的最大流与最大匹配中的边数相等通过最大流算法，我们同样可以得到选边的具体方案 最显然的一个优化是不记录容量，所有边的容量都是一其次，这个网络中的可增广链很特别，它一定由源点开始，在点集A和点集B之间做若干次往返，再由B到达汇点的。

搜索时可以不考虑第一条与源点连接的边和最后一条与汇点连接的边，直接从点集A中的一个未匹配点开始到点集B中的一个未匹配点结束可以想象，在广搜的目标路径中减少两条边对于需要扩展的结点数的影响是巨大的这就是匈牙利算法的基本思想 基本的网络流算法与匈牙利算法的时间复杂度其实没有区别 都是O(M*N)，更快的算法可以参考[2]但是后者在所需空间、编写难度以及实际的运行时间上都拥有绝对的优势 几乎可以肯定匈牙利算法最初不是由上面这样的优化得到的，但这两种优化手段在网络流算法的设计中是很实用的：根据图的特殊性简化存储方式、量身定制搜索可增广链的方法[例] 牧场规划 题目来源：2003年安徽省省选 小可可的好朋友Sealock最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验他以网格的方式，非常规整地把牧场分割成M*N个矩形区域(M*N≤5000)，由于各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知区域(i,j)地可种面积使A(i,j) 每个区域种最多只能种植一个品种地花生可种植面积为零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。

这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做相邻 小可可准备帮助Sealock规划一下如何选择种植区域，才能使得实际可种植面积总和最大对应选择方案与网络的割 建立方案与网络的割之间一一对应关系的方法在[4]中曾有所描述，我们根据这道题再回顾一遍S T图1 建立网络 将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点由二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷 方案对应的割：将方案中所选的白点和未选的黑点再加上源点划为一个集合，其它点划到另一个几何，就得到了一个割直接把这个过程反过来，我们很容易由割得到一个方案在这个对应中：一、不合法方案对应的割均为正无穷；二、在合法方案对应的割中，割上的点代表了方案没有取到的边所以当割的容量最小时、方案选取的面积最大，而根据最大流最小割定理，我们可以通过求网络最大流得到它的最小割。

广搜可增广链 这同样是由二分图转换来的网络，但是边的容量一般化了我们仍然可以不搜索首尾两条边，不同的是以某一个“新源点”（原可增广链上的第二个点）为起点的广搜可能要进行多次，次数最多等于源点到它的边的容量；同理，一个“新汇点”可以容纳多个可增广链另外，为白点和黑点分别设计扩展过程也可以大大提高算法的效率三、改进错误算法——更灵活的优化3.1 介绍 我们常说的算法优化有四个方向：时间复杂度的优化、空间复杂度的优化、编写难度的优化以及思维难度的优化但是正如标题所表达的，这一部分的内容是如何提高算法的正确率 纠错也算是优化吗？如果你也有同样的疑问，那你一定是想到代码的查错上去了提高算法的正确率当然是对算法的优化甚至，算法的错误常常也是由于对题目信息的不充分利用导致的，只不过除此之外还有很多别的原因，我们一会儿就会进一步分析到它们 应对错误需要有一套方法首先，我们总会希望错误不要出现，比如思维严谨一点、看问题全面一点当问题不可避免地出现时，处理方法一定要视情况而定：如果考试的时间已经不多，可以通过一些简单的处理适当地提高正确率；如果还不紧张，就应该仔细地分析分析错误；实在无能为力的话，放弃已有的算法另寻他解也是一个明智的选择。

应急时的简单处理虽是无奈之举，却也值得一提最直接的办法是加入额外的判断过程，尽量把想到的反例都包括进去，但在问题比较复杂时，这通常是一件让人头疼而且收获不大的工作另一方面，随机化加重复求解的处理操作简单、效果惊人，更能为人们所接受对于最优化问题，取多次运算得到的最优解即可；判定性问题稍麻烦些，原算法还得满足下面两个前提中的至少一个：一、它的正确率高于50%，于是我们可以采用得出次数较多的那个结果；二、它可以准确判断“是”、“否”中的一个方面，假如被判断为“是”时一定正确，那么就把剩下得到的全是“否”的输入判为“否”应对具体错误时还能找出许多小技巧，这儿就不再列举了 下面我将通过分类举例来讲述我对如何仔细分析错误的理解 导致我们设计出一个错误算法的原因大致有三类： 一、误解模型的性质其中的模型指所有的数学模型，之前所说的信息利用不充分也属于这一类这是一个主流原因，更深入的讨论见下一节中古老的《渔网》问题 二、猜想错误不知如何将模型与算法联系起来时，我们常提倡大胆去猜想但猜想难免出错，如何处理这类错误至关重要在《奶牛航班》的分析过程中出现了这个问题 三、不了解算法细节需要适当改进一个经典算法时，如果我们对这个算法的掌握不够透彻，很容易出现问题。

下面的例子，《可疑的斑点》，不是图论问题，但很有代表性，它主要涉及KMP算法3.2 例题[例] 奶牛航班 题目来源：USACO 2005年十月竞赛，Flying Right 约翰的奶牛们开通了一条飞机航线，专门为奶牛服务每天早上，她们沿着密歇根湖的西岸，从线路的最北端出发飞到最南端，全程经过N个机场（包括头尾两个）到了下午，她们又会沿着同样的路线飞回最北端每天都会有数目不同的K群奶牛要求乘坐飞机，一群牛会在某一个机场等待，并希望飞到另外一个特定的机场 飞机上只能同时容纳C头奶牛乘客，航班的负责牛希望知道在这一天中她们最多可以满足多少头奶牛的要求飞机可以只将一群牛中的一部分带到目的地 约定：1≤N≤10,000，1≤K≤50,000，1≤C≤100初步分析 飞机的一去一回很明显是两个相同的问题而且如果一头奶牛非要绕一次折返点的话，它会在原来的基础上再多在飞机上坐一段路，这并不划算于是这两个子问题互不干扰，可以单独处理，我们接下来只需考虑一个方向上的事情还有一个问题是我们不必多考虑的，那就是飞机在途中的哪些机场着陆我们可以认为它在每个机场都做停留（这并不耽误什么），或者干脆把它当作一辆长途汽车。

题目给人的第一感觉是动态规划：将机场看作点、牛的飞行路线看作边，那么算法将为每个点记录下从起点飞到这里最多能服务多少头奶牛，并通过边进行状态转移 联系到这一题的实际情况，我们会很快发现这是很荒谬的在这样的动态规划得到的方案中，肯定不会出现有重叠关系的边，但是我们的飞机完全有可能同时满足两头路线重叠的牛的飞行要求 看来这不是一个常规的动态规划题，我们只好先把动态规划的思路搁在一边最小费用流模型 数据规模的约定提醒了我们要好好利用飞机上座位不多（最多100个）这个条件一个座位一个座位地考虑，最直接的方法莫过于网络流了 容量网络的建立并不复杂：仍然以机场为点，牛群的飞行线路为边每条边的容量赋为牛群中的牛数Mi，权值都是1代表这个牛群最多可以“容纳”Mi个座位，每当一个座位选择了这个群，就相应的得到1点权值再从每个点（除最后一个）向它的后一个点连一条容量无穷大、权值为0的边，代表座位在这一段可以是空闲的总的来说，模型中的一个单位流就代表了一个座位 为了避免最大费用流这个怪异的名词，在实现时把权值改为-1即可最小费用流的算法中，用Bellman-Ford算法求一次最短路需要O(K*N)，最大流量等于座位数C，所以算法的总复杂度是O(K*N*C)，无法承受题目给出的数据规模。

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