（模式识别与智能系统专业论文）fpt算法在cbvc问题中的运用.pdf

f p t - 算法在c b v c 问题中的运用 摘要 f p t 算法( f i x e d p a r a m e t e r - t r a c t a b l e a l g o r i t h m s ) 被认为是当前比较流行的 运用于解决许多n p 完全问题的较为有效的算法，许多f p t - 算法是通过两个步 骤来对问题进行求解：首先，把实例转化为一个较小的等价体，具体来说，其大 小由只依赖于参数的一个函数所限制。这一步称为化简问题核心。其次，通过用 一些更小的参数解决一些导出子例，把简化了的问题用递归的方式来解决。因为 在递归调用中的那些参数更小，所以递归最终能完成( 要么找到一个解，要么了 解到由于k 蔓o 而没有解存在) 。这一步称为限定搜索树。 顶点覆盖问题是一个公认的n p 完全问题，对它的解决将具有十分广阔的应 用前景，特别是对于受二分图约束的顶点覆盖( c b v c ) 问题在超大规模集成电 路芯片的修复上的运用已相当成熟。但随着芯片集成度的提高，对顶点覆盖的算 法无论在精确度上还是运行时间上都提出更高的要求。而把固定参数算法与受约 束的二分图顶点覆盖问题相结合起来的算法能适应这种要求。 本文通过用把匹配理论的经典理论运用到参数理论与二分图顶点覆盖问题 的结合中，得到时间复杂度只需要0 0 2 6 + 以【8 】的优良结果的算法的一个实例 来证明参数理论在解决n p 完全问题时的有效性，并得出个结论：参数复杂性 算法虽然好用，但也不是放之四海而皆准的算法，只有把f p t - 算法充分与具体 实际问题相结合才能产生出更为优越的结果，这是立足于对具体问题的深入理解 和掌握的基础上的，对具体问题理解越透彻，得到的结果也会更优异。此外，通 过对这一实例的具体分析，也希望更多的人能注意到它的优良特性，更多的人把 参数复杂性理论运用到更多的领域。 关键词：f p t - 算法； m i n - c b v c 问题；m i n f g r a 问题；n p 一完全问题： 顶点覆盖； 匹配理论 f p t - 算法在c b v c 问题中的运用 3 1 0 ，2 0 0 5 a b s t r a c t f p t - a l g o r i t h m s ( f i x e d p a r a m e t e r - t r a c t a b l ea l g o r i t h m s ) i sc o n s i d e r e da p o p u l a r e f f i c i e n ta l g o r i t h m sw h i c hi su s e dt os o l v es e v e r a ln p - c o m p l e t ep r o b l e m s m a n yf p t a l g o r i t h m sw o r ki nt w os t a g e s ：f i r s t ly ，t h ei n s t a n c ei st r a n s f o r m e di n t oa ne q r i v a l e n t o n et h a ti ss m a l l e ri ns i z e t ob es p e c i f i c ，i t ss i z ei sb o u n d e db yaf u n c t i o nt h a t d e p e n d so nt h ep a r a m e t e ro n l y t h i ss t a g ei sc a l l e dr e d u c t i o nt op r o b l e mk e r n e l s e c o n d l y , t h en e ws m a l li n s t a n c ei ss o l v e dr e c u r s i v e l yb ys o l v i n gs e v e r a ld e r i v e d i n s t a n c e sw i t hs m a l l e r , t h er e c u r s i o ne v e n t u a l l yt e r m i n a t e s ( e i t h e rb yf i n d i n ga s o l u t i o no rb yr e a l i z i n gt h a tn os o l u t i o ne x i s t sb e c a u s eo fk o1 t h a ts t a g ei sc a l l e d b o u n d e ds e a r c ht r c e v e r t e xc o v e rp r o b l e mi sar e c o g n i z e dn ph a r dp r o b l e m ，b u ti th a sp r o m i s i n g e x t e n s i v ea p p l i c a t i o n s ，e s p e c i a l l y , i th a sar a t h e rm a t u r ea p p l i c a t i o ni nt h ep r o c e s s i n g o fr e p a i r i n gv l s i ( v e r yl a r g e s c a l ei n t e g r a t i o n ) c h i p sf o rc b v c p r o b l e m w i t ht h e i n c r e a s i n go f t h ed e n s i t yo f c h i p s ，m o r ep r e c i s ea n dr a p i da l g o r i t h m so f v e r t e xc o v e r p r o b l e ma r en e e d e d ，s ot h ea l g o r i t h m sw h i c hc o m b i n ef p t - a l g o r i t h m sw i t hc b v c p r o b l e m c a l ls a t i s f yt h ed e m a n d s f r o mai n s t a n c ew h i c ha l g o r i t h m si st h a tc l a s s i c a lr e s u l t si nm a t c h i n g t h e o r ya n d d e v e l o p e dt e c h n i q u e so fp a r a m e t e r i z e dc o m p u t a t i o na r en i c e l yc o m b i n e da n dg a i ni t s r u n n i n gt i m eb o u n d e db y0 0 2 6 2 + 妇) ，w ec a ns e et h ev a l i d i t yo f t h ep a r a m e t e r i z e t h e o r ya n dt h e r e f o r ed r a wac o n c l u s i o nt h a tf p t - a l g o r i t h m sa r ev e r yg o o d ，b u ti ti s n o te v e r y t h i n g o n l yf u l l yc o m b i n ef p t - a l g o r i t h m sw i t hp r a c t i c ec a r ti tm a k eo u t b e a e rr e s u l t s ，t h ed e e p e ri tc a t lb eu n d e r s t a n d ，t h eb e t t e rw ec a ng e tt h er e s u l t s ， m o r e v e r , a n a l y s i n gt h ei n s t a n c e ，w eh o p em o r ep e o p l ew o u l d n o t i c ei t sg o o dt r a i t ，a n d m o r ep e o p l ep u t p a r a m e t e r i z e dc o m p l e x i t yt h e o r yi n t ou s e i nm o l ef i e l d s k e y w o r d s ：f p t - a l g o r i t h m s ；m i n - c b v cp r o b l e m ；m 1 n - f c r ap r o b l e m ；n p c o m p l e t ep r o b l e m ；v e r t e xc o v e r ；m a t c h i n gt h e o r y f p l 算法在c b v c 问题申的运用 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下( 或 我个人) 进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不合任何其他个人或集体已经发表或撰写过的研究成 果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明 确的说明并表示了谢意。本声明的法律结果由本人承担。 学位论文作者签名：汛 对擞 日 期：2 曲工年3 月f 0 日 关于论文使用授权的说明 本人完全了解昆明理工大学有关保留、使用学位论文的规定，即： 学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布 论文的全部或部分内容，可以采用影印或其他复制手段保存论文。 ( 保密论文在解密后应遵守) 导师鼢晕黼糊：洫翅毖 日 期：兰! ! 生三月 lq 旦 注；此页放在封面后，目录前。 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 1 1 引言 绪论 一个软件系统的性能在很大程度上取决于其内部计算机算法的性能。目前计 算机所做的信息处理问题大致分为一般( t r a c t a b l e ) 问题与难解( i n t r a c t a b l e ) 问 题两类。对于一般计算机问题，人们可以找到有效算法使计算机可以在能够容忍 的时间和空间( 多项式时间和空间) 内解决这些问题。而对于难解问题( 被称为 n p 完全问题或n p h a r d 问题) ，人们很难找到快速有效算法。当被处理问题规 模增大时，计算机的计算量有可能成百倍、成千倍呈指数型地增长，最终在时间 和空间上超出计算机的实际计算能力。几十年来，计算机理论学者和算法专家致 力于寻找对一般计算问题的实时高性能算法和对大规模难解问题的快速算法。 1 2课题研究内容 本课题研究的主要对象是对超大规模集成电路芯片的缺陷修复，而该问题可 转换为受约束的二分图顶点覆盖问题。在超大规模集成电路芯片内部，芯片可以 抽象为一个m n 的阵列，对该阵列进行修复可以归结为用s r 个备用行和s c 个备用列来替换阵列中有缺陷的行和列【l ，2 ，3 】，而这可转换为受二分图约束的顶 点覆盖问题( c o n s t r a i n tb i p a r t i t ev e r t e xc o v e r ，c b v c ) 口，具体内容在论 文后面章节有详细阐述。 而顶点覆盖问题是最早被证明为n p 完全的难解问题之一，从它产生的那一 天开始人们便对它投入了大量的精力来研究顶点覆盖问题的算法，试图能找到一 种快速，高效的算法，能在较短的时间复杂度内找到图的最小顶点覆盖集。 1 3课题的研究现状 1 3 i 国外顶点覆盖问题的研究现状 国外对此问题的发展分两个阶段： 第一阶段：上个世纪七十年代至九十年代中期。 2 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 传统计算方法的局限使得在这个问题上一直得不到突破。这一阶段对顶点覆 盖问题的求解，常用的方法是用近似算法，或者是根据问题的实际情况，提出对 应的启发式算法。这些算法在实际应用中往往能取得较好的效果。但在一些对结 果要求严格，必须得到问题的精确解的应用中，上述算法便不一定能满足要求。 第二阶段：上个世纪九十年代末期至今。 这一突破出现在九十年代末期。b u s s 等人提出了参数计算理论，很好的应用于顶点覆 盖问题的求解上。并提出了第一个固定参数算法，证明了该算法的运行时间复杂度为 0 ( 砌+ 2 2 k 2 m ) 4 】，该算法的时间复杂度随后被d o w n e y 和f e l l o w s 改进为 o ( k n + 2 2 七2 ) 【5 。b a l a s u b r a m a n i a n 教授率先在顶点覆盖问题的精确求解上突破了以2 为 底的指数复杂度。仇提出的新算法证明了顶点覆盖问题可在d ( 砌+ 1 3 2 2 7 1 8 。k 2 ) 的时间 复杂度内被求解【6 1 。不久c h e n 和k a n j 提出了时间复杂度为o ( i m + 1 2 7 1 k 2 ) 的固定参数 算法 7 】。最近，j i a n e rc h e n 和l y a da ，l ：，且f 满足： ( 1 ) 有一个计算f 的多项式时间确定性图灵机： ( 2 ) 对于任意的x ：，x l ln e t 仅当厂( l 2 。 定义：语言l 是n p 完全的当且仅当 ( 1 ) l n p ： ( 2 ) 对于所有l e p 有l 。l 。 如果有一个语言l 满足上述性质( 2 ) ，但不一定满足性质( 1 ) ，则称该语言 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 是n p 难的。所有n p 完全语言构成的语言类称为n p 完全语言类，记为n p c 。由 n p c 类语言的定义可以看出它们是n p 类中最难的问题，也是研究p 类与n p 类的 关系的核心所在。 定理2 1 设l 是n p 完全的，则 ( 1 ) l p 当且仅当p = n p ： ( 2 ) 若l 。l i ，且上1 p ，则厶是n p 完全的。 证明：( 1 ) 若p = n p ，则显然l p 。反之，设l p ，而l n p 。则l 可在多 项式时间p ，内被确定性图灵机m 所接受。又由l 的n p 完全性知lo c 。l 。，即存 在映射f ，使l = f ( l ) 。 设n 是在多项式时间p ：内计算f 的确定性图灵机。我们用图灵机m 和n 构 造识别语言厶的算法a 如下： 1 ) 对于输入x ，用n 在p ：( 1 x 1 ) 时间内计算出f ( x ) ： 2 ) 在时间l f ( x ) i 内将读写头移到f ( x ) 的第一个符号处： 3 ) 用m 在时间p ( f l x l ) 内判定，( 曲l 。若，( 砖l ，则接受x 否则拒绝x 。 上述算法显然可接受语言，其计算时间为p ：( 1x 1 ) + i f ( x ) i + p l ( ，i x i ) 。由 于图灵机一次只能在一个方格中写人一个符号，故i ，( x ) i 矧xi + p ：( ix1 ) 。因此， 存在多项式r 使得p ：( 1 x i ) + l f ( x ) i + p ，( ，ix 1 ) r ( x ) 。因此，l 。pa 由l t 的任 意性即知p = n p 。 ( 2 ) 我们只要证明对任意的f n p ，有l 。c 。l l 。由于l 是n p 完全的，故存 在一个多项式时间变换f 使l = f ( l ) 。y , f l j yl * 。三。，故存在一多项式时间变 换g 使厶= g ( 二) 。因此，若取f 和g 的和复合函数h = g ( f ) ，则厶= h ( l e 易知 h 为一多项式。因此三o c 。l f 。- 由l 的任意性即知l i n p c 。 从定理2 1 的( 1 ) 可知，如果任一n p 完全问题可在多项式时间内求解，则所 有n p 中的问题都可在多项式时间内求解。反之，若p n p ，则所有n p 完全问 昆明理工大学硕士论文f p t - 算法在c b v c 问题中的运用 题都不可能在多项式时间内求解。 定理2 1 的( 2 ) 实际上是证明问题的n p 完全性的有力工具。一旦建立了问题 l 的n p 完全，性后，对于l ，n p ，只要证明问题l 可在多项式时间内变换为厶， 即l o c 。l 。，就可证明厶也是n p 完全的。 2 3 2一些典型的n p 完全问题 定理1 所提供的证明一个问题的n p 完全性的方法只有在有了第一个n p 完 全问题之后，才能使用。获得“第一个n p 完全问题”称号的是布尔表达式的可满 足性问题。这就是著名的c o o k 定理。 定理2 2 ( c o o k 定理) ：布尔表达式的可满足性问题s a t 是n p 完全的。 证明在这里略去，详细内容可参见【9 。 c o o k 定理的重要性是明显的，它给出了第一个n p 完全问题。使得对于任何 问题q ，只要能证明q n p 且s a t o c 。q ，便有q e n p c ，这里n p c 就是指n p 完全问 题。所以，人们很快就证明了许多其它问题的n p 完全性。这些n p 完全问题都是 直接或间接地以s a t 的n p 完全性为基础而得到证明的。由此逐渐生长出一棵以 s a t 为树根的n p 完全问题树。下图是这棵树的- - d 部分。其中每一个结点代表 一个n p 完全问题，该问题可在多项武时间内变换为它的任- - ) d 予结点表示的问 题。实际上，由树的连通性及多项式在复合变换下的封闭性可知，n p 完全问题 树中任意结点表示的问题可以在多项式时间内变换为它的任一后裔结点表示的 问题。目前这棵n p 完全问题树上已有几千个结点，并且还在继续增长。 1 4 昆明理工大学硕士论文 f p t 一算法在c b v c 问题中的运用 其中，s a t ： c n f s a t ： 3 一s a t ： c l i q u e ： v e r t e x c o v e r ： s u b s e t s u m ： h a m - c y c l e ： t s p ： 图1部分n p 完全问题树 布尔表达式的可满足性问题 合取范式的可满足性问题 三元合取范式的可满足性问题 团问题 顶点覆盖问题 子集合问题 哈密顿回路问题 旅行售货员问题 昆明理工大学碗士论文 f p t 算法在c b v c 问题中的运用 第三章二分图顶点覆盖在芯片修复中的运用 由于顶点覆盖问题本身是图论中的一个经典问题，在算法中用到了大量的图 的知识。所以我们在正式介绍c b v c 算法前先介绍一些图的基本概念。 3 1 图的基本概念 所谓图( g r a p h ) 是指有序二元组g = ( v ，e ) ，其中v 非空称为顶点集 ( v e r t e x - s e t ) ，v 中元素称为顶点( v e r t e x ) ；e 称为边集( e d g e - s e t ) ，e 中元素称为 边( e d g e ) ，e 刻划了边与顶点之间的关联关系，若e 中v x v 元素全是无序对， 则所构成的图称为无向图( u n d i r e c t e dg r a p h 或g r a p h ) ，记为g 。若e 中y 矿元 素全是有序对，则所构成的图称为有向图( d i g r a p h ) ，记为d 。e 中元素称为有 向边。设a e ( d ) ，则存在x ，y v ( d ) ，和有序对( x ，y ) v x v 使e ( a ) = ( x ，y ) 。a 称为从x 到y 的有向边。x 称为a 的起点( o r i g i n ) ，y 称为a 的终点 ( t e r m i n u s ) ，起点和终点统称为端点( e n d v e r t i c s ) 。设ee ( g ) 。则存在x ，y v ( g ) 和无序对( x ，y ) v v 使e ( e ) = ( x ，y ) 。由于无序对 x ，y ) 和 y ，x ) 表示同一个元素。所以通常简记v ( e ) - - x y 或y x 。e 称为连接x 和y 的边( e d g e c o n n e c t i n gxa n dy ) 。 图论中大多数定义和概念是根据图的图形表示提出来的。例如，边与它的两 端点称为关联的( i n c i d e n t ) 与同条边关联的两端点或者与同一个顶点关联的 两条边称为相邻的( a d j a c e n t ) 。两端点相同的边称为环( 1 0 0 p ) 。有公：共起点并 有公共终点的两条边称为平行边( p a r a l l e le d g e s ) 或者称为重边( m u l t i - e d g e s ) 。两 端点相同但方向互为相反的两条有向边称为对称：逆2 ( s y m m e t r i ce d g e s ) 。 设( v ，e ) 是图，v 中元素的个数v 和e 中元素的个数，即v = t v l 积e = e 分别称为该图的顶点数或阶( o r d e r ) 和边数( s i z e ) 。 设g 是无向图。x v ( g ) 的顶点度( v e r e xd e g r e e ) 定义为g 中与) c 关联边的 数目( 一条环要计算两麴，记为d 。( 砷或d e g ( x ) 或d e e e l ) 。 顶点度为d 的顶点称为d 度点( d d e g r e ev e r t e x ) 。零度点称为孤立点( i s o l a t e d v e r t e x ) e 1 2 ，1 3 1 6 昆明理工大学硕士论文f p t - 算法在c b v c 问题中的运用 3 2 二分图顶点覆盖在芯片修复中的运用 随着超大规模集成电路芯片集成度的增加，在生产过程中生产出有缺陷的芯 片的机率也大大增加。为了提高芯片成品率，人们提出了许多相关算法，对于使 用一些备用行和备用列来修复可修复陈列的算法尤其引入注目，这些算法可参考 文献 1 4 、1 5 、1 6 、1 7 、1 8 、1 9 、2 0 。 一个典型的可修复陈列是由一个矩形陈列加上一系列备用行和一系列备用 列组成，如图3 1 和图3 2 所示可修复陈列是一个由相同元素组成的7 行7 列的 陈列加上三个备用行和三个备用列共同构成。一个缺陷元素可以通过用一个备用 行或个备用列来代替有缺陷元素的这行或这- - n 来修复的。 大体上来说，在可修复阵列中备用行和备用列的数目远小于可修复阵列的行 数和列数，修复一个阵列的成本与取代缺陷的行数和列数成正比。因此，能够使 用最小数目的备用行和备用列来修复缺陷元素的算法是令人满意的算法。此外， 由于备用行和备用列的数目都是有限的，我们也需要先规定好在替换中的备用行 和备用列的数目的限制。 定义3 1 在可修复陈列中的最小错误覆盏( b l l n f c r a ) 给定一个有缺陷元素的有着n 行m 列的矩型陈列a 和两个给定的正整数k ，和 k ，有这样两种结果：要么我们能够找到一个包含最小行数和列数的最小集r ， 使得每一个缺陷元素都包含在或者是r 的一个行中或者是r 的一个列中，而这r 中的行数和列数被k ，和k ：分别限制，要么这样的集合不存在。 m i n - f c r a 问题是由n h a s a n 和c l l i u 在 9 中首先提出，同时在同一文章 中他们还讨论了这一问题的复杂性。这一问题已经公开了几十年了。许多关于 m i n - f c r a 问题的算法及其变化在 1 4 ，1 5 ，1 7 ，1 8 ，2 0 论文中可以看到。尤其在 b l l n f c r a 问题中f c r a 被证明是n p 一完全问题，要寻找到最小的集合r 并不是必 须的。此类算法绝大多数是宿发式的并且不能保证能找到最小集合r 。证明f c r a 是n p 一完全问题是基于这样一个事实：m i n f c r a 问题等同于在二分图上受约束的 最小顶点覆盏问题( m i n c b v c ) ，并且也是基于从团问题到m i n c b v c 问题的化简 的基础上的，这回答了h a s a n 和l i u 在1 9 8 8 1 4 中提出的公开问题，对此我们 昆明理工大学硕士论文f p t 一算法在c b v c 问题中的运用 将在后面详细讨论。 图3 1 s c 3 2 2 二分图上受约束的顶点覆盖 图3 之 设a 是一个有着n 行和m 列的矩型可修复陈列。假设a 包含缺陷元素。一个 a 的错误覆盖包括一个由a 中若干行组成的集合s ，和一个由a 中若干列组成的集 合足，使得a 中的每一个缺陷元素要么在s ，中的一行，要么在只中的一列( 或 者是即在s ，中一行又在足中列) 。如果其错误覆盖包括最小数目的行和最小数 量的列则我们称其为a 的最小错误覆盖。假设现在有k ，个备用行和也卜备用列， 则在可修复陈列a 中的最小错误覆盖( m i n f c r a ) 面临两个结果，要么找得到a 中的个包括最多k l 行最多k ：列的最小错误覆盖，要么报告这样的最小错误覆 盖不存在。 在二分图上j l i i n f c r a 问题能够很容易地改变成为一个受约束的最小顶点覆 盖问题。在一个圈中的顶点集c 是一个顶点覆盖如果图中的每一条边有至少一个 顶点在c 中。这顶点覆盖是最小顶点覆盖如果在图中所有的顶点覆盖中它包含最 小数目的顶点。一个图g = ( 矿，e ) 二分图如果其顶点集v 被分成两个集合u ( 上 部分) 和l ( 下部分) ，使得g 中的每一边的一个端点在u 中而另一个端点在l 中。一个二分图通常写成g f u l ，e ) 形式以显示其顶点是二分的。顶点集u 和l 分别被称为图g 的u 一部分和l 一部分。一个顶点被称为u 一顶点( 卜顶点) 如 果它在图g 的u 一部分( l - 部分) 。 昆明理工大学硕士论文f p t - 算法在c b v c 问题中的运用 图3 - 3 举一个m i n f c r a 问题的例子，一个n 行m 列的可修复陈列a 及两个正整数 k ，和k 。，我们可以构造一个二分图g 。= ( u u 厶e ) ，其中u = “，“。) ， l = v 。，v 。) ，如果有一条边与坼和u ，相连，当且仅当在陈列a 中第i 行和第j 列的那个元素是有缺陷的，由图3 3 可见。容易看出由 “，“。) 中的k t 个点和 v ，v ，) 中的k 2 个顶点构成的一个顶点集c 是图q 的一个覆盖集当且仅当相应 的k 行和k 2 列构成阵列a 的一个覆盖。尤其，顶点集c 是图吼的一个最小顶点 覆盖当且仅当a 中相应的行和列构成陈列a 的一个最小覆盖。因此，m i n f c r a 问题能被正式地简化为以下图问题： 定义3 2 在二分图上受约束的最小顶点覆盖( m i n - c b v c ) 给定一个二分图g = ( u u l ，e ) 和两个正整数七。和k l ，共有这样两个结果： 要么找到图g 的一个有着至多t 。个u 一顶点和至多k 1 个l 一顶点的最小顶点覆盖， 要么报告没有这样的顶点覆盖存在。 事实上，很容易看出在一定意义上m i n f c r a 问题和m i n c b v c 是等同的，从 m i n f c r a 例子到m i n c b v c 例子之间有一个简单的映射，对一个问题的解决意味 着相应的另一个问题也得到解决。 3 2 3 m i n f c r a 是n p 。完全问题 h a s a n 和l i u 1 4 对m i n f c r a 问题的复杂性进行过讨论。在这部分，我 们对m i n f c r a 问题是n p ：完全问题给出精确的答案。 因为m i n 。f c r a 问题和m i n c b v c 问题是等同的，我们只需证明 m i n c b v c 问题是n p 。完全的即可。很容易看出m i n - c b v c 问题是n p 问题： i 9 昆明理工大学硕士论文f p t - 算法在c b v c 问题中的运用 给出m i n c b v c 问题的一个实例 ，这里g = ( u u 厶e ) 是一个二分图， 简单假设在图g 中有不超过吒个u 一顶点和不超过矸个l 一顶点，则检查是否他们 能形成一个最小顶点覆盖( 表明一个二分图中的个最小顶点覆盖能在o ( 聊 ) 时间内被计算出来【2 l 】。) 接下来，我们通过把n p - 完全问题中的团问题化简为m i n c b v c 问题而显 示m i n c b v c 河题是n p 一难的。在图g 中的大小为q 的一个团是g 中q 个顶点 的一个集合q ，使得在q 中每一对顶点都是相邻的。 是团问题的一个实 例，这是g 是一个图，q 是一个整数，问是否图g 包含一个大小为q 的团。团 是一个众所周知韵n p 完全问题【2 2 】。 设g = ( u u 三，e ) 是有着一个完全匹配的一个二分图，图g 是基本的如果g 中的每一条边都被包含在g 中的一个完全匹配中。由此可知一个基本的二分图 正好有两个最小顶点覆盖，分别称为u 和l ( 见 2 u ，定理4 1 1 ) ，一个基本二 分图的一个例子是一个有着偶数长度 q ，吒，) 的一个简单环，在其中只有两 个最小顶点覆盖 v i ，b ，v 2 ) 和 v 2 ，v4 ，v 2 ) 。 定理3 1m i n - c b v c 问题是n p - 完全问题 证明：从以上的讨论可知，保须证明n p 完全的团问题能在多项式时间内化 简为m i n c b v c 问题即可。 设 是一个团问题的实例，这里g - - 是一个有着n 个顶点和m 条边的简单图，q 是一个正整数。我们构造一个m i n c b v c 问题的一个例子 ( 嚣，k ，巧 ，这里b = ( u u l ，e 口) 是个：二分图，吒，两是非负整数eg 中每一 个顶点和b 中的一个顶点块风相关联组成一个顶点”。u ，一个顶点v ，上和 - 条l i i ( u 。，v 。) ，g 中每一条边e 与b 中的一个边块口。相连接，b 是有着 2 n 十2 个顶点的一个环，这个环的顶点二分为够。，上。) ，这里u 。u 有h + 1 顶点， l ，e 工有n + 1 个顶点。最后，如果g 中的一个顶点w 是g 中一条边e 的一个端 点，我们从顶点块b 。中的u 一顶点“。到边块忍中的任意l 一顶点增加一条新的 昆明理工大学硕士论文 f p t 算法在c b v c 问题中的运用 边。这种类型的边称为“块间边”。值的注意的是没有块间边既和一个顶点块中 的一个l 广顶点相连，又和一个边块中的u 顶点相连。这完成了图b 的结构。容 易看出图b 是二分图，并且有一个n + 聊+ 1 ) 条边的完全匹配。因此，b 中一个 最小顶点覆盖正好包含n + m ( n + 1 ) 个顶点。现在令蚝= q + g ( g 一1 ) ( n + 1 ) 2 ， = h + m ( n + 1 ) 一h 。m i n - c b v c 问题的实例 定能在多项式时间内由 团问题的实例 所构造。 二分图b 的每一个最小顶点覆盖包含每一个顶点块中的至少一个顶点( 因 为在一个顶点块中的两个顶点被一条边所连接) 并且也包含每一个边块中的至少 + 1 个顶点( 因为一个边块有2 h + 2 个顶点和一个完全匹配) 。现在，由于图b 有正好n 个顶点块和m 个边块，b 的一个最小顶点覆盖有正好开+ m ( n + 1 ) 个顶点， 我们能推出在每一个顶点块中每一个最小顶点覆盖包含正好个顶点，在每一个 边块中包含正好刀+ 1 个顶点。这样，一个最小顶点覆盖的交集和一个块( 要么是 一个顶点块要么是一个边块) 必然是这个块的一个最小顶点覆盖。 b 中顶点块和边块是基本二分图。因此，每一个块有正好两个最小顶点覆盖， 称为这个块的u 部分和l 一部分。因此，图b 的每一个最小顶点覆盖由每一个块 的要么是u 一部分要么是l 一部分( 但不是两者同时) 构成。 现在我们准备证明原图g 有一个大小为q 的团当且仅当二分图b 有一个有 着最多k 个u 顶点和最多矸个l 一顶点的最小顶点覆盖。 设q 是图g 中有着q 个顶点的一个团。我们对二分图b 构造一个有着蚝个 u 一顶点和砰个l - 顶点的最小顶点覆盖。设c 口是b 中的一个集合，c 口是由相对 应于团q 中的q 个顶点与q ( q 一1 ) 1 2 条边的q 个顶点块与q ( q 一1 ) 2 个边块的u 部分和顶点块与边块的剩下l - 部分组成。集合c 0 共有7 + m ( n + 1 ) 个顶点，这正 是b 的最小顶点覆盖的规谋，在b 中有着k = 孽+ 口( g 一1 ) ( n + 1 ) 2 个u 一顶点和 一= n + m ( n + 1 ) - x , 个k 顶点。因此，这足以显示集合c 0 是b 的一个顶点覆盖。 由于或者是块的u 部分，或者是块的l 部分被完全包含在集合g 中，所以 2 l 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 在相同的块中每条边连接的两个顶点被c 0 所覆盖。现在考虑一条块阃边e ，e 把 一个顶点块b 。的u - 顶点和一个边块毽中的一个l - 顶点相连，这里w 是图g 中 边e 的一个端点。如果边e 不在团q 中，那么b e 的l - 部分在集合c d 中，这样边 e 被c 口所覆盖a 如果边e 在团q 中，那么吼的u - 顶点在c o 集合中，这样边p 被c 口所覆盖。由于在二分图b 中只有仅有的边，我们推断出集合c o 是图b 的 有着k 个u 一顶点和k 个l 一顶点的一个最小顶点覆盖。这样，图o 中一个大小为 q 的团意味着二分图b 的有着k 个u 一顶点和_ 个l - 顶点的一个最小顶点覆盖。 现在假设二分图b 有有着吒个u 一顶点和坼个l 一顶点的一个最小顶点覆盖 c 。因为k = q + q ( q 一1 ) ( n + 1 ) 2 和带着每个块的c 的交集，要么正好是块的u - 部分，要么正好是块的l 一部分，我们推出顶点覆盖c 包含正好q 个顶点块的 u 一部分和g 国一1 ) 2 个边块。令只是b 中这些块的集合，是图g 中q 个顶点 的顶点集，与疋中q 个顶点块相对应，疋是g 中有着g ( q 1 ) 2 条边的边的集合， 与& 中q ( q 一1 ) ，2 个边块相对应。考虑s 。中的一个边块b 。，这里e = 【w l ，w 2 】是图 0 中的一条边。从顶点块巩，的u 一顶点到边块眈中的一个l 一顶点有一条块间 边，从顶点块玩：中的u 一顶点到边块曰。中的一个l 一顶点又有一条块间边。因为 在边块皿中没有l 顶点，在顶点覆盖c 中，顶点块巩，和风：的u 一部分必然在c 中。因此，顶点和w 2 在集合砭中。现在，在集合e 。中的g ( g 一1 ) 2 条边中的 每一条边在集合匕中都有两个端点。而集合圪只有q 个顶点。我们推出在图g 中顶点集k 和边集e 必然能形成一个大小为q 的团。这样，在二分图b 中有着k 个u 顶点和矸个l 。个顶点的一个最小顶点覆盖意味着在原图g 中的q 个顶点的 一个团。 这就完成了团问题在多项式时间内化简为m i n - c b v c 问题的证明。因此，m i n c b v c 问题是一个n p - 完全问题。# 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 第四章固定参数算法 我们所介绍的复杂性理论迄今为止主要是解决“是非”判定性问题。参数复 杂性理论就象其名字暗示的一样是用参数来作“是与非”的判定。它试图辨别出 当把那些参数在其中没有起什么作用的问题参数化以后，能有好的运行效果的问 题。 4 1固定参数算法理论 4 1 1 参数问题 一个判定性问题通常的形式是这样的：“给定一个实例i ，判断i 是否有性 质p ”。通过给性质p 一个限制，我们得到问题的形式为：“给定个实例i ，判 断i 是否具有性质p ，这里p 依赖于k ( 受限制于k ) 。”这很容易让人想到具有 这种形式的问题的自然例子，即“是否一个图g 有一个大小为k 的控制集 ( d o m i n a t i n gs e t ) ”或者“是否一个图g 有一个大小为k 的独立集( i n d e p e n d e n t s e t ) ”。此类问题就被称为参数问题： 定义4 1 参数语言 一个参数语言三被定义为三。如果 在一个参数语言中三 中，我们就称k 为参数。参数可以是任意的类型，但通常参数都限制在自然数n 的范围内。这样参数问题就可以表示为三+ n 。对一个固定的k ，我们把 = ( i 上 称为三的第k 部分( s l i c e ) 4 1 2 思想 对于参数问题，我们将试图找一个比较好的算法。我们已经知道，对于n p 完全问题而言，参数取一切值我们都不能得到一个完全的多项式算法，用野蛮搜 索策略很容易得至t j o ( n ) 算法，但是，当我们要么增加主要的输入要么增大参数 时，这些算法通常是无意义的，因为其运行时间会( 爆炸) c e x p l o d e s ”) 。 昆明理工大学硕士论文 f p t - 算法在c b v c 问题中的运用 然而，我们跳出思维局限看问题，找到其运行时间为f ( k ) n0 ( i 的算法是可能 的。这类算法是十分有意义的，因为当增加主要的输入规模以后，其算法的运行 时间只会导致多项式级别的增长。我们甚至可以宣称，把参数的值固定以后，相 关问题能得到多项式时间算法。 这个复杂性理论听起来象是一个巨大的突破。事实上，这确实是一个巨大突 破，但这并不意味着我们对指数级计算有什么突破，因为f ( k ) 是指数不变的， ( f ( k ) 的指数部分是不变的) ( 只要p n p ) 。也不是所有的问题都可用这种方法， 所以我们可把n p - 完全问题作个分类，可以转化为f ( k ) no ( 1 类型的算法的问题都 称作固定参数易解类型( f i x e dp a r a m e t e rt r a c t a b l e ，即f p t ) 。 4 1 3 固定参数易解类型f i x e dp a r a m e t e rt r a c t a b i l i t y 一个固定参数易解类型的问题被简称为“参数问题”，记为“f p t ”，如果解 决此问题的算法及其运行时间和问题的主要输入没有指数相关性( 不是指数级 的) 。 定义4 2 固定参数类型f p t 个参数语言三z * x n 是固定参数类型f p t 有一个算法a ，一个常数口和一个函数f ：n n s 乜 ( a ) 彳( ) 的运行时间至多为m ) l x l 。 ( b ) l 亡4 ( ) = 1 固定参数复杂性方法( f p t ) 已经被认为是处理n p 一难解问题的一种方法，并 且事实上它也是这样的。些闯题用f p t 算法来解决是非常好用的，当参数取值 较大时算法依然有效。其中一个最好的例子是n p 一难的顶点覆盖问题，目前所知 的最好的运行时间是0 ( 1 2 7 1 + 女叻 7 ，当k 取到2 0 0 的时候算法仍然有效。 昆明理工大学硕士论文 f p t 一算法在c b v c 问题中的运用 4 2固定参数算法的技巧 4 2 1 介绍 当我们设计f p t 问题的算法时我们必须考虑这和多项式问题的算法设计不 同。通常，我们会避免野蛮搜索方法，因为我们知道这往往会导致指数时间复杂 度的解。我们用f p t 方法处理问题时。问题的某些部分将不可避免地也会陷入指 数级运算时间，以其把注意力集中在避免指数运算上，不如限制指数的增长。 因为f p t 是一个相对较新的领域，关于决定用什么算法技巧和这些算法技巧 能做什么等方面还有很多工作要做。但目前大量的f p t 算法是由二个步骤组成 4 4 ：首先，把实例转化为一个较小的等价体。具体来说，其大小由只依赖于参 数的一个函数所限制。这一步称为化简问题核心。其次，通过用一些更小的参数 解决一些导出子例，把简化了的问题用递归的方式来解决。因为在递归调用中的 那些参数更小，所以递归最终能完成( 要么找到一个解，要么了解到由于k k 的所有顶点。如果我们不选择度 k 的 一个顶点，那么我们必须选择它的比k 更多的邻接顶点，那样则顶点覆盖变的太 大了。 现在设s = v v j a e g o , ) 砖。如果蚓 i 则我们拒绝，因为s 代表一个顶点 集，这个顶点集的顶点必然属于g 的任意一个女顶点覆盖中。设足= k - t s l ek 是我们已经选择到我们的顶点覆盖的顶点数。 设h = g 【矿一s 】，是在矿一s 上的导出子图，可能包含0 度顶点e 这些顶点 不能包含在任意的顶点覆盖中，所以要从舟中去掉。设 抒= 1 4 一 z t t l d e g ( x ) = o ) 。 目中的顶点限制为度sk 的顶点。现在我们从图中所选的任意一个顶点都不 能覆盖和其它顶点相连的超过k 条的边。因为我们不能选择超过k 的顶点，我们 不能覆盖有着超过膏( 七十1 ) 个顶点的任意图，这里旷k 。即：如果i 日1 j ( _ j + 1 ) 则拒绝。 问题化简为找在规模是( + 1 ) 的一个图中的一个k 顶点覆盖。这可以通过 昆明理工大学硕士论文f p t - 算法在c b v c 问题中的运用 检测( ：卜d 种可能的顶点覆盖中的每一种雨在。c t ，时间内完成