（运筹学与控制论专业论文）图的控制集问题的近似算法研究.pdf

图的控制集问题的近似算法研究 摘要 控制集问题是组合优化理论中一个有意义的，重要的研究领域。给定无向 图g = ( ve ) 和顶点子集s y ，如果对于v v v ， s 或u 与s 中的元素相邻， 则称s 是图g 的一个控制集。一般的控制集问题是寻找图g 的最小个数的控制 集s 。部分控制集问题是指对于给定的顶点赋权图g = ( ke ；c ) 和正整数k ，寻 找图g 的一个顶点子集t ，使得在其控制下的顶点个数不小于k 且使丁中顶点权 和达到最小。本文主要从算法和计算复杂性角度对控制集和部分控制集问题进 行讨论。主要研究内容有： ( 1 ) 将集合覆盖问题的近似算法理论应用到控制集问题中，给出了该问题 的g r e e d y 算法，原始对偶算法和线性规划的舍入算法，进而对各算法的近似度 进行了理论分析。 ( 2 ) 引入了部分控制集问题并建立了其整数规划模型。在证明了该问题 的p 一困难性基础上，给出了修正g r e e d y 算法和基于“参数修剪”技巧的原 始一对偶算法，进而分析了算法的近似度。 关键词：图的控制集：部分控制集；p - 困难；g r e e d y 算法：原始一对偶算法 a p p r o x i m a t i o n d o m i n a t i n g a l g o r i t h m sf o r s e tp r o b l e m s a b s t r a c t d o m i n a t i n gs e ti sa l li m p o r t a n tf i e l di nc o m b i n a t o r i a lo p t i m i z a t i o nw i t h m a n ya p p l i c a t i o n s g i v e na nu n d i r e c t e dg r a p hg = ( ve ) ，as e ts v i sc a l l e d d o m i n a t i n gs e t ，i ff 6 re a c h v ，e i t h e rt so ru i sa d j a c e n tt oav e r t e xo fs t h ed o m i n a t i n gs e tp r o b l e ma s k sf o rad o m i n a t i n gs e to fm i n i m u mc a r d i n a l i t y t h ep a r t i a ld o m i n a t i n gs e tp r o b l e mi st of i n d ，f o rag i v e nv e r t e xw e i g h t e dg r a p h g ：( v e ；c ) a n dap o s i t i v en u m b e rk ，as u b s e tt v s u c ht h a ta tl e a s tk v e r t i c e so fv & r ed o m i n a t e db yta n dt h et o t a lv e r t e xw e i g h to ft i sm i n i m i z e d t h i st h e s i sd i s c u s s e st h et w op r o b l e m sf r o mt h ep o i n to fv i e wo fa l g o r i t h m sa n d c o m p u t a t i o n a lc o m p l e x i t y t h em a i nr e s u l t sa r ea sf o l l o w s ： ( 1 ) a p p l y i n gt h et e c h n i q u eo fa p p r o x i m a t i o na l g o r i t h mf s e tc o y e rp r o b l e m t ot h ed o m i n a t i n gp r o b l e m ，t h r e ea l g o r i t h m s - - g r e e d ya l g o r i t h m 、p r i m a l d u a la l - g o r i t h ma n dl pr o u n d i n ga l g o r i t h m ， l l ep r o p o s e d ，a n df u r t h e rt h e i rp e r f o r m a n c e r a t i ow i t ht h e o r e t i c a la p p r o a c hi sa n a l y z e d ( 2 ) f i r s tan e wp r o b l e m ，c a l l e dp a r t i a ld o m i n a t i n gs e tp r o b l e m i si n t r o d u c e d ， a n d s h o wt h a ti ti si ng e n e r a ln p h a r d t h e nt w oa p p r o x i m a t i o na l g o r i t h m sf o r t h i sp r o b l e m - - t h er e v i s e dg r e e d ya l g o r i t h ma n dp r i m a l - d u a la l g o r i t h mb a s e do n “p a r a m e t e rp r u n i n g ”t e c h n i q u e ，a y ep r o p o s e d ，a n d t h ep r o o fo nt h ep e r f o r m a n c e r a t i oo ft h ea l g o r i t h m si sg i v e n k e y w o r d s ：d o m i n a t i n gs e t ；p a r t i a ld o m i n a t i n gs e t ；n p h a r d ；g r e e d y a l g o r i t h m ；p r i m a l d u a ls c h e m a 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：潍铨签字日期：砷f 年1 - n 7 e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：矿店硅 导师签字：方亏参 签字日期：上弦宫年r 月) 1 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 签字日期：必浒j - 月7 日 电话： 邮编： 第1 章综述 1 1组合最优化问题与计算复杂性 1 1 1 最优化问题 在实际和理论上具有重要性的许多问题，都涉及到选取一个“最好”的构形， 或者为了达到某个目标而选取一组参数，这样的问题连同求解它们的技术，形 成了最优化问题的体系。最优化问题自然地分成两类：一类是连续变量的问题， 另一类是离散变量的问题。具有离散变量的问题，称为组合最优化问题，它一 般是要求从一个有限集或可数无限集里寻找一个最好的对象，如一个整数，一 个集合，一个排列或一个图等。以下是最优化问题的一般定义。 定义1 1 1 一个最优化问题的一个实例是一对元素( fc ) ，其中f 是一个集 合或可行点的定义域；c 是费用函数或映射c ：f 一凡，问题是求一个f f ，使 得对一切y f 有c ( f ) c ( ) 。这样一个点，称为给定实例的整体最优解。 一个最优化问题。就是它的一些实例的集合，。为了对最优化问题有更直观 的了解，我们给出几个例子。 例1( 最小支撑树( 简记为m s t ) ) 给定顶点赋权无向图g = ( ve ；c ) ，其中c ：e 一珥是边权函数，寻找 图g 的一个支撑树t ，并且t 的边权和达到最小。 1 2( 线性规划( 简记为l p ) ) 令仇，n 为正整数，b ，c 扩，a 是m 礼的矩阵，它的元素啦f z ，求 解下列不等式 a x 2 o 且使得目标函数2 ：凹达到最小或最大。 【z o 例3( 背包问题( 简记为k n a p s a c k ) ) 给定集合s = 口l ，0 , 2 ，口。 ，s i ：e ( m ) ，p r o f i t ( a i ) 4 ( = 1 ：2 ，7 i ) ， 且给定正整数日，寻找集合s 的子集x ，满足s t z e ( x ) = 皿xs i z e ( a i ) b ，且 使得p r o f i t ( x ) = 啦x 刀o ，让( 啦) 达到最大 例4( 最大适定性问题( 简记为m a x - s a t ) ) 图的控制集问题的近似算法研究 给定几个布尔变量，u = f z l ，z 2 ，互。 ，甸子c 由若干个布尔变量或其否 用“+ ”连接起来，布尔表达式f = c l c 2 c ，u ：c _ 皿是句子的权函数，给 出u 的一个真值分配，使得被适定的句子总权重最大。 ， 例5( 旅行售货员问题( 简记为t s p ) ) 给定完全赋权图g = ( v e ic ) ，其中c ：e 一耳是边权函数，寻找通过y 中 所有顶点一次且仅一次的圈，并使得圈上的边权和达到最小。 关于其它的最优化问题的术语和实例，可参考文献【1 ，2 1 。 1 - 1 2 n 尸- 完备与p 困难 在解决最优化问题时，算法的有效性往往是我们首要关心的问题。所谓有 效算法，或称多项式时间算法，是指其基本运算步数由输入规模的多项式所界 定的算法。例如，解线性规划问题的椭球算法，解指派问题的匈牙利方法等都 是有效算法。然而，还有许多优化问题，如旅行售货员问题，顶点覆盖问题和可 适定性问题等，它们的算法设计如此之难，以至于人们无法知道其是否存在有 效算法。为此，c o o k 3 和k a r p 4 在七十年代初提出了只完备性理论，将这些 有效算法的存在性难题统一成一个深刻的数学猜想。 在考虑尸完备性理论之前，我们先给出最优化问题的三种形式( 这里只 针对最小化问题给出定义最大化问题相关概念可类似给出) ： ( 1 ) 最优化形式：给定最优化问题的实例( fc ) ，求最优可行解： ( 2 ) 计值形式：给定最优化问题的实例( 只c ) ，求最优解对应的目标函数 值； ( 3 ) 判定形式：给定最优化问题的实例( 只c ) ，以及一个整数三，判定是否 存在可行解f f ，使得c ( f ) 三? 对于大多数组合最优化问题，就多项式时间算法的存在性而言，这三种形 式是等价的。考虑最优化问题的判定问题，即答案为“是”或“否”的问题，按照判 定问题的计算复杂性把它们分类。 定义1 1 2给定判定问题a ，如果它能被某个多项式算法所解决，则 称- 4 是p 类的。 p 是相对容易的判定问题类，它们有有效算法。如例l 最小支撑树、例2 线性 规划问题等都属于p 类。 2 图的控制集问题的近似算法研究 定义1 1 3 给定判定问题a ，如果对于问题a 的答案为“是”的实例z ，均存 在对工的一个简短( 即其长度以z 的长度的多项式为界) 证明，使得能在多项式 时间内检验这个证明的正确性，则称a 是p 类的。 显然，p p ；而且p 类中包含人们所关心的许多问题，如上面提到 的背包问题、可适定性问题和旅行售货员问题等。可是究竟p 是尸的真子集 呢，还是p 和p 一样呢? 倘若后者是对的，那么若干著名的难题，如旅行售货 员问题、可适定性问题等便是p 类的，因此( 假设) 是容易的。现在人们普遍认 为p 是p 的真子集，但是尚无正式的证明。p n p 被认为是当今数学和计算 机科学中最重要的猜想之一。 在p 问题中有一类最难的问题一p - 完备问题。多项式变换是、r 尸完 备理论中一个最基本的工具。给定判定问题a 和b ，如果对于a 的任意实 例x ，在多项式时间内能构造出b 的一个实例y ，使得z 是a 的“是”实例当且仅 当y 是b 的“是”实例，则称问题以可多项式地变换到问题b 。 定义1 1 4 给定判定问题a n p ，如果所有其它的n p 问题都能多项式地 变换到a ，则称a 为n p 一完备的。 换句话说，如果问题a 是j v p 完备的，那么它具有很强的性质：若a 有有效 算法，则每个p 问题也有有效算法。1 9 7 1 年，c o o k 3 找到了第一个n p 一完备 问题一适定性问题，开创了p 一完备问题研究的历史。1 9 7 2 年k a r p 4 i t n 了另 # b 2 1 个问题与适定性问题等价。而后，以它们为“种子”繁衍出许多的n p 完备 问题，到目前为止，大约有几万个已被证明是n p 一完备问题。 a ，p - 完备问题概念的实际意义在于人们普遍相信，正确求解a r p 完备问题 的任何算法。在最好情况下也需要指数量级的基本运算步数，从而除规模很小 的实例外是不实用的。“难计算”是这些问题的固有性质。还有一些问题，虽然 不属于p 问题，但我们可以证明它们至少与任意的p - 完备问题同样困难，因 此很可能是难解决的，我们把它们称为p 困难的。除此之外，对于最优化形式 的最优化问题，若其判定形式是p - 完备的，我们也称该最优化问题是 r 尸困 难的。如前面例3 的背包问题、例4 的最大适定性问题和例5 的旅行售货员问题都 是n p 困难问题。将问题按其算法复杂性进行分类，p 类，p - 完备或者p - 困 难等，是最优化问题研究的一个重要内容。 3 图的控制集问题的近似算法研究 1 2p 困难问题的近似算法 在面对一个新的组合优化问题时，人们总是设法给出一些求解这个问题的 充分必要条件。如果所给的充分必要条件可在多项式时间内得到验证，那么常 常由此构造出解决该问题的有效算法。但是对于许多问题，人们无法找到这种 可在多项式时间内验证的充要条件，这时，尸- 完备性或者p 一困难性的证明， 便可使人们相信该问题不可能有有效算法求解。在这种情况下，人们会转而寻 求其它解决问题的方法，比如对一些特殊情形给出有效算法，或设计近似算法 等。 近似算法是随着大量重要的组合优化问题的n p 困难性而发展起来的。当 我们面对的是p - 困难问题时，用g a r e y 和j o h s o n 5 1 的话说“不仅我不能求解出 有效算法，任何名人也不能”。如果最优解不能实现，一个合理的目标是寻找一 个多项式时间算法，来求得“接近”最优的满意解，即近似算法。 近似算法并不保证给出最优解，那么如何评价近似算法的好坏呢? 主要是 基于两个方面的考虑：首先是时间复杂性方面的要求，即要求有一个多项式时 间界：其次是性能方面的要求，即希望所求的近似解尽可能“接近”最优解。 对于近似解好坏的评价，g a r e y ，g r a h a m 和u l l m a n 6 1 及j o h n s o n 7 给出了近 似算法中近似度的定义，它强调算法在最坏情况下目标函数的误差界限。 定义1 2 1对于一个最优化问题，一个算法a 被称为争近似算法，如 果a 是多项式时间算法，而且 ( 1 ) 当是最小化问题时，对其所有实例i ，4 ( ，) - ：o p t ( i ) ； ( 2 ) 当n 是最大化问题时，对其所有实例i ，么( ，) 2 o p t ( 1 ) 显然s 1 ，s 越接近1 ，近似度越好。 随着对n p 困难问题的深入研究，人们开发出许多近似算法的方法和技巧， 如贪心算法局部搜索法，基于线性规划的近似算法( 原始对偶算法和l p 舍入 法) ，动态规划，随机算法等，它们在解决不同的组合优化问题时，各有很好的 应用。而且，随着近似算法的进一步发展，最优化问题可根据算法的近似度进 行分类。以下将尸类组合最优化问题简记为n p o 。 定义1 2 2 ( a p x 类)给定n p o ，若对于某个常数：1 ，n 存在多项 式时间玉近似算法，则称为a p x 类。 前面提到的最大适定性问题具有2 一近似算法f 7 1 ，因此该问题属于。4 p x 类， 此外背包问题也属于该类。然而，一些重要的p 类组合问题并不存在近似算 4 图的控制集问题的近似算法研究 法，除非p = n p 。换句话说，对于一些问题，求出它们的一些常数近似度的近 似解与精确地求解该问题本质上是一样无望的。例如，对任意的 1 ，旅行售 货员问题没有e 一近似算法 8 】o 这意味着，在假设p n p 下，a p x 类严格包含 在n p 类组合问题中。 定理1 2 3若p n p ，则a p x 类c p d 。 定义1 2 4 ( p t a s 类)给定n p 0 ，对于n 的任意实例，和 0 ，当 算法a 应用到输x ( t ，) 时，可得到1 + 近似算法。且a 的运行时间为l 引的多项 式，则称算法a 为多项式时间近似方案( 简记为p 烈s ) 。p t a s 类是p d 中具 有p t a s 的一类问题。 在一个p t a s 中，的运行时间是i ，l 的多项式，同时也可能与；有关。近似 度越好，即三越小，则运行时间越大。在大多数情况下，随着近似度要求的增高， 在计算代价上也会有显著的增长。前面例3 背包问题属于p t a s 类f 9 1 a 由于背包 问题也属于a p x 类，因此我们很容易的得到下面的结论。 定理1 2 5 若p n p ，则尸7 m s 类ca p x 类。 定义1 2 6 ( f p 阴蹼)给定1 2 n p d ，对于的任意实例，和 0 ，当 算法4 应用到输入( j ，) 时，可得到l + 近似算法，且a 的运行时间为i j i 和：1 的多 项式，则称算法a 为完全多项式时间近似方案( 简记为f 尸t 4 s ) 。f p t a s 类 是n p o 中具有f p t a s 的一类问题。 从理论上讲，f p t a s 是p 困难最优化问题的最令人满意的结果。有f 尸丁 a s 算法的问题从某种程度上讲也是所有n p 困难问题中最容易的一种。例3 背 包问题也属于f p t a s 类9 1 。由此我们得到下面的结论。 ： 定理1 2 7 若p n p ，i j f p t a s 类cp t a s 类。 1 3 控制集问题的背景与模型 一控制集问题的背景 图上的控制集问题的研究起源于“五皇后问题”。图1 1 说明这样一个问题： 在8 8 的棋盘上放置一个皇后，按规则她只能水平、竖直、斜线移动，因此， 图1 1 中的皇后可移动到棋盘上标有“x ”的方格上。1 8 5 0 年，欧洲的象棋爱好 者考虑：在这个棋盘上至少放置几个皇后，可以使棋盘的每个方格都能被她们 占领? 图1 1 右图说明六个皇后可以控制棋盘的每个方格。但该问题的最小值 5 图的控制集问题的近似算法研究 是5 。“五皇后问题”是5 个皇后的控制集问题。随后数学家对这一问题进行了深 入的研究，1 9 6 2 芏1 e ，o y s t e i n o r e 1 0 】首次给出了“控制集”这一概念。棋盘上的控 制集问题可以叙述为更一般的图上的控制集问题。 x x x xx x幽xx xxxx x xx xx xx x x x x 图1 1 ：皇后 增 幽 嬲 磐 幽 鬻f 控制集问题给定无向图g = ( v e ) 和顶点子集s y ，如果对任意 的口v ，u s 或 与s 中的元素相邻，则称s 为g 的一个控制集。控制集问题是 寻找图g 的基数最小的控制集，即最小控制集。 对于图上的控制集，还有几种不同的定义，它们从不同的方面阐述了控制 集问题。我们考虑下面的等价定义。给定无向图g = ( ve ) ，集合s y 称为控 制集，当且仅当： ( 1 ) 对任意顶点u v s ，存在顶点s 。使得u 与t l 相邻： ( 2 ) 对任意顶点u v s 。d ( v ，1 ； ( 3 ) n s = v ( 其e p n v 】= u v ：u u e ) ut 为u 的闭邻域， 司= u s m ) ： ( 4 ) 对任意顶点u v s ，i ( u ) ns l 1 ； ( 5 ) 对任意顶点u v ，1 人r mns l 1 。 此外，对于赋权无向图的控制集问题可以描述为：给定顶点赋权无向 图g = ( ve ；c ) ，其中c ：v 一兄+ 是顶点权函数，寻找图g 的顶点权和最小控制 集。 图的控制集问题是组合优化领域的一个重要问题，在设施最优定位，选择 代表集、监视集，人员指派，通讯和对策等问题中都有广泛的应用背景。 6 图的控制集问题的近似算法研究 由于控制集问题是p 一完备问题，人们无法给出有效算法，因此在研究该 问题时，人们或者在某些特殊情形下给出有效算法，或者对其近似算法进行研 究【l l ，1 2 】。h e d e t n i e m i ，c o c k a y n e 和g o o d m a n 1 3 给出树形图上控制集问题的多 项式时间算法；r a m a l i n g a m $ f i ：l p m n g a n 1 4 给出区间图上控制集问题的多项式时 间算法。p a r e k h 1 5 】则给出一般控制集问题的近似算法一g r e e d y 算法，该算法 的近似度为1 1 1 ( 其中为图中项点的最大度) 。此外由于控制集问题是集合覆 盖问题的特例，有关集合覆盖问题的相关算法均可以应用到控制集问题，我们 在第二章中将给出具体应用。 二部分控制集问题 随着人们对控制集问题研究的深入，一些附带特定条件的控制集问题成了 目前人们研究的重点。 ( 1 ) 独立控制集问题：给定无向图g = ( ke ) 和顶点子集s y ，如果对于 任意口v ，1 t ) s 或 与| 5 r 中的元素相邻，且s 中任意两个顶点都不相邻，即s 是 独立集，则称s 为独立控制集。寻找基数最小的独立控制集称为独立控制集问 题。g a r e y 和j o h s o n 5 1 证明该问题为p - 困难的。a l i m o n t i 和c a l a m o n e r i 1 6 给 出对于b 一正则图，该问题的近似度为( j e i 2 2 b + 2 ) ( b + 1 ) b 2 + l 的一个近似 算法。 ( 2 ) 完全( 开) 控制集问题：给定无向图g = ( ve ) 和项点子集s y 如果对于任意顶点u v ，都存在顶点u s ，使得u 与t 相邻，则称s 为完 全( 开) 控制集。p f a f f 1 7 证明寻找基数最小的完全( 开) 控制集是p _ 困难 的：h a y n e s ，h e d e t n i e m i 和s l a t e r 1 1 贝l j 对该问题进行了更详细的研究。 ( 3 ) 连通控制集问题：给定无向图g = ( ve ) 和顶点子集s y ，如果对 于任意u v ，u s 或u 与s 中的元素相邻，且g f 剐为g 的连通子图，则称s 为 连通控制集。g a m e y 和j o h s o n 5 证明寻找基数最小的连通控制集为p 一困难 的；c u h a 和k h u l l e r 1 8 给出该问题的修 e g r e e d y 算法，其近似度为2 ( 1 + 日( ) ) ； 进而他们对上述方法进行改进，并将近似度改进为l i l + 3 ( 为图中顶点的最 大度) 。 ( 4 ) 七控制集问题：给定无向图g = ( y e ) 和顶点子集s y ，如果 对于任意u v ，u s 或u 与s 中的元素相邻，且对任意的顶点口v s ， 有i n ( v ) ns l 七，则称集合s 为七控制集。c o c k a y n e ，g a m b l e 和s h e p h e r d 1 9 】 给出最小基数的七控制集上界，最小肛控制集基数不超过鲁( n 为图g 顶点个 7 图的控制集问题的近似算法研究 数) 结合上述问题的提出背景，我们给出一个新的问题一部分控制集问题。 考虑如下实际问题：已知一些地区和这些地区之间的联结关系，人们希望 在其中一些地区建立公共设施，如公共图书馆、超市、车站等，使得每个地区周 围至少建有一个公共设施可以为它服务。由于每个设旅的建立均需要一定的费 用，由此提出的最优化问题是：在满足上述要求的前提下，如何选择建设公共设 施地点，使得总建设费用最小。这个问题就是地区联结图上的最小控制集问题。 但在实际生活中，由于某些原因，我们并不能要求所有的地区都得到服务，这样 我们考虑另一个相关的优化问题：如果只要求部分地区得到服务，那么如何选 择建设公共设施的地点，才能在满足要求的情况下使得总建设费用最小，我们 称此问题为部分控制集问题。 部分控制集问题给定顶点赋权图g = ( ve ；c ) ，其中c ：v 一日一是顶点权 函数，正整数k ( k i y l ) ，寻找顶点子集r y ，使得l 州7 l 且。rc ( 口) 达 到最小。 对于部分控制集问题，特别是其近似算法的研究，现有的结果较少。但是与 此相关的部分集合覆盖问题的近似算法研究较多，这对于我们研究部分控制集 问题有一定的启发。对于部分集合覆盖问题，k e a r n s 2 0 首先给出- j g r e e d y 算法 和初步的近似度估计；s l a v 伙【2 1 】则对该算法给出了更精巧的分析，得到了更好 的近似度，但其证明较繁锁；g a n d h i 等人 2 2 】则给出了原始对偶，近似算法( 其 中，是每个元素在子集中出现的频数的最大值) 。在第三章中，我们将结合上 述文章的思路给出部分控制集问题的近似算法。 本文将针对图上的控制集问题、部分控制集问题，研究其计算复杂性，并 对其近似算法进行讨论。主要结果有： ( 1 ) 对于控制集问题：将集合覆盖问题上的相关结果推广应用到控制集问 题，得到该问题的相关近似算法； ( 2 ) 对于部分控制集问题：证明该问题的尸一困难性，给出其修正g r e e d y 算 法和原始对偶算法两个近似算法，并分析各算法的近似度。 8 第2 章控制集问题的近似算法 本章讨论控制集问题的计算复杂性和近似算法。我们将集合覆盖问题 的若干近似算法应用到控制集问题中，给出了不同近似度的三个近似算 法，g r e e d y 算法、原始对偶算法和线性规划舍入算法。 2 1控制集问题的定义及计算复杂性 控制集问题 给定顶点赋权图g = ( ve ；c ) ，其中c ：y 一再是顶点权函 数，寻找顶点子集s y ，使得对于任意的幻v ，t ，s 或u 与s 中的元素相邻 且。sc ( 口) 达到最小。 g a r e y 和j o h 瑚o n 【5 于1 9 7 9 年证明了权重为1 的控制集问题为p - 困难的。下 面给出赋权的控制集问题只困难性的一个证明。为此，考察该问题的判定形 式： 实例：给定顶点赋权图g = ( v ，ec ) 和正整数p ； 问题：是否存在控制集s ，满足。sc ( v ) p ? 定理2 1 1 控制集问题是p - 困难的。 证明：我们将构造从已知的n p 一困难问题顶点覆盖问题，到控制集问题 的一个多项式变换。给定顶点覆盖问题的一个实例，：图g = ( ve ) ，正整数k ， 是否存在顶点覆盖c ，使得i g i 耳? 由此构造控制集问题的一个实例如下： 图g = ( v 7 ，e 7 ；c ) 的顶点集合矿由两部分构成： 图g = ( v e ) 的顶点集y ；补充顶点集t = 。；( u ，u ) e ) ； v = vut 。 图g 7 = ( v 7 ，e 7 ；c ) 的边集合e 7 = eue lu 岛，其中 e 为图g = ( v e ) 的边集： 局= ( 让，。) ：让v ( t ，u ) e ) ； 易= ( ，t 。) ：”k ( 让，u ) e ) 顶点权函数c 三1 ；p = k 图的控制集问题的近似算法研究 假设c 是图g 的一个顶点覆盖，满足i c i k ，则e 也是图g 的一个控制 集，易见c ，也是图g ，的一个控制集，且。gc ( v ) = i c i = 口。即所构 造的控制集问题的实例为“是”实例。反之，假设s 是图g 7 的一个控制集， 有唱sc ( u ) = l s i 口= k 。令c = , v l v s ny ) u v l t 。s nt ) ，则有下列 成立： 。 ( 1 ) i c l l s l ； ( 2 ) c 是图g 的一个顶点覆盖。因为若图g 中存在一边( “， ) e ，且t ，u 均 不属于c ，这说明在图g ，中u ，t ，t 。也均不属于s ，这与s 是图g ，的控制集矛盾。 即顶点覆盖问题的实例为“是”实例。 易见，上述构造为顶点覆盖问题到控制集问题的一个多项式时间变换，故 定理得证。 2 2 g r e e d y 算法 在解决最优化问题时，往往首先想到的是g r e e d y 算法，其基本思想是每一 步都做出最优选择，我们希望通过局部最优得到全局最优。对于g r e e d y 算法在 组合优化问题中的应用，j 0 h n s o n f 7 和l 叫缸z f 2 3 将该算法应用到未赋权的集合 覆盖问题，得到算法的近似度为h ( d ) = 冬1 ( d 为最大的子集基数) ，( d ) 的 上界为1 + 1 0 9 d ，即日( d ) = o ( 1 0 9 d ) 。随后，c h v 乱缸 2 4 】将上述g r e e 句算法推广 到赋权的集合覆盖问题中，得到相同的近似度。在上述研究成果的基础上，我 们给出控制集问题的g r e e d y 算法。 记n v 】= 仳v ：伽e u u ，并称之为顶点u 的闭邻域；v s y ， 记f 别= u 。s m 。i e d ( v ) 为g 中顶点 的度，= m a x 。yd ( ) g r e e d y 算法2 2 1 s t e p l ：s 1 = d ，i = 1 ； s t e p 2 ：若y s 1 = 口，令铲= s ，转s t e p 4 否则，执行：在y 【s 】中选取顶点q ，满足 一丽箫刊n 编, v ev 懈) 一丽罚痢2 一t 丽不可丽 p 时 s t e p 3 ：对任意u n v i 】n s t l ，令p r i c e ( v ) = n ，s s il j i + ) ：i = i + l ， 转s t e p 2 ； s t e p 4 ：输出伊。 1 0 图的控制集问题的近似算法研究 下面给出该算法的近似度分析。该算法输出的顶点子集为伊，酽的总权重 为c ( 9 ) ；记南刀和o p t 分别为控制集问题的最优解和最优目标函数值。引入记 号，v v v ，将g v 中的顶点按照在算法中被控制的顺序排列为 i ，呓，嚷， 其中= d ( u ) + l ；对于同一次迭代中被控制的顶点可任意排列。 弓i 理2 2 2 若1 s 0 号z i ：v j 6 n v t l & a + l 。 该条件说明，非0 对偶变量对应的顶点可至多被控制- i - 1 次。这是因为每 个顶点至多与个顶点相邻，因此该条件显然对每一个顶点均成立。故下面原 始对偶算法主要基于原始互补松弛条件给出。 1 3 图的控制集问题的近似算法研究 原始对偶算法2 3 2 s t e p l ：z _ 0 ，y _ 0 ；s _ 0 ； s t e p 2 ：当吲= v 时，转s t e p 3 ，否则，执行：在y 旧中选择一个顶点， 记为吩，增加协直到存在一个顶点帆变紧，即j ：码州。t 】协= q ； s = s u 似l j ：蜥协= q ；更新y ； s t e p 3 ：输出sy 。 定理2 3 3 算法2 3 2 为控制集问题的+ 1 近似算法。 证明：令y 是算法2 3 2 结束时的解，s 为算法输出的控制集。当q = l ，p = + l 时，均满足互补松弛条件。因此由命题2 3 1 ，该算法近似度为+ l = q p 。 证毕。 三原始对偶算法的改进 为了使算法达到更好的效果，我们对原始对偶算法进行如下改进。 方法一：整理最终结论。基本思想是：每一次迭代结束后，对加入控制集的 点，按其进入顺序从后到前检验是否有多余的顶点选入解集，若有则舍去。 s t e p l ：y 一0 ：s _ d ，七一0 s t e p 2 ：当阎= v 时，转s t e p 4 ，否则，执行：k k + 1 ， 在y 中选择一个未被控制的顶点，记为，增加协直到存在一个顶点啦 变紧，即j ：v j e l 的= “，则s = su 抛l ，砷陬1 = c 女) ； s t e p 3 ：改进对于i 一七递减到1 ，若s 似】仍是y 的控制集，则s s 仇： s t e p 4 ：输出s ，y 。 方法二：同时增加某些元素的对偶值。当逐一的增加元素的对偶值时，会 增加算法的运行时间，故考虑同时增加一些对偶变量的值，以减少运行时间。 s t e p l ：g 一0 ；s 一回，k 一0 ； s t e p 2 ：当俐= v 时，转s t e p 4 ，否则，执行：七一k + l 。 改进对于y 阍中所有的顶点 ，同时增加其掣值，直到邑：巧吲协= ， 则s = s u 喙i j ：。，【。】珊= c k ； s t e p 3 ：对于i 一岛递减到l ，若s 巩 仍是y 的控制集，则s 卜s h ； s t e p 4 ：输出sy 。 尽管上述改进方法不改变算法近似度，但在实际应用中却有很好的效果。 1 4 图的控制集问题的近似算法研究 2 4线性规划舍入算法 本节，利用基于线性规划的舍入技术，给出控制集问题的又一近似算法。 一线性规划舍入算法的基本思想 ( 1 ) 给出整数规划模型及其线性规划松弛： r a i n 羔1 勺巧 q ：“ 襄字j 羔1 焉i 巧 o ，1 )= ，n ( l p ) ： m i n 1 勺 n 2 二1 巧巧机江l ，m 【巧0 j = l ，佗， ( 2 ) 求解l p 得分数最优解矿= ( z i ，z ；，z ：) 。 ( 3 ) 给定一个界值q ( 0 口 1 ) ：当苟2q 时令= 1 ，否则令= 0 ，从 而得到i p 的解( 墨z ：) 。 二控制集问题的线性规划舍入算法 h o c h b a u m 2 8 给出集合覆盖问题的线性规划舍入算法。下面我们将该算法 应用到控制集问题中。控制集问题的整数规划模型和线性规划松弛模型见第三 节( 2 1 ) 和( 2 2 ) 式。 线性规划舍入算法2 4 1 s t e p l ：求解l p ( 2 2 ) 式，得到最优解z = ( z l ，z 2 ，z 。) s t e p 2 ：给定界值，= + 1 ，将孔 的点仇放入s 中； s t e p 3 ：输出s 定理2 4 2 算法2 4 1 为控制集问题的+ l 近似算法。 证明：记o p t l | p 表示l p ( 2 2 ) 的最优目标函数值，o p 豫示控制集问题i p ( 2 1 ) 的最优目标函数值，s = 饥。， v i 。，) 表示算法2 4 。1 输出的解，s 的总 权重为c ( s ) 。由算法规则知，就，睾0 = l t ) 。 ( 1 ) 往证s 是个控制集。假设存在点v 不能被s 中任何一个顶点控 制a 令岛= 仇i ：吩【仇】) 则有 1 5 图的控制集问题的近似算法研究 ( 口) i s j i ，； ( 6 ) s j 中所有顶点酞，均有x i 7 1 。 r e ( a ) ，( 6 ) 可以得到l p ( 2 2 ) 中关于吻的约束： 巧 ，= 1 i ：v j c n v d 。 这与z = ( z 1 ，x 2 z 。) 是l p 的最优解矛盾。 ( 2 ) 再证c ( s ) f o p t z p ，o p t 。容易验证， c ( s ) 机s ，q 忍：1 ，c t 露 = ，：1c i x i = ，o p t l p f o p t = ( a + 1 ) o p t 1 6 定理得证。 第3 章部分控制集问题的近似算法 本章将讨论部分控制集问题的计算复杂性和近似算法。我们首先证明了 部分控制集问题是n p 一困难的；其次给出了该问题的修i e g r e e d y 算法和基于参 数“修剪”技巧的原始对偶算法，进而对这两个近似算法的近似度进行了分析。 3 1部分控制集问题及其计算复杂性 给定顶点赋权( 无向) 图g = ( ke ；c ) ，其中c ：v 一4 是顶点权函数。对于 顶点子集s 矿和顶点u v ，若u s l ，则称顶点口被集合s 所控制。一般的 控制集问题就是寻找图g 的一个顶点子集y 7 y ，使得y 中所有顶点都被矿7 所 控制并且y 7 的顶点权和达到最小。在实际问题中，我们经常遇到只要求y 中部 分顶点得到控制的情形，由此得到部分控制集问题，即给定正整数k ( k i u l ) ， 寻找g 的顶点子集t y ，