（运筹学与控制论专业论文）两个组合优化问题的线性时间算法.pdf

摘要 摘要 本文主要研究两个问题的线性时间算法，一个是赋权无向图中最大权森林问题 的线性时间算法，另一个是赋权无向图中m u l t i c u t 问题的线性时间算法。 对于赋权无向图g = ( k e ) 中的最大权森林问题，本文提出了时问复杂度为 o ( i e i ) 的线性时间算法一一m w f 算法，并证明了该算法是一个p t a s ，即对 v k z + ，该算法能在o ( i e i ) 时间内求得近似比为1 一去的近似解。 对于赋权无向图g = ( ve ) 中的m u l t i c u t 问题，本文主要研究树上的 m u l t i c u t 问题，当顶点对的数目k = 2 时，本文提出了线性时间算法，并且论证 了k 为常数时树上的m u l t i c u t 问题是一个尸问题。 关键词：线性时间最大权森林多割 a b s t r a c t 摘要 i nt h i sp a p e r , w em a i n l yc o n s i d e rl i n e a rt i m ea l g o r i t h m sf o r t h em a x i m u mw e i g h t e d f o r e s tp r o b l e ma n d t h em u l t i c u tp r o b l e m f o rt h em a x i m u mw e i g h t e df o r e s tp r o b l e mo naw e i g h t e du n d i r e c t e dg r a p hg = ( ve ) ，w ep r o p o s eal i n e a rt i m ea l g o r i t h m 一一m w f w ep r o v et h a tt h i sa l g o r i t h mi s a p t a s t h a t st os a y , v 忌z + 。t h i sa l g o r i t h mc a l lf i n das o l u t i o nw i t ha p p r o x i m a t i o nr a t i o 1 一去i no ( i e i ) t i m e f o rt h em u l t i c u tp r o b l e m ，w ed i s c u s st h i sp r o b l e mw h e nt h ew e i g h t e du n d i r e c t e d g r a p hg = ( ve ) i sat r e e w ep r o p o s eal i n e a rt i m ea l g o r i t h mw h e n 后= 2 ( t h en u m b e r o fv e r t e xp a i r s ) ，p r o v et h a tt h i sp r o b l e mi sapp r o b l e mf o ra r b i t r a r yc o n s t a n tk k e y w o r d s ：l i n e a rt i m e ，m a x i m u mw e i g h t e df o r e s t ，m u l t i c u t i i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文储虢弘呸书 黼瓤7 年莎月纱日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学 位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文储虢弧强书 签字吼w 气年6 月叶日 导师签名：亨钿硼 签字吼1 年g 月日 致谢 致谢 这篇论文的完成，离不开很多人的帮助。首先要感谢我的导师张国川教授对我 两年来生活上和学 - - j 上的关心和指导。张老师一直给予我热情的帮助。他的严谨治 学，积极乐观，平易近人，求实较真的态度，无一不感染着我。张老师的细心指 点，让我受益匪浅。他不仅传授给我们丰富的专业知识，而且在研究问题的思路 和方法上认真的点拨，不厌其烦。张老师还为我们营造了一个良好的学术环境，为 我们提供了众多的交流机会，在此向他表示最诚挚的谢意! 感谢杨启帆老师，谈之奕老师等，感谢他们传授我知识，使我学业上得到进 步。 感谢陈光亭老师，沈灏老师，胡晓敏老师等，他们在我本科的学习和生活中， 给了我很多帮助。 同时也要感谢讨论班里的师兄师弟们，他们分别是：方侃，吕思远，徐海峰， 罗文昌，路滨，陈林，叶德仕，侯海洋，余国松。谢谢他们平时对我的关心和帮助 以及众多极具价值的建议。 最后我要感谢我的父母对我的培养和关怀，感谢女友给予我生活的激励和支 持。 绍论 1 绪论 1 1 组合优化问题及算法复杂性简介 日常生活中，几乎所有的社会活动中都有寻优的需求，用数学的语言来描述这 些活动，建立相应的数学模型，以适当的方法来求解这些数学模型，并得到令人比 较满意的结果，是2 0 世纪应用数学的重大发展之一。在这样的背景下，组合优化 得到了很大的发展，组合优化是运筹学的一个重要分支，在计算机科学，物流和供 应链管理等新兴领域有着广泛的应用。组合优化问题又称离散优化问题，是一类 重要的优化问题，虽然某些组合优化问题历史悠久，但作为运筹学的一个独立分支 而发展起来还是近几十年的事。 我们可以把一个优化问题看作一个带有参变量的提问，当这些参变量被赋予特 定的值，我们就可以得到该问题的一个实例，对于特定的实例，总是存在一种方 法，按照这种方法我们可以快速的找到问题的最优解或者令我们比较满意的近似 解。但是对于任意一个优化问题，是否存在一个普遍有效的方法，用之可以快速 有效的解决该优化问题的所有实例，却往往不为人所知。这就给我们提出一个问 题：是否可以具体问题具体分析，从问题的特殊结构出发，利用这些特性找到解决 问题的办法? 组合优化问题的研究就是这样，我们希望可以利用问题各自的组合结 构，找到解决问题有效的方法。 定义1 ：组合优化问题丌是一个极大化问题，它有一个实例集合，对于该实例 集合中的每一个实例，有一个有穷的可行解集合s ( ，) 。它有一个目标函数，该 目标函数对每一个实例和每一个可行解盯s ( ) ，赋予一个有理数1 ( 1 ，口) ，则 实例，的最优解为这样一个可行解a r a s ( i ) ，它使得对于所有的盯s ( i ) ，都有 f ( i ，盯) f ( i ，t 7 a ) 。 求解任何一个问题，我们都需要一种方法，我们称之为算法。 定义2 ：算法是用来求解问题的一个通用程序的描述，算法分为确定性算法和 随机算法，这里我们给出确定性算法的定义，即算法由前一步到后一步的运算是由 绍论 当时的状态确定的。如果一个算法对问题7 r 的任意一个实例，在有限步之后，一 定可以得到该实例的一个解，那么我们说该算法解决问题丌。 能够解决一个优化问题的算法并不唯一，有些算法可以求得问题的最优解，而 有些算法只能求得近似解。于是我们有以下定义： 定义3 ：对于一个优化问题7 r 的任意一个实例，算法a 总是能够找到一个可 行解盯s ( ，) ，那么我们称算法a 为问题7 r 的一个近似算法。如果这个可行解的 值总是等于最优解的值，那么我们说算法4 为问题丌的一个最优算法。 为了求解一个问题，我们可以设计有很多种算法，在这些算法中，有的能够求 出问题的最优解，我们称之为最优算法。有的能够求出问题的近似解，这些近似解 值与最优解值相比，有一个确定的衡量，我们称这种衡量为算法的性能比，称这 类算法为近似算法。还有些算法，求出的解值与最优解值相比，没有确定的界，我 们称之为启发式算法。近似算法的性能比有绝对性能比和渐进性能比之分，下面我 们给出近似算法性能比的确切定义。 定义4 ：近似算法a 的绝对性能比r 定义为： r a = i n ， r l l r a ( i ) r ，对任意的实例，) 一个近似算法a 的渐进性能比兄署定义为： r 署= i n f r 1 l 存在n z + ，使得对任意的实例i n ，有r a ( i ) 7 ) 。 任何算法求解问题都要付出一定的代价，那就是求解问题所要花费的时间。 在日常购物中，我们希望能够物美价廉，同样，我们希望算法即高效又精确，然 而，鱼和熊掌往往不可兼得，我们可以在相对较短的时间内求得一个问题的近似 解，而却要花费大量的时间去求解问题的最优解。所以，一个算法的好坏，不仅 仅在于它所求出的解的质量，还在于它的效率。在一般意义下，算法的效率用算法 所用的全部计算资源的多少来衡量，但是通常用时间作为衡量标准，我们称之为算 法的时间复杂度。 定义5 ：算法的时间复杂度是关于实例输入长度的函数，用来表示算法的时间 需求，对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的实例 所需的时间( 基本运算步骤) 。 2 绪论 不同算法的时间复杂度函数一般不同，判断它们的效率高低就需要一个评判标 准，以下是一种常用的评判标准。 定义6 ：若存在一个常数c ，使得对于所有的扎0 ，都有lf ( n ) l ci 夕( 钆) i ， 则称函数f ( n ) 是0 ( 9 ( n ) ) 。如果p 是一个多项式，礼是输入长度，则时间复杂度 是0 ( p ( n ) ) 的算法称为多项式时间算法。我们把不能这样限制时间复杂度函数的 算法称为指数时间算法。在多项式时间算法中，有两个重要的概念，p t a s 和 f p t a s 。一个多项式时间近似方案p t a s 是这样一个算法：算法的输入不仅仅 是问题的一个实例，还有一个参数e 0 ，对任意的e 0 ，算法能够在关于输入的 多项式时间内求得近似比1 + e 的近似解。例如，一个刀a s 的运行时间可能是 d ( 礼；) 。一个完全多项式近似方案f 刀a s 是指：算法的时间复杂度是关于输入规 模和的多项式，如果一个p t a s 的运行时间是d ( 壶n 3 ) ，我们称这个p t a s 为 f p t a s 。 在复杂性的研究中，仅当输入规模很大时，研究才显得有意义。很多实际问题 由于输入规模太大或者问题本身要求，我们又希望能够快速的得到问题的解，最优 算法或者阶数较高的近似算法求解问题所用的时间都让人难以接受。这样就要求 我们在设计算法时尽可能降低算法的复杂度，甚至可以牺牲部分解的质量来换取解 的效率。我们知道，对于一个p h a r d 问题，要求出它的最优解很困难，然而 现实中我们需要在较短的时间内求出问题的解，这就促使我们设计问题的多项式 时间的近似解。如果一个近似算法的性能比在我们能够接受的范围内，而且复杂度 又不高，在实际中就会有很好的应用价值。线性时间算法是一类很好的多项式时 间算法，它时间复杂度很低，如果一个线性时间算法的性能比不差，就有很高的实 际应用价值。在这样的背景下，线性时间复杂度算法的研究就显得非常必要。 1 2线性时间算法相关研究进展 一个优化问题的线性时间算法a 是指：对于该优化问题的任意一个输入规模 为n 的实例，算法a 都能够在o ( n ) 时间内求得问题的解。本文研究的是线性时 间算法，在给出本文研究结果之前，我们先给出一些经典的组合优化问题的有关线 性时间算法的研究进展。 绍论 最短路问题是一个与实际应用有着紧密联系的经典优化问题。例如，我们乘 车旅行总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出 每对十字路口之间的距离，如何找出这一最短行程? 一种比较容易想到的方法就 是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们 很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而 其中绝大多数是不值一虑的。首先，我们阐明如何有效地解决这类问题。在最短 路径问题中，给出的是一有向加权图g = ( ve ，w ) ，其中y 为顶点集，e 为有向 边集，w 为边上的权集。最短路径问题研究的问题主要有：单源最短路径问题和 所有顶点对之间的最短路径问题。单源最短路径问题是指：已知图g = ( ve ) ， 我们希望找出从某给定的源结点s v 到y 中的每个结点的最短路径。对于单源 最短路问题，当图g = ( ve ) 中所有的边的权重都不小于零时，公认的比较好的 算法是d i j k s t r a 在1 9 5 9 年提出来的。但在单源最短路径问题中可能存在权为负 的边。这时如果图g = ( ke ) 不包含从源s 可达的负权回路，则对所有v v ， 最短路径的权定义依然成立，即使它是一个负值也不违反最短路的定义。但如果 存在一从s 可达的负回路，最短路径的权的定义就不能成立。8 到该回路上的结 点就不存在最短路径。当有向图中出现负权时，d i j k s t r a 算法失效。当不存在源 s 可达的负回路时，b e l l m a n f o r d 算法可以用来求源s 到其它顶点的最短路。 当图g = ( ve ) 是一个无回路的有向图时，求图g = ( ue ) 的单源最短路径问题 可以在o ( v + e ) 时间内解决。有向无回路图中的最短路径总是存在的，这是因 为即使图中有权为负的边，也不可能存在权为负的回路。每对结点间的最短路径 是指：要找出图中每对结点间的最短路径问题。这个问题在实际中常常会出现。 例如对一交通网络图，要造表说明其上的每对车站之间的距离时就可能会出现这 种问题。对于有向图g = ( ve ) ，要求每对结点间的最短路径，我们可以把单源 最短路径算法运行iy1 次来解决，每次依序把图中的每个结点作为源点。若所有 边的权为非负则可以采用d i j k s t r a 算法，时间复杂度为o ( v 3 ) ；如果有负权边的 存在，则须对每个结点运行一次速度较慢的b e l l m a n f o r d 算法，其运行时间 为o ( v 2 e ) 。另外f l o y d w a r s h a l l 算法可以用来解决存在负权边但无负回路的 有向图g = ( ve ) 的每对结点问的最短路径问题，其运行时间为o ( y 3 ) 。另外， 4 绪论 对于任意有向图g = ( ve ) ，如果图中边的权重分布为【1 ，2 ，m 】，其中m 为一 个正整数。g o l d b e r g 6 1 给出了一个线性平均时间的算法，该算法的时间复杂度为 o ( m + nl o gc ) ，其中c 为图中边的最大权值与最小权值之比。当图g = ( ve ) 是 无向图，且图中边的权重是正整数时，t h o r u p 7 在1 9 9 9 年给出了一个线性时间 和线性空间的算法。m i t r a ，h a s a n 和k a y k o b a d 8 1 在2 0 0 1 年给出了赋权图的时 间复杂度为o ( m k + n ) 的单源最短路算法。其中k 为图g = ( ke ) 最大边权重和 最小边权重的比值，m 是图g = ( ke ) 中边的数目，n 是图g = ( ke ) 中点的数 目。对任意权重的有向图，当图g = ( ke ) 的边权重分布在 0 ，1 】之间，u l r i c h 和 m e y e r 9 1 提出了线性平均时间算法，该算法的时间复杂度为o ( m + n ) 。 旅行商问题是计算机算法中的一个经典的难解问题，已归为尸一c 问题类。 对该问题有一个实际的描述：某著名旅游区共有n 个景点c 。，c 2 ，a n ，每个景点的 位置与两两之间距离均为已知。一名游览者从某一景点g 出发，游览每个景点仅 一次，最后回到出发点c i ，问：为使行程最短，如何安排旅游路线? 旅行商问题 ( t r a v e l i n gs a l e s m a np r o b l e m ，缩写t s p ) 可以描述为：给定图g = ( ke ) 和关 于边e 的非负权重函数w ：e _ 兄+ 找一个最小费用环游，使得该环游经过g 中 每个顶点仅一次。t s p 问题不仅应用于行程路线的安排，也应用于机器排序，聚 类，计算机线路安排，曲线重构。t s p 问题的主要研究进展有： l ：一般t s p ( 对权重函数没有限制) 是p 困难问题，已证明不存在近似比为 p ( 礼) ( 关于n 的多项式) 的近似算法。 2 ：在度量空间下的t s p ，即w ( u ，v ) sw ( u ，w ) + w ( w ， ) ，u ，u ，w v ，是 n p 完全问题，并且存在近似比为1 5 的近似算法。 3 ：在d 维欧几里德空间下的t s p ，也是p 完全问题，存在p t a s ，但是没 奄fp t a s o 对在d 维欧几里德空间下的t s p 问题，a r o r a 1 0 1 在1 9 9 7 年给出了一个能在 o ( n ( 1 0 9 n ) d ( c ) ) 时间内求得近似比为1 + 1 c 的近似算法，并证明了该算法对欧几 里德空间下的最小生成树和最小费用完美匹配同样适用。对赋权无向平面图上的 t s p 问题，k l e i n 1 l 】在2 0 0 8 年给出了线性时间算法，该算法能够在o ( c 1 f 2 n ) 时 绪论 问内求得近似比为1 + 的近似解，并且证明了非赋权时，算法的时间复杂度为 o ( c 1 n 1 。 在计算机科学里面，子集和问题在密码学和复杂性理论中都占有重要的地 位子集和问题可以描述为：给定一个整数集合，是否存在一个子集，使得该子集 中所有元素之和为零? 例如，给定集合 7 ，一3 ，一5 ，5 ，8 ) ，答案是肯定的因为子集 一3 ，一5 ，8 ) 的元素和为零。子集和问题是尸一c 问题。该问题还可以描述为：给 定一个整数集合5 - 和一个整数8 ，是否存在s 的一个子集，使得该子集的所有元 素和为s ? 子集和问题可以看作背包问题的一个子问题。子集和问题的一个有趣的 特殊子问题是划分问题，在划分问题中，8 是整数集合s 中所有元素和的一半。 子集和问题不是最优化问题，而是一个判定问题。一个简单的想法是枚举出所有 的组合情况，如果集合s 中有个元素，则总共有2 种组合情形，当n = 1 0 时，有1 0 2 4 中组合方式，但是当n 很大时，这个指数时间的复杂度让人难以接 受。在子集和问题的研究进展中，先后有人提出了指数时间算法，伪多项式时间 动态规划算法，多项式时间近似算法，本文主要关注线性时间算法，所以对上述算 法不再详细介绍。对子集和问题，p r z y d a t e k 1 2 1 在1 9 9 9 年给出了空间复杂度为 线性，时间复杂度为o ( n l o g 几) 随机算法。给定n 个正整数的一个集合和容量为c 的背包，找该集合的一个子集，使得该子集的所有元素和尽量接近c 且不超过c 。 k e l l e r e r ，m a n s i n i ，p f e r s c h y 和s p e r a n z a 1 3 】在2 0 0 3 年给出了时间复杂度为 o ( m i n ( 詈，n + 刍l o g ；) ) ，空间复杂度为o ( n + ；1 ) 的算法，并且证明了当最优解不 超过( 1 一) c 时，算法总能够找到最优解。 在计算复杂性理论中，反馈顶点集问题图论中的尸一c 问题，它是最早 的被证明是尸一c 问题的问题之一，反馈顶点集问题可以描述为：给定一个 无向图g = ( ke ) ，权函数w 赋予g = ( ve ) 中每个顶点非负的权重，找顶点 集y 的一个子集，使得删除这个子集后g = ( ve ) 中不合圈，要求该子集的权 重和最小。k a r p 最早证明在有向图上该问题是p c 问题，而且对于无向 图，该问题也是p c 问题。对于有向图，当顶点的入度或者出度不超过2 时 该问题已经是p c 问题，对于平面有向图，当顶点的入度或者出度不超过 2 时该问题已经是p c 问题。我们很容易可以看出，如果删除无向图中权 6 绍论 重最小的边集使得图中不含圈，就等价于找最小生成树，这是一个p 问题。然 而，如果图g = ( ke ) 是有向图，则该问题是p c 问题。虽然反馈顶点集问 题是一个尸一c 问题，对于某些特殊的图形，依然存在线性时间最优算法。 l u 和t a n g 1 4 1 在1 9 9 7 年关于间隔图上的反馈顶点集问题提出了线性时间算法。 z h a n g ，l i 和l i 1 5 1 在2 0 0 4 年提出了关于i n t e r v a l 图上的反馈顶点集问题的线性 时间算法。c a r r a b s ，c e r u u i ，g e n t i l i 和p a r l a t o b 1 6 1 在2 0 0 5 年针对d i a m o n d 图上 的反馈顶点集问题提出了线性时间算法。 最长共同子序列( l c s ) 问题是找一个序列集合中所有序列( k 个) 的最长共同 子串。这是一个经典的计算科学问题，可以用来寻找两个文件中的不同点，该 问题在生物信息学中也有广泛的应用。在( l c s ) 问题中，当序列的数目k 作为 该问题的一个输入时，m a i e r 1 7 1 证明该问题是p h a r d 。当序列的数日k 为 常数时，该问题能够在多项式时间内用动态规划解决，一个很容易想到的方法 是求出一个序列中所有的子序列，然后判断这些子序列中哪些是其它所有序列的 子序列，然后从中选择一个最长的作为该问题的解。判断一个序列是否是另外 一个序列的子序列只需要线性时间。假设k 个序列的长度分别为n 。，n 2 ，n 知， 如果我们首先找出第一个序列的所有子序列，然后按照上述方法判断，则时间复 杂度为0 ( 2 n 1 ) 。当七= 2 时，动态规划能够在o ( n 1 n 2 ) 时间内求得问 题的解，对一般的k ，动态规划的时间复杂度是o ( k 兀警。仡) 。另外，对该问 题b e r g r o t h ，h a k o n e n 和r a i t a 1 8 提出了时间复杂度更低的算法。值得一提的是 l c s 并不唯一，要找到所有的l c s ，需要花费更多的时间，因为l c s 可能有指 数多个，即使后= 2 也是如此。然而借助于l c s 的某些特性，对k = 2 情形g u o 和h w a n g 1 9 】提出了时间复杂度为o ( n l ) ，空间复杂度为o ( n ) 的原始对偶算 法，其中n 为序列中元素的个数，三为l c s 的长度。 和l c s 问题很相近的一个问题是l o n g e s tc o m m o nr e p e a t 问题。和l c s 问 题一样，l o n g e s tc o m m o nr e p e a t 问题也有很好的实际应用背景。这是因为重 复性的字符串在数据挖掘，数据分析，数据压缩，计算分子生物学，计算机辅 助系统分析等领域有着广泛的应用。l o n g e s tc o m m o nr e p e a t 问题定义为：给 定一个字符串集合s = 五，正，瓦】，l o n g e s tc o m m o nr e p e a t 问题是找集合 绍论 s 中所有的字符串的最长子串，使得该子串在每个z 中最少出现两次。 在这 里我们把反向的相同字符子串也作为问题的解，详细的定义如下 2 0 】。假设t 是一个字符串，丁吲代表字符串t 的第i 个字符，t i j 】代表字符串t 的子串 t t i + 1 】，t j l 。t i i 丁| 代表字符t i 一1 】。t r 代表字符串t 的逆序。所 以有l t r i = i t i ，t 1 司= t i l t i i + 1 1 。t 兄c 代表字符串t 的完全逆序，在这里有 i t r c l = i t i ，t 兄c 嘲和t i l t l i + 1 形成一个w a t s o nc r i c k 对。字符串t 中的重 复有三种情形； 1 正常的重复子串：子串p 称为字符串t 的一个正常重复子串，如果 p = t i ，i + l p i 一1 且p = t i 7 ，i 7 + i p i 一1 】。这里i i 7 。 2 逆序的重复子串：子串p 称为字符串t 的一个逆序重复子串，如果 p = t i ，i + i p l 一1 】且p r = t i 7 ，z + i p i 一1 1 。 3 完全逆序子串：子串p 称为字符串t 的一个完全逆序重复子串，如果 p = t i ，i + l p l l 】且p 冗c = t i ，i 7 + i p i 一1 】。 对l o n g e s tc o m m o nr e p e a t 问题，l e e ，i l i o p o u l o s 2 0 】和p a r k 在2 0 0 7 年提 出了线性时间算法。 在数学学科的图论里面，匹配( m a t c h i n g ) 问题或者称为边独立集( e d g e i n d e p e n d e n ts e t ) 问题所要寻找的是一个边的集合，使得在这个边集中，任意两条 边之间没有公共顶点。这个边集可能是包含所有顶点的一个子图。下面给出匹配 问题的确切定义： 匹配( m a t c h i n g ) 问题：给定一个图g = ( ke ) ，那么g 中的一个匹配m 指的 是图g 中的一个边集，在这个边集中，任意两条边之间在图g 中没有公共顶点。 如果g 中一个顶点秒和匹配m 中的一条边相邻接，则我们称顶点 是匹配的。否 则称之为非匹配的。我们称匹配m 为图g 中的一个极大匹配，如果图g 中的任 意一条不在匹配m 中的边都和匹配m 中的一条边相邻接。我们称匹配m 为图g 中的一个完美匹配，如果图g 中的任意一点都在匹配m 中，即匹配m 匹配掉了 图g 中的所有点。每一个完美匹配都是最大的匹配，则每一个完美匹配也都是极 大匹配。另外，完美匹配也是一个最小的边覆盖。一个近完美匹配是指图g 中只 绪论 有一个顶点是非匹配的，这种情况只能是当图中的顶点数目为奇数的时候发生，因 此这样一个匹配也是最大的。 在任意的一个没有孤立点的图中，匹配的数目和边覆盖的数目之和等于图中 顶点的数目【2 1 】。如果有完美匹配，则匹配的数目和边覆盖的数目都是l v l 2 。 如果a 和b 是两个极大匹配，则i a i 2 1 b i ，i b l 2 1 a i 。很多学者通常会考虑 二部图的匹配问题，一个二部图g = ( v = ( x ，y ) ，e ) 的最大匹配问题【2 2 】相 对于一般图的匹配问题要简单很多。增广路算法可以在o ( i v l | e 1 ) 时间内找到 最大匹配。h o p c r o f t k a r p 算法相对于增广路算法降低了时间复杂度，它能在 o ( i v l l 2 e ) 时间内找到最大匹配。另外m u c h a ，s a n k o w s k i 2 3 提出了一个时间 复杂度为o ( i v l z 3 7 6 ) 的算法，但是该算法的实际应用性不强。在赋权的二部图 中，每条边有一个权值，二部图的一个最大赋权匹配指的是匹配中的边的权值之 和最大，如果一个二部图不是完全二部图，则可以添边使之成为完全二部图， 所添的边的权值为零。这样的一个问题就是我们常说的指派问题。该问题可以 用基于最短路算法的增广路算法来解决，如果用到b e l l m a n f o r d 算法，则可 以在o ( i v l 2 i e i ) 时间内找到问题的最优解。如果用到d i j k s t r a 算法，则可以在 o ( i v l 2 z o g ( i v l ) + j v i i e i ) 时间内找到问题的最优解。对于一般图的最大赋权匹配问 题，e d m o n d s 提出了第一个多项式时间算法。m i c a l i 和v a z i r a n i 2 4 1 提出了另外 一个时间复杂度为o ( i v l l 2 e ) 的算法。对一般赋权图的匹配问题的线性时间算法 的研究进展如下：p r e i s 2 5 1 在1 9 9 9 年提出了赋权图匹配问题的首个线性时间算 法，其算法的近似比为互1 。d r a k e 和h o u g a r d y 2 6 在2 0 0 3 年提出了赋权图匹配 问题的另外一个线性时间算法。s e t h 和p e t e r 2 7 1 在2 0 0 4 年提出了赋权图匹配问 题的第三个线性时间算法，该算法能在o ( m l o g ) 时间内求得近似比为；一e 的近 似解。 斯坦纳树( s t e i n e rt r e e ) 问题是一个经典的组合最优化问题，它和最小生成树 问题极为相近，不同的是为了减少生成树的长度，斯坦纳树可能包含除要求之外 的其它点。斯坦数树问题最早被描述为欧几里德s t e i n e rt r e e 问题：把平面上给定 的个点连接起来。要求任意两个点之间要么是用直线段直接相连，要么通过连 接替它添加的点相连，使得整个连通图形的总长度最小。欧几里德s t e i n e rt r e e 问 9 绍论 题中，添加的点的度数必须是3 ，而且与该点相连接的三条表形成度数为1 2 0 度的 三个角。s t e i n e rt r e e 问题在度量空间下和图论中都有各自的描述，这里不再一一 介绍，下面给出s t e i n e rt r e e 问题的确切定义。 斯坦纳树问题：给定图g = ( ke ) ，r v ，函数厂：e r + ，兄上的一个 s t e i n e rt r e e 是图g 中包含兄中所有点的一个连通无圈子图。通常称冗中的点 为端点，y r 中的点为斯坦纳点。斯坦纳树问题在芯片设计，网络设计，无线 电传输，计算生物学中有广泛的应用。s t e i n e rt r e e 问题是一个p c 问题， 但是某些比较特殊的s t e i n e rt r e e 问题却有时间复杂度很低的线性时间算法或者 时间复杂度比较低的多项式时间算法。对斯坦纳树问题，k o u ，m a r k o w s k y 和 b e r m a n 2 8 在1 9 7 9 年提出了时间复杂度为o ( i r i i v l 2 ) ，近似比为2 ( 1 1 l ) 的 近似算法。m a t t h i a s 和t a z a r i 2 9 1 在2 0 0 7 年对平面图上的一类斯坦纳树问题提 出了一个刀a s ，算法的时间复杂度是o ( n l 0 9 2n ) 。g e o r g i a d i s 3 0 】在2 0 0 3 年提 出了针对瓶颈斯坦纳树的线性时间算法。b r a n d s t a 和d r a g a n 3 1 1 在1 9 9 7 年对 d i s t a n c e h e r e d i t a r y 图上的斯坦纳树问题提出了线性时间算法。 组合优化问题中的装箱问题和排序问题也分别有线性时间算法，b e k e s i ， g a l a m b o s 和k e u e r e r 3 2 】提出了装箱问题的近似比为；线性时间算法。 d e l l 7 a m i c o 和f i n t a 3 3 1 提出了m 个相同平行机处理n 个单位加工时间工件 的线性时间算法。f i n n 和h o r o w i t z 3 4 1 提出了多处理机调度问题的线性时间算 法。以上仅仅是组合优化问题研究中的部分线性时间算法研究结论。下面我们简 要介绍一下本文的研究结论。 1 3 本文的研究概述 本文主要考虑两个问题的线性时间算法，一个是赋权无向图中最大权森林问题 的线性时间算法，一个是赋权无向图中m u l t i c u t 问题的线性时问算法。 对于赋权无向图g = ( ve ) 中的最大权森林问题，我们提出了时间复杂度为 o ( i e i ) 的线性时间算法，并证明了该算法是一个p t a s ，即对v k z + ，该算法能 在o ( i e i ) 时间内求得近似比为1 一去的近似解。 对于赋权无向图g = ( ve ) 中的m u l t i c u t 问题，当图g = ( ve ) 是一棵 1 0 绍论 树，k 为常数时，本文提出了线性时间算法。并分别对k = 2 和一般的常数k 进行 讨论，证明了对于任意的常数k ，该问题是一个p 问题。 最大权森林的线性时间算法 2 最大权森林的线性时间算法 2 1 最大权森林介绍 本章我们主要讨论赋权无向图的最大权森林问题，并将提出该问题的线性时间 算法。对任意图g = ( ke ) ( 文中所讨论的图均为无向赋权连通图) ，w ：e z + 为权函数，g 的最大权森林定义为： 定义7 ：对任意赋权无向图g = ( ve ) ，设其权函数为w ：e z + ，f 为图g 的所有带权森林的集合，w ( f ) = w ( e ) ，f ，则我们称厂。为 g = ( v e ) 的最大权森林，如果w ( f o ) = 嘴蚤w ( 厂) 。 则图g = ( ve ) 中的森林是由g 中所有点生成的无圈图。n g u y e n 2 】等人提 出了求非赋权平面图的星形生成森林i 口- i 题的近似比为；的近似算法，并且证明了 对于非赋权平面图来说，找到近似比好于鬻+ e 的近似算法是困难的；同时，在 这篇文章中，他们证明了求赋权树的最大星形森林存在线性时间算法，求赋权平 面图的星形生成森林问题存在近似比为石1 多项式近似方案。本文中我们提出了图 g = ( ke ) 的最大权森林问题的近似算法一m w f ( m a x i m u mw e i g h tf o r e s t ) 算法。 2 2m w f 算法 在提出算法之前，我们首先简要叙述算法的主要思想，然后对之进行详细的 描述。 显然，一个连通图的最大权森林是该图的一棵生成树。为了能够得到这样的一 棵生成树，很简单的方法是依次选择权重最大的边，并且保证所选择的边不会形成 圈。但是这样就需要按照权重对边排序，时间复杂度至少为o ( j e il o gl e l ) 。如果 问题的规模比较大，排序所需要的时间( 相对于线性时间o ( i e i ) ) 明显较多。但是 如果能够在线性时间内依次选择权重大的边，并且保证比较好的算法性能比，这 样，算法的实用性会好很多。出于这样的目的，我们设计了m w f 算法，它的主要 思想是：对图g = ( ve ) 中的任意一个顶点v ，找出与顶点v 相邻接的权重最大 最大权森林的线性时间算法 的边，这样，就不需要对与顶点u 相邻接的所有边进行排序，因为只需要从与顶点 u 相邻接的任意一条边出发，逐个对比和顶点v 相邻接的边的权重，选出权重较大 的一条边，如果两条边的权重相同，则可以选择两条边中的任意一条边。按照这 样的方法，就可以在o ( i e i ) 时间内选出- 9 顶点v 相邻接的权重最大的边。对图中 所有的顶点重复以上操作，我们可以得到图g = ( ve ) 的一些连通分支，把每一 个连通分支压缩为一个点，在图g = ( ve ) 中，如果两个连通分支之间存在两条 或则两条以上的边，则保留权重最大的一条边。按照这样的方法，可以在o ( i e i ) 时间内得到新图g 。按照同样的方法，找出图g 7 的所有连通分支，压缩所有连 通分支，保留连通分支之间权重最大的边，得到新图g ”。我们将证明，如果得到 的连通分支的个数为1 ，则我们就得到了问题的最优解；按照上述方法，可以在 d ( ie1 ) 时间内求得近似比为( 1 1 2 七) 的近似解。 依据上述思想，我们提出的算法可描述为： m w f ( m a x i m u mw e i g h tf o r e s t ) 算法： 输入：赋权无向图g = ( ve ) ； 输出：赋权无向图g = ( ve ) 的最大权森林。 s t e p l ：对v v g 舻( 最初i = 0 ，k o = 0 ，g o = g ) ，找出- 9v 相邻接的权重最 大的边，如果与v 相邻接的权重最大的边不止一条，则选择这些边中的任意一条， 从而得到图g 舻的若干连通分支，检查每一个连通分