论文部分内容阅读
覆盖问题是一类非常著名的组合优化问题.顶点覆盖问题与集合覆盖问题,作为图灵奖获得者Richard M.Karp提出的21个经典NP完全问题中的两个备受关注的问题,目前已被理论计算机科学领域中的广大研究工作者所熟知,因而相关的研究工作已经有很多.本文主要是研究这两类问题所对应的推广问题连通k-路覆盖问题(CVCPk)与部分集合多重覆盖问题(PSMC). 连通k-路点覆盖问题(CVCPk)产生于无线传感网络中的安全与检测.对于一个图G=(V,E),如果图中的每一条k-1长路都有至少一个点属于点集S,我们称点集S是图G的k-路点覆盖,如果S在图G中导出的子图是连通的,我们就称点集S是图G的连通k-路点覆盖(CVCPk). 部分集合多重覆盖问题(PSMC)是集合多重覆盖问题(SMC)与部分集合覆盖问题(PSC)的结合.给定一个集合E,实数0<ρ<1,以及由E的子集构成的集簇S.对于任意集合S∈S都给定一个成本ws>0.对于任意元素e∈E都定义一个覆盖需求re>0.集合多重覆盖问题指的是找到一个最小的子集簇F(∈)S,使得E中的每一个元素都能达到覆盖要求,其中元素e能达到覆盖要求指的是e属于F的至少re个集合.部分集合多重覆盖问题指的是找到一个最小的子集簇F(∈)S,使得E中至少ρ|E|个元素达到覆盖要求值. 本学位论文计划分为四章,第一章介绍相关概念与背景知识,并介绍研究现状.第二章,设计了一个连通3-路覆盖问题的近似算法,其近似比为2α+1/2,其中α为(不加连通条件的)3-路覆盖问题的近似比.第三章给出部分集合多重覆盖的贪婪算法,并提出一个新的衡量算法性能的参数:部分完全近似比,即将部分覆盖的近似值与完全覆盖的最优值进行比较.结果表明我们的算法部分完全近似比为lnr/1-p,数值实验也表明了用部分覆盖替代完全覆盖的优点.第四章对研究方法与研究结果进行讨论与总结.