（计算机应用技术专业论文）若干np难解问题的参数化算法研究.pdf

摘要 n p 难解问题是理论计算机科学的主要研究对象，对n p 难解问 题提出实际有效的固定参数可解算法是理论计算机科学中的一个新 的研究方向。 本文以m a t c h i n g 、p a c k i n g 、m a x i m u mc u t 和m u l t i c u t 等经典的 n p 难解问题为研究对象，在深入挖掘问题结构中新特点、新性质的 基础上，运用多种参数计算技术对它们提出了一系列的固定参数可 解算法。其主要研究工作包括： 带权的m s e tp a c k i n g 、m dm a t c h i n g 问题以前一直是用近似算 法求解的，本文运用参数计算理论对该类问题进行了研究，首次证 明了该类问题是固定参数可解的。本文首先运用最新的着色技术和 动态规划技术对带权的m s e tp a c k i n g 问题提出了一个时间复杂度为 o ( 1 2 2 所d ( 1 ) 的固定参数可解算法，接着在此基础上利用问题本身的 结构特点对带权的m dm a t c h i n g 问题提出了一个时间复杂度为 o ( 1 2 2 ( 肿1 d ( 1 ) 的固定参数可解算法，然后对带权的3 dm a t c h i n g 问题提出了一个时间复杂度为o ( 5 4 8 3 2 z ) 的固定参数枚举算法，其 中z 表示需要枚举的权值最优解的个数。 针对3 dm a t c h i n g 参数化计数问题目前还不存在固定参数可 解的精确算法，本文提出了一个基于m o n t e c a r l o 自适应覆盖算法的 固定参数可解随机近似算法。即对于一个含有拧个三元组的集合墨 给定一个整数后和两个正实数和6 ，该算法能在时间 0 ( 5 4 8 3 2 l n ( 2 1 8 ) e 2 ) l 内返回一个数，使得p r o b ( 1 - ) o s 段l + g ) n o l 一6 ，其中o 表示s 中大小为k 的m a t c h i n g 的精确个数。在设计 该随机近似算法时，本文的关键发现是3 dm a t c h i n g 参数化计数问 题通过着色技术可以转化为标准的集合并集计数问题。 m a x i m u mc u t 问题通常是用近似算法来求解的，本文运用参数 计算理论对该问题进行了研究。首先对该问题及其相关概念进行了 参数化定义，然后对参数化m a x i m u mc u t 问题提出了一种基于随机 划分技术的随机算法。该随机算法依次将实例图的顶点进行 f i n ( 1 i e ) 1x 2 七( o l 一6 ，w h e r en oi s t h et o t a ln u m b e ro f m a t c h i n g so fs i z eki nt h et r i p l es e ts o u ra l g o r i t h mi sb a s e do nt h e r e c e n ti m p r o v e dc o l o r - c o d i n g t e c h n i q u e sa n dm o n t e c a r l os e l f - a d j u s t i n g c o v e r a g ea l g o r i t h md e v e l o p e db yk a r p ，l u b ya n dm a d r a s t h em a x i m u mc u t p r o b l e m i sa l s os t u d i e di nt e r m so f p a r a m e t e r i z e dc o m p u t a t i o n a lc o m p l e x i t yt h e o r y a f t e rd e f i n i n gt h e p a r a m e t e r i z e dv e r s i o no ft h ep r o b l e m ，w ep r e s e n tar a n d o m i z e d p a r a m e t e r i z e da l g o r i t h mb a s e do nr a n d o ms e p a r a t i o n t h ea l g o r i t h m r a n d o m l yb i p a r t i t i o n st h ev e r t e xs e to fag i v e ni n s t a n c ef o rf l l l ( 1 占) 1x2 七 ( o n o 都有乃z ) s 暖门) ，则称苁疗) = d ( 烈以) ) 。 本文讨论的算法都是指数时间算法，在表示时间复杂度时一般用符号d 幸， 其目的是隐藏多项式时间表达式而突出指数时间表达式。其具体定义为，给定 一个函数a n ，动，如果存在一个常量k o ，c 和n o 使得对于所有的硷，砌。都有 a n ，助烈幼刀c 则称a n ，助= d 木( 双动) 。 1 6 全文结构 本文内容共分为9 章，具体结构组织如下： 第l 章绪论。概述了本文的研究背景、研究内容和研究意义，并且简要 地介绍了参数计算基本理论，说明了本文中的相关符号和术语。 第2 章主要参数化算法设计技术。概述了本文用到的四种主要参数化算 法设计技术，即核心化技术、分支限界技术、着色技术和随机划分技术。对于 每种技术，首先阐述其基本思想或基本原理，然后结合实例剖析和总结了其技 术要点。 接下来六章分别阐述6 个具体的研究点及其相关结果。根据具体问题的类 别，该六章可以分为三个部份。 第一部份：以m a t c h i n g 和p a c k i n g 问题为研究对象，以求解问题实例的一 个最优解、枚举问题实例的多个最优解和统计问题实例的所有解为线索分三章 分别进行阐述。 第3 章带权m a t c h i n g 和p a c k i n g 问题的一种固定参数可解算法。本章首 先运用参数计算理论对该问题进行参数化，然后分别对它们提出了一种基于着 色技术的固定参数可解算法。 第4 章3 一dm a t c h i n g 问题的一种固定参数枚举算法。本章运用固定参数 枚举理论和着色技术对参数化3 一dm a t c h i n g 问题提出了一种高效的枚举算法。 1 2 博士学位论文第一章绪论 第5 章3 dm a t c h i n g 参数化计数问题的种随机近似算法。本章运用着 色技术和m o n t e c a r l o 自适应覆盖算法对3 dm a t c h i n g 参数化计数问题提出了 一种固定参数可解的随机近似算法。 第二部份：以最大割问题为研究对象，着重研究有着广泛应用背景的 m a x i m u mc u t 问题和进一步研究基于保证值的参数化m a x c u t 问题，其中后者 也是参数计算领域中目前很有代表性的基于保证值的参数化问题。 第6 章m a x i m u mc u t 问题的一种基于划分技术的固定参数可解算法。本 章首先运用参数计算理论对m a x i m u mc u t 问题进行了参数化，接着提出了一个 随机的固定参数可解算法，然后在此基础上提出了一个确定性的固定参数可解 算法。 第7 章基于保证值的m a x c u t 问题参数算法的改进。本章对基于保证值 m a x c u t 问题关于边的核和关于顶点的核分别进行了研究，在此基础上对该问题 提出了一个改进的参数化算法。 第三部份：着重研究参数化m u l t i c u t 问题。 第8 章m u l t i c u t 问题参数算法的改进。运用相关问题的最新研究结果对 m u l t i c u t 问题提出了一个改进的参数化算法。 第9 章本文的结论部份。总结了本文的主要贡献和创新点，并对下一步 的研究方向进行了展望。 1 3 博士学位论文第二章主要参数化算法设计技术 第二章主要参数化算法设计技术 参数化算法设计技术是设计固定参数可解算法的基础，是参数计算理论中 的研究热点。本章介绍文中用到的几种主要技术，即核心化技术、分支限界技 术、着色技术和随机划分技术。 2 1 核心化技术 核心化过程是求解许多参数化问题的“必须”阶段【5 1 彤1 。一个参数化问题 是固定参数可解的当且仅当该问题是可核心化的【8 1 。 2 1 1基本思想 核心化技术的基本思想是在对问题求解之前，通过一些归约规则快速地处 理问题实例中容易处理的部份，使实例“收缩”至真正难解的核一i 二, f s 3 l 。 例如对于参数化点覆盖问题，b u s s 等人提出了如下归约规则1 5 4 1 。 规则l ：删除所有的孤立点； 规则2 ：对于度为l 的点，将其邻居点放入覆盖集； 规则3 ：对于度至少为斛l 的点，将该点放入覆盖集。 设( g ，硒为点覆盖问题的任意一个实例，g 为在图g 上尽可能使用上述规 则之后的剩余图，旷为归约过程已放入覆盖集中点的个数。容易证明，( g ，助是 点覆盖问题的一个真实例当且仅当( g , k - k ) 是点覆盖问题一个真实例，并且g 至多含有j j 2 个顶点 5 3 j 。 上述通过一组归约规则将实例进行精简的过程就是一个核心化的过程。 定义2 1 对于参数化问题q ，如果存在一个多项式时问算法4 和一个递 归函数g ，且算法彳能将q 的任意一个实例g ，幼转化为一个新实例o ，尼i ) ，其中 i x l ( k ) 和鱼， ，妨是9 的一个真实例时当且仅当0 ，七i ) 也是9 的一个真实例， 则称参数问题q 是可核心化的，算法a 称为q 的一个核心化算法，新实例o j ) 称为核心化之后问题q 的核【3 l 。 如果以参数为横坐标、实例的规模大小为纵坐标，则问题的任意实例都可 看作二维平面上的一个点。设核心化之前实例所在的平面为尸，核心化之后实 例所在的平面为尸。核心化过程本质上是一个将p 中任意实例0 ，肋转换到尸 1 4 博士学位论文第二章主要参数化算法设计技术 中对应实例o 谚，) 的映射过程。如果一个问题可以核心化，则在平面尸上真、假 实例的分布必定有一定的规律，即存在某个函数烈七) ，使得区域k 1 矽) 中的 所有实例要么都全为真实例要么都全为假实例。只有区域i x l 。该类特征多项式的根可由有关数学工具直接求出，设c 为上 述特征多项式的根，则搜索树丁的叶子结点数所= 扩。因此分支限界搜索算法的 时间复杂度为优西。 分支限界技术的主要优点是：( 1 ) 利用参数限定了分支树的深度；( 1 ) 利 用分支规则排除了大量的不可能为解的组合；( 2 ) 利用“树 的结构特点对所 有可能解的组合进行了“多级压缩 。 2 2 2 技术要点 从分支限界技术的基本思想可以看出，其技术要领是如何设计正确的分支 规则和如何设计高效的分支规则。 1 、分支规则的正确性 分支限界技术的关键是在实例上找到一个能够进行分支的“局部结构 。如 何寻找这种特定的“局部结构 ，目前还没有明确的判定法则。根据经验，本章 总结如下几点作为“局部结构”的必要条件：( 1 ) 其中至少有一个单元必定属 于实例的某个最优解。( 2 ) 其中每个单元都可能属于实例的某些最优解。( 3 ) 不存在两个既相互属于对方的最优控制范围，又属于实例同一最优解的两个单 元。 从有界搜索树模型可以看出，在一个实例( x ，j | ) 中寻找一个大小为k 的解 d ，分支限界技术采取的策略是在每条从根结点到叶子结点的路径上将x 分解 为与叶子结点对应的实例x l 和耽可吖l 两部份，将d 分解为x 2 的最优解d 2 和实 例g l ，k - l 伤1 ) 的一个解d l 两部份，并且d l 可在多项式时间求出，伤通过逐次 分解求出。因此在寻找“局部结构 时，上述条件( 1 ) 和( 2 ) 是必须的，否 则通过逐次分解求出的解就不是砣的最优解。对于条件( 3 ) ，反设存在两个单 1 9 博士学位论文第二章主要参数化算法设计技术 元甜和”相互属于对方的最优控制范围内，在分支时它们必定分被分开，共同 属于的最优解不可能形成，这就可能导致解的丢失。 现以平面图上的独立集问题和平面图上的支配集问题为例进一步说明上述 “局部结构 的要点。 平面图上的独立集参数化问题【7 9 1 输入：一个平面图皑悃和一个非负整数后； 问题：图g 中是否有一个大小至少为后的独立集? 即k 个相互之间没有边 的顶点。 一般图上的独立集参数化l ；- j 题是研l 】完全的【引，但平面图上的独立集参数 化问题是固定参数可解的。因为平面图有一个重要性质：任意一个平面图都至 少有一个度最多为5 的顶点。运用该性质就可以找到一个满足分支条件的“局 部结构 。 设( g ，曲为平面图上独立集问题的任意一个实例，g 上度最多为5 的点为， 现选定研v 】= 中含有2 七个元 素未知子集日的一个特定的划分，可以首先构造一个( 胛，2 k ) 全集空间，然后对 其中o ( n 2 2 k + 1 2 i 0 9 2 ( 2 七h 1 0 9 ( 2 七) 个划分进行逐个试探寻找。根据定理2 2 ，可知f 中 至少存在一个划分能够实现对未知子集日预定的划分。 随机划分技术的优点是算法过程比较简明，算法的时间复杂度明显低于其 相应的确定性算法。该技术除了求解k - s e ts p l i t t i n g 问题之外，已成功应用到 p a c k i n g 、m a t c h i n g 和k - p a t h 等问题的求解中【叫。 2 5 本章小结 本章对参数化算法设计的四种基本技术分别进行了介绍、剖析和总结，这 些技术也是本文中将要用到的主要技术。它们在各章节中的具体应用如表2 1 所示。一个实际问题的解决通常要同时用到多种算法技术。 博士学位论文 第二章主要参数化算法设计技术 在参数计算领域，近年来人们还提出了其他一些参数化算法设计技术，如 迭代压缩技术【l o o 、图分离技术1 1 0 n 、参数隐含上界技术【9 7 】和局部化贪婪技术1 0 2 等等。这些技术有的是由某种基本技术演变发展而来的，有的是由多种基本技 术有机结合而形成的。由于它们在本文中没有被直接应用，本章不作详述。 表2 - i4 种基本技术在本文中的具体应用 序号技术名称技术要点应用章节 l 核心化技术归约规则的设计和核推导七 2 分支技术分支规则的设计八 3 着色技术着色和求解三、四、五 4 随机划分技术概率分析 土 、 博士学位论文第三章带权m a t c h i n g 和p a c k i n g 问题的一种固定参数可解算法 第三章带权m a t c h i n g 和p a c k i n g 问题的一 种固定参数可解算法 带权的m dm a t c h i n g 和m s e tp a c k i n g 问题( 庇：3 ) 通常是用近似算法来求解 的。本章首先运用参数计算理论对这两个问题进行了参数化定义，然后运用最 新的着色技术和动态规划技术对带权的m s e tp a c k i n g 问题提出了一个时间复杂 度为o ( 1 2 2 嘞d ( 1 ) ) 的固定参数可解算法，接着在此基础上利用问题本身的结构 特点对带权的m dm a t c h i n g 问题提出了一个时间复杂度为o ( 1 2 2 忙1 ) 叩) ) 的固 定参数可解算法，表明了带权的m s e tp a c k i n g 问题和带权的m - dm a t c h i n g 问 题都是固定参数可解的。 3 1引言 m a t c h i n g 和p a c k i n g 问题是一类重要的组合问题，尤其是m dm a t c h i n g 问 题和m s e tp a c k i n g 问题在调度、代码优化和生物信息学等领域有着广泛的应用 背景。m dm a t c h i n g 问题可以看作是m s e tp a c k i n g 问题的一种特殊情况。下面 首先给出几个与m s e tp a c k i n g 问题相关的定义。 定义3 1 ( 常规) s e tp a c k i n g t 3 5 】：给定一个含有n 个元组的集合s ，目标是 构造一个最大子集，使得y 中任何两个元组之间均没有相同元素( 如图3 1 所示) 。 e 图3 - 1s e tp a c k i n g 问题示意图 定义3 2m s e tp a c k i n g 1 】：给定一个含有刀个元组的集合s ，其中每个元组 包含最多m 个元素( ，庀3 ) ，目标是构造一个最大子集y ，使得f 中任何两个元组 博士学位论文 第三章带权m a t c h i n g 和p a c k i n g 问题的一种固定参数可解算法 之间均没有相同元素。 一个含有m 个元素的元组，本章简称为一个m 元组。对于一个含有多个元 组的集合p ，如果p 中任何两个元组之间均没有相同元素，则称p 为一个 p a c k i n g 。 定义3 3 ( 参数化) m s e tp a c k i n g l 9 1 】：给定一个组对( 墨粉，其中s 是一个含 有刀个元组的集合，并且每个元组包含最多m 个元素，k 是一个整数，目标是 在s 中构造一个正好含有k 个元组的p a c k i n g 或者报告s 中不存在一个这样的 p a c k i n g 。一个正好含有k 个元组的p a c k i n g ，叫做一个k - p a c k i n g 。 更一般地，如果对m s e tp a c k i n g 问题实例中每一个元组赋予一个非负权值， 就得到了带权的m - s e tp a c k i n g 问题。此时，一个p a c k i n g 的权值定义为该p a c k i n g 中所有元组的权值之和。 定义3 4 ( 带权的) m s e tp a c k i n g 1 0 3 1 ：给定一个含有刀个带权元组的集合s ， 其中每个元组含有最多m 个元素，目标是在s 中寻找一个权值最大的p a c k i n g 。 常规s e tp a c k i n g 问题是k a r p 等人提出的2 1 个n p 完全问题之一【3 5 j 。在该 问题中各元组的大小不一致，增加了求解的难度。为了便于分析问题，人们通 常研究各个元组大小受限的脚s e tp a c k i n g 问题。 m s e tp a c k i n g ( 舵：3 ) 问题是n p 难的【i 】。近年来人们运用参数计算技术对 参数化的m s e tp a c k i n g 问题进行了大量的研列9 1 ，舛1 。特别地，3 s e tp a c k i n g 问 题已成为参数计算领域中的一个热点问题，其相关研究结果如表3 1 所示i 1 0 4 】。 其中j w a n g 等在文献【1 0 8 】中提出的时间复杂度为d 宰( 3 5 2 3 七) 的算法是当前求解 参数化3 - s e tp a c k i n g 问题的最好结果。 表3 - 13 s e tp a c k i n g 问题参数算法研究进展历程 文献随机算法确定性算法 主要技术 1 0 2 1d 幸( ( 5 7 七n 局部贪婪 【1 0 6 】o * ( 1 0 8 8 3 0 * ( 3 2 0 0 0 3 代数法、着色法 1 9 5 】 o * ( 12 6 7 3 致七) ) 核心化、着色法 【1 0 7 】d 幸( 2 5 2 勺o * ( 1 6 3 勺 分治法、着色法 9 1 1d 木( 2 5 2 3 k )o * ( 1 2 8 3 着色法、分治法 9 4 】d ( 4 6 1 3 勺着色法、动态规划 【1 0 8 】d 宰( 3 5 2 3 分治法 博士学位论文 第三章带权m a t c h i n g 和p a c k i n g 问题的一种固定参数可解算法 然而据我们所知，带权的m s e tp a c k i n g 问题以前还没有相关的参数算法研 究。带权的m s e tp a c k i n g 问