连通3-路点覆盖问题及部分集合多重覆盖问题的近似算法
发布时间：2020-03-21 12:12
【摘要】：覆盖问题是一类非常著名的组合优化问题.顶点覆盖问题与集合覆盖问题,作为图灵奖获得者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都给定一个成本ws0.对于任意元素e∈E都定义一个覆盖需求re0.集合多重覆盖问题指的是找到一个最小的子集簇F(?)S,使得E中的每一个元素都能达到覆盖要求,其中元素e能达到覆盖要求指的是e属于F的至少re个集合.部分集合多重覆盖问题指的是找到一个最小的子集簇F'(?)S,使得E中至少ρ|E|个元素达到覆盖要求值。本学位论文计划分为四章,第一章介绍相关概念与背景知识,并介绍研究现状.第二章,设计了一个连通3-路覆盖问题的近似算法,其近似比为2α+ 1/2,其中α为(不加连通条件的)3-路覆盖问题的近似比.第三章给出部分集合多重覆盖的贪婪算法,并提出一个新的衡量算法性能的参数:部分完全近似比,即将部分覆盖的近似值与完全覆盖的最优值进行比较.结果表明我们的算法部分完全近似比为lnr/1-ρ,数值实验也表明了用部分覆盖替代完全覆盖的优点.第四章对研究方法与研究结果进行讨论与总结。
【图文】：
化是由R%收缩后得到的点所构成的集合．对每一个收缩点ｓ邋ｅ邋＼／（Ｇｌｖ．＼Ｓ），我们逡逑令儿表示收缩点ｓ对应到原图Ｇ上的点集．我们把儿中的点统称为标准点（ｎｏｍｒｎｌ逡逑ｒｅｒｈｃｅｓ）．为７便于读者理解上述概念，，我们给出了一个例子．如图２．１⑷，｛心，逡逑和｛＾p海梢远杂Φ酵迹牵郏樱ⅲ葜械牧礁隽ǚ种В恚唬玻停恚罚梢远杂Φ酵煎义希峰义
本文编号：2593315
【图文】：
化是由R%收缩后得到的点所构成的集合．对每一个收缩点ｓ邋ｅ邋＼／（Ｇｌｖ．＼Ｓ），我们逡逑令儿表示收缩点ｓ对应到原图Ｇ上的点集．我们把儿中的点统称为标准点（ｎｏｍｒｎｌ逡逑ｒｅｒｈｃｅｓ）．为７便于读者理解上述概念，，我们给出了一个例子．如图２．１⑷，｛心，逡逑和｛＾p海梢远杂Φ酵迹牵郏樱ⅲ葜械牧礁隽ǚ种В恚唬玻停恚罚梢远杂Φ酵煎义希峰义
本文编号：2593315
本文链接：https://www.wllwen.com/kejilunwen/yysx/2593315.html
