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

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

将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边，由白点指向黑点，容