（计算机科学与技术专业论文）覆盖问题的参数算法研究.pdf

；hi = ，二： r e s e a r c ho nt h ep a r a m e t e r i z e da l g o r i t h m sf o rc o v e r p r o b l e m s s p e c i a l i t y ：q 幽巳堕! 金 s 堡i 金d 堡金g d d ! 金堡b d q i q g y m a s t e rd e g r e e c a n d i d a t e = 一盥曼西坠坠l i s u p e r v i s o r = p r o f j i a n x i nw a n g s c h o o lo fi n f o r m a t i o ns c i e n c ea n de n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a ，h u n a n ，p r c h i n a 52舢09 mi舢7m j l洲y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：垄兰生一一日期：卫年月堕日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 硕士学位论文摘要 摘要 覆盖问题是计算几何和组合优化领域中的一类重要的难解问题， 对此类问题的研究不但具有重大的理论意义，而且在生物计算、电路 设计、网络选址、工艺流程分析等应用领域具有许多重要的实际意义。 人们从实际应用中抽象出了许多的覆盖问题，如顶点覆盖问题、树覆 盖问题、超平面覆盖问题、集合覆盖问题等。本文主要对超平面覆盖 问题和基于保证值的完美匹配图中顶点覆盖问题进行了深入的研究。 对于超平面覆盖问题，本文首先通过深入分析直线覆盖问题( 超 平面覆盖问题的一个特例) 的结构特征，提出了一个时间复杂度为 d ，- c ( ( o 7 3 6 k ) b i 拘确定性的参数算法，较大地改进了以前最好的时间复 杂度为o * ( ( k 2 2 ) 2 的算法。更一般地，我们还提出了关于超平面覆 盖问题的确定性的参数算法，其时间复杂度为0 木( ( 娴! ( ( d ! ) ! ) ) ，较 之前的时间复杂度为d ，c ( 秽川) ) 的算法亦有较大改进。 对于完美匹配图中基于保证值的顶点覆盖问题，已有相关文献提 出了一个时间复杂度为d 木( 1 5 七) 的固定参数算法。本文对此算法作了 进一步的改进，其整体思路是首先采用迭代压缩技术将原问题转化为 求一个特殊的具有完美匹配的k 6 n i g 图上的最小顶点覆盖问题，然后 将后者进一步转化为参数化2 a s l a s a t 问题的一个变种问题 ( k p m 2 一a a s a t 问题) ，最后，通过深入分析问题的结构特征，我 们采用分枝搜索技术和隐含参数技术求解k p m 一2 a a s a t 问题。整 个算法的时间复杂度为d 水( 9 勺，较之前最好结果有较大改进。 本文最后对上述两个问题的研究工作进行了总结，并对今后的相 关研究工作做了简要的阐述。 关键词超平面覆盖问题，完美匹配，顶点覆盖，n p 完全性理论，固 定参数算法 p r e v i o u sb e s tr e s u l t0 木( 艘h 1 ) f o rt h ea b o v eg u a r a n t e ev e r t e xc o v e rp r o b l e mo ng r a p h sw i t h p e r f e c tm a t c h i n g ，t h e r ee x i s t s af i x e dp a r a m e t e r i z e da l g o r i t h mw i t h r u n n i n gt i m eo 木( 15 勺w ep r e s e n ta ni m p r o v e da l g o r i t h m ，t h em a i ni d e a o fw h i c hi sa sf o l l o w s f i r s t l y ，w e ，u s i n gi t e r a t i v ec o m p r e s s i o nt e c h n i q u e ， t r a n s f o r mt h ep m - - a g v - - v cp r o b l e mt oas p e c i a lv e r t e xc o v e rp r o b l e m o nk 6 n i gg r a p hw i t hp e r f e c tm a t c h i n g ；l a t e r ，w et r a n s f o r mt h el a t t e rt oa v a r i a t i o no ft h ep a r a m e t e r i z e d2 - a s l a s a tp r o b l e m ( k p m 一2 一a a s a t p r o b l e m ) ；f i n a l l y ，t h r o u g hf u r t h e ra n a l y z i n gt h es t r u c t u r eo ft h ep r o b l e m w e ，u s i n gb r a n c ha n ds e a r c hm e t h o da n di m p l i c i tp a r a m e t e rt e c h n i q u e ， p r o v i d eap a r a m e t e r i z e da l g o r i t h mf o rt h ek p m 一2 一a a s a tp r o b l e m t h e t o t a lc o m p l e x i t yo fo u ra l g o r i t h mi so 木( 9 勺，i m p r o v i n gt h ep r e v i o u sb e s t a l g o r i t h m f i n a l l y ，t h es t u d yw o r ko nt h ep r o b l e m s ，m e n t i o n e da b o v e ，i s s u m m e d u pa n ds o m er e l a t e df u t u r er e s e a r c h e sa r ep r o p o s e db r i e f l y k e yw o r d s h y p e r p l a n e - c o v e rp r o b l e m ，p e r f e c tm a t c h i n g ，v e r t e x c o v e r ，t h e o r yo fn pc o m p l e t e n e s s ，f i x e dp a r a m e t e r i z e da l g o r i t 硕士学位论文 第一章绪论 1 1 研究背景。 1 2 研究现状。 1 2 1 参数计算与复 1 2 2 参数算法设计 1 2 3 参数算法分类 1 3 研究内容一6 1 3 1 参数化超平面覆盖问题f p t 算法的研究6 1 3 2 完美匹配图中基于保证值的顶点覆盖问题f p t 算法的研究7 1 4 研究意义。7 1 5 论文组织8 第二章超平面覆盖问题的固定参数算法9 2 1 引言9 2 2 直线覆盖问题一l o 2 2 1 相关性质和推论1 0 2 2 2 直线覆盖问题的算法1 1 2 2 3 算法l c a 正确性证明和时间复杂度分析1 5 2 3 超平面覆盖问题17 2 4 小结2 0 第三章完美匹配图中基于保证值的顶点覆盖问题的固定参数算法2 l 3 1 引言一2 1 3 2 相关术语和问题的定义2 3 3 2 1 有关图的一些术语的定义2 3 3 2 2 有关可满足性问题( s a t ) 的一些术语的定义2 4 3 2 3 相关问题的定义2 6 3 3p p m k v c 问题的转化2 7 3 3 1 转化过程t r a n s f e r l 2 7 3 3 2 转化过程t r a n s f e r 2 2 9 3 4p m k 2 a a s a t 问题的求解31 3 4 1 与p 2 a a s a t 问题有关的引理和定义一3 1 3 4 2p m k - 2 - a a s a t 问题的求解算法3 2 3 5p m a g v - v c 问题的求解3 5 硕士学位论文 目录 3 6 小结。3 7 第四章结束语3 8 4 1 研究工作总结3 8 4 2 进一步研究工作展望3 9 参考文献4 1 致谢4 8 攻读硕士学位期间主要的研究成果4 9 v 硕士学位论文 1 1 研究背景 随着现代工业、现代交通运输的迅速发展以及各研究领域科研活动的深入展 开，在许多应用中出现了大量的n p 难解的计算问题。而在n p 完全性理论【l 】中， 一个计算问题一旦被证明是n p 难解的，则这一问题被认为是无法用现代计算机 求解的问题。然而，所有这些应用中的n p 难解问题是必须解决的问题，因此自 n p 完全性理论发展以来，人们提出了一系列实际解决n p 难解问题的方法，如 启发式算法【2 】【3 】、近似算法【4 j 【5 】、随机算法【6 】【7 1 等。但这些算法都存在明显的不足： 启发式算法对于解的质量难于评估；近似算法只能得到近似解无法得到精确解， 甚至许多问题也难于近似；而随机算法的成功与否依赖于问题实例的概率分布。 正因为如此，人们急切需要新的方法来处理这些n p 难解问题。 二十世纪末，以d o w n e yr 和f e l l o w sm 为代表的计算机理论专家首次提出 了参数复杂性的概念，并在其专著参数复杂性【8 】牛系统地阐述了参数计算与 复杂性理论，标志着参数计算与复杂性理论的诞生。自从参数计算与复杂性理论 的诞生以来，它表现出了极强的生命力。世界上许多的计算机理论专家把自己的 研究重心转移到参数计算与复杂性理论的研究中，在许多的关于理论计算机科学 的顶尖国际期刊和国际会议中，发表有关参数计算与复杂性理论的论文所占比重 越来越大。更重要的是大量的与参数计算直接或间接相关的研究结果已发表在理 论计算机科学之外的领域的期刊和会议上，例如数据库系统、芯片设计、计算生 物学、人工智能、密码学等【9 。1 5 】。自从2 0 0 0 年起，本领域已成功举办了多次关 于参数计算理论的国际会议。关于参数计算算法和理论的特刊也陆续在著名的国 际期刊如( j o u r n a lo fc o m p u t e ra n ds y s t e ms c i e n c e s ) ) ，t h e o r e t i c a lc o m p u t e r s c i e n c e ) ) ，( t h e o r yo fc o m p u t i n gs y s t e m s ) ) 上发表。在十几年的时间里，参数 计算与复杂性理论得到迅速发展和壮大，很快成为理论计算机科学的一个重要分 支。 作为一种新的处理n p 难解问题的手段，参数计算与复杂性理论试图从另一 个角度着手，解决大量的实际应用中出现的n p 难解问题。该理论的关键思想是 根据实际应用的实际情况，将所给n p 难解问题参数化，而所取参数在实际应用 中只在一个较小的范围内变化，从而充分利用“小参数 这一特殊性质，快速解 决这一类实际应用中出现的n p 难解问题。当把所给的n p 难解问题参数化，此 硕士学位论文 第一章绪论 参数问题的每个实例就具有瓴胗的形式，其中x 是原问题的实例，k 是参数。 若k i ) ，如果c 中存在两点不同时被这k 条直线中的任一 条直线覆盖，那么，c 中所有点必定被这k 条直线中的l c 条分别覆盖( 其中，i q 表示集合c 所含点的个数) 。 证明：可用反证法进行证明。设c = p l ，见，pr c l ，其中p l ，见，p j c j 共一 条直线，且，不是这k 条直线中的一条。不妨设p l ，p 2 不被这k 条直线中的任一 条直线同时覆盖，并且它们分别被这七条直线中的两条直线，l 和如覆盖，则p l ，l ， 硕士学位论文第二章超平面覆盖问题的固定参数算法 p l 譬如，仇如，见盛，l ，所以l l # l ，1 2 l 。考虑点肋，若p 3 l l ，则由性质2 1 有l l = l ， 矛盾! 所以阳叠，l 。同理p 3 诺1 2 。所以点p 3 必被这k 条直线中除，l 和1 2 之外的某条 直线覆盖，不妨设这条直线为1 3 。此时p l e l l ，p l 叠，2 ，p i l l 3 ，仇如，p 2 萑l l ，见诺如， p 3 e 3 ，p 3 萑l l ，p 3 诺1 2 。以此类推，考虑点p 2 ，则称三，为c o m p l e t el i n es e t ；若吲= l ，则称三，为p a r t i t i a ll i n es e t ； 若吲= o ，则称厶为e m p t y _ l i n e _ s e t 。，p f ，劫表示覆盖点a 和历的直线，双妇f ，劫) 表示集合s 中被直线妇b 砌覆盖的所有点的集合。在算法的初始状态，三中k 个 集合l ，( 1 触) 均为e m p t y 。算法主要运用了深度有界搜索树方法，其line s e t 主要的算法思想如下所述。 首先，从s 中任意选取一点( 设为p 1 ) ，将其放入任一e m p t yl i n es e t 中( 不 失一般性，设此集合为三1 ) ，并将其从s 中删除，此时三l 变为p a r t i t i a ll i n es e t 。 然后，从s 中再任选一点( 设为沈) ，由性质2 2 可知，此时需要分别作如 下两种情况进行分支讨论： ( 1 ) 将点忱加入到三l 中，此时陋l i - 2 ，即三l 从p a r t i t i a l l i n e s e t 变为 c o m p l e t e _ l i n e _ s e t 。由性质2 1 可知，p l 和优确定了直线l ( p l ，见) 。所以，此时 可以将s 中被直线j l 覆盖的所有点s ( i ( p l ，p 2 ) ) 从s 中删去，并全部加入到三l 中。 在这种情况下，求解直线覆盖问题的实例( s 七) 就转化为求解实例( s - s ( t ( p l ，优) ) ， 三) 。需要注意的是，实例( s - s ( t q g l ，优) ) ，三) 中的三与实例( s 后) 中的三是不同的； ( 2 ) 将点耽加入到另一e m p t yl i n es e t 中( 设此集合为l 2 ) 并将其中s 中 删除。此时三2 变为p a r t i t i a ll i n es e t ，上中e m p t yl i n es e t 个数减l ，而 尸甜所i a ll i n es e t 的个数加1 。 一般地，当从s 中任选第i 个点p ，( & 尼) 时，需要进行以下分支讨论： ( 1 ) 对于三中的任意p a r t i t i a ll i n es e t ，需将p f 加入到此集合中进行分支讨 论。设三，是上中的某一p a r t i t i a ll i n es e t ，力是厶中的点。若将p t j j f l ) k 至：0 三，中， 硕士学位论文第二章超平面覆盖问题的固定参数算法 由性质2 1 可知，p ，和历确定了直线，p ，劫。此时，将义蛔，劫) 中的所有点从s 中删除并加入弓中，求解直线覆盖问题的实例( s 工) 就转化为求解实例( s - s ( t ( p ， 删，三) 。当然，实例( s - s ( t ( p l ，见) ) ，上) 中的与实例( s 后) 中的三是不同的； ( 2 ) 若三中存在e m p t y _ l i n e _ s e t ，则将肋加入到任一e m p t y _ l i n e _ s e t 中，并 把p f 从s 中删除。 当三中p a r t i t i a ll i n es e t 和e m p t y 的个数均为，且s非空时，算line s e t0 法没有找到一个三，使得萨ir 。三，所以返回“f a l s e ；而当三中 一，o ， p a r t i t i a l l i n es e t 和e m p t y 的个数均不小于，且s为空时，算法已找_line s e t0 到一个三使得弘lr ，所以返回“t r u e 。 一j 5 - j 为了能更清晰的描述算法的执行过程，方便后面的时间复杂度的分析，我们 在图2 1 中给出了与算法算法d b s t l i n e c o v e r 相对应的深度有界搜索树。其中， 方框代表集合，黑点代表元素，即从9 中移入此集合中的点。 图2 - 1 算法d b s t l i n e c o v e r 对应的深度有界搜索树 1 2 硕士学位论文第二章超平面覆盖问题的固定参数算法 通过深入分析直线覆盖问题的结构特性，我们发现其实有些分支是不必要 的。下面对是否需要将点p 加入到集合厶中作进一步的讨论和分析。 ( 1 ) 当厶是p a r t i t i a l l i n e s e t 时，若p 被直线勋f ，劫覆盖( 其中，a 和历 分别是p a r t i t i a ll i n es e tl f 和厶中的点) ，则不需要将p 加入到厶或厶中。否 则，力，p y ，p 三点共一直线，由性质2 1 可知，p f 和易应被同一集合包含。所以， 对于中除厶外的所有p a r t i t i a ll i n es e t ，若存在一p a r t i t i a ll i n es e t 三，使得p 被直线肋，劫覆盖，则不需要把p 加入到厶中。 ( 2 ) 当厶是e m p t y 时，对于三中的任意 三，设line s e t p a r t i t i a ll i n es e t 乃是集合与中的点。因为若要将p 加入到集合厶中，根据推论2 1 可知，义勋，劫) 中的所有点必定被不同的直线覆盖。否则，可以将双，劫) 中的所有点加入到 三，中，但这一情况在( 1 ) 中已经进行了考虑。设n l 是p a r t i t i a ll i n es e t 的个数， n 2 是e m p t y _ l i n e _ s e t 的个数。若三中存在一个p a r t i t i a l l i n e s e t 白，使得双勋，劫) 中点的个数大于n l + n 2 ，则不需要将p 加入到集合厶中。因为若将p 加入到集合 - - k l f 中，算法最终不可能找到一个三，使得s = - u ，_ l ；。 在图2 2 中，函数j u d g e ( s , l ，p ，o 描述了是否需要将p 加入到集合厶中的判 断条件。 图2 - 2 函数j u d g e 下面给出关于直线覆盖问题的确定性参数算法l c a 。如图2 3 所示，在算法 执行的第一步，检查s 是否为空。若s 为空，算法返回“t r u e ；否则，从s 中任选一点p ，若三中存在p a r t i t i a l l i n e s e t ，则对每一p a r t i t i a l l i n e s e tl i 调用 1 3 硕士学位论文第二章超平面覆盖问题的固定参数算法 函数j u d g e ，若函数的返回值为“t r u e ，则将p 加入到厶中，并递归调用算 法l c a ( s , 三) ，其中参数s 变为s - s ( 1 ( p ，p 3 ) ，参数三变为 三l 双，p ，p ，) ) ) ， 直到返回值为“t r u e ”为止。若上述递归调用的返回值均为“f a l s e ，且三 中含有e m p t y ，则从三中任选一，并调用函数，_lines e t e m p t y l i n es e tj u d g e 若函数的返回值为“t r u e ，算法l c a 进行递归调用，其中参数s 变为仞) ， 参数三变为 三l ，仞 ，厶) 。如果没有任何一个递归调用的返回值为“t r u e ， 算法l c a 返回“f a l s e 。 图2 - 3 算法l c a 1 4 硕士学位论文第二章超平面覆盖问题的固定参数算法 2 2 3 算法l c a 正确性证明和时间复杂度分析 接下来证明算法l c a 的正确性并分析其时间复杂度。 定理2 1 算法l c a 可以正确判断是否存在不超过k 条直线覆盖平面上给定 的n 个点。 证明：一方面，当给定的输入实例为假时( 即不存在k 条直线覆盖s 中所有 点) ，算法l c a 必定返回“f a l s e ”。因为算法第4 4 步可确保集合厶( g 敛) 中的所有点共同一直线，所以，对于某一个输入实例，如果不存在k 条直线能覆 盖s 中所有点，则算法l c a 不可能把s 中所有点都移入三1 ，厶中，即s 不可 能为空，算法l c a 第7 2 步必定返回“f a l s e 。 另一方面，当给定的输入实例为真时( 即存在k 条直线覆盖s 中所有点) ， 算法l c a 的返回值一定是t r u e 。因为当s 为空时，意味着s 中所有点均被移 入上l ，厶中，即算法l c a 已经找到一个满足条件的三，所以算法第l 步返回 t r u e ；当s 不为空时，算法l c a 从s 选取一点p ，由性质2 1 可知，不需要考 虑将p 移入c o m p l e t e，否则算法第45步已经将从s中删除。而算法line s e t p 第4 步考虑了将p 移入p a r t i t i a ll i n es e t 时的情况，第6 步考虑了将p 移入 e m p t y _ l i n e _ s e t 时的情况( 因为所有的e m p t y _ l i n e _ s e t 没有区别，所以只需将p 移入任意一个e m p t y即可) 。因此，算法 考虑了所有的分支情况，l i n e s e tl c a 即如果输入实例为真，算法l c a 则一定可以找到一个三= 上l ，l k 使得 s = - ij ! ! ，三，中的点共一直线) 。 定理2 2 算法l c a 的总的时间复杂