论文摘要
给定一个顶点赋权的无向图G=（V,E）和正整数k,最小权顶点覆盖k-路问题（MWVCPk）要求找到图G的一个权重最小的顶点子集FCV,使得图G中的任何一条k-路都至少有一个顶点在F中,其中k-路指包含k个顶点的路。对于任意的k≥2,MWVCPk都是NP困难的。因此,研究者们主要从近似算法和特殊图上的精确算法两个角度去研究此问题。论文的第一部分,我们给出了MWVCP3第一个启发式算法,多启动贪婪迭代算法。我们对算法进行了数值实验,图的实例通过随机的方法生成,其中最大的实例包含1000个顶点和250000个边。数值实验结果表明该启发式算法能在极短时间内得到小规模问题的最优解、可接受时间内得到大规模问题的可行解。论文的第二部分,我们考虑了 Series-Parallel图上的MWVCP3,利用动态规划方法给出了一个该问题的精确算法,算法的运行时间为O（|V|）。
论文目录
文章来源
类型: 硕士论文
作者: 张文杰
导师: 涂建华
关键词: 最小权顶点覆盖路问题,迭代贪婪算法,启发式算法,动态规划
来源: 北京化工大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 北京化工大学
分类号: O157.5
DOI: 10.26939/d.cnki.gbhgu.2019.000427
总页数: 50
文件大小: 2132K
下载量: 21
相关论文文献
- [1].一种增量式约简方法求解最小顶点覆盖问题[J]. 计算机应用研究 2018(12)
- [2].3度图的最小顶点覆盖问题的多项式时间算法[J]. 数学理论与应用 2014(03)
- [3].化学反应优化算法求解最小顶点覆盖问题[J]. 小型微型计算机系统 2015(02)
- [4].一种求解平面图的最小顶点覆盖算法[J]. 计算机系统应用 2010(09)
- [5].图的最小顶点覆盖问题的链置换模型[J]. 佳木斯大学学报(自然科学版) 2018(02)
- [6].奖励收集顶点覆盖问题的一个2-近似算法[J]. 北京化工大学学报(自然科学版) 2014(02)
- [7].树上限制性k-node multi-multiway cut 问题的近似算法[J]. 洛阳理工学院学报(自然科学版) 2020(03)
- [8].改进的最小顶点覆盖问题的贪婪算法[J]. 内蒙古师范大学学报(自然科学汉文版) 2012(02)
- [9].顶点覆盖问题线性内核算法[J]. 计算机研究与发展 2008(S1)
- [10].加权最小顶点覆盖的加权分治算法[J]. 小型微型计算机系统 2015(05)
- [11].最小顶点覆盖问题的加权分治算法[J]. 运筹与管理 2015(05)
- [12].最小顶点覆盖快速降阶算法[J]. 小型微型计算机系统 2008(07)
- [13].分层算法求解竞赛图上的最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2012(01)
- [14].Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J]. 北京化工大学学报(自然科学版) 2019(01)
- [15].图顶点覆盖问题决策神经网络模型[J]. 计算机学报 2009(08)
- [16].最少顶点覆盖问题的研究[J]. 中国新通信 2014(13)
- [17].DNA计算图的最小顶点覆盖问题[J]. 襄樊职业技术学院学报 2008(01)
- [18].一种混合化学反应优化算法求解最小顶点覆盖问题[J]. 计算机应用研究 2016(09)
- [19].次模函数近似算法求最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2011(01)
- [20].图的最小顶点覆盖的粘贴DNA计算模型[J]. 首都师范大学学报(自然科学版) 2013(01)
- [21].基于DNA步行者求解最小顶点覆盖问题的计算模型[J]. 广州大学学报(自然科学版) 2020(01)
- [22].单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法[J]. 噪声与振动控制 2012(03)
- [23].基于DNA自组装模型解决图的最小顶点覆盖问题[J]. 安徽理工大学学报(自然科学版) 2015(03)
- [24].基于邻接矩阵与关联矩阵解决最大匹配等问题[J]. 贵阳学院学报(自然科学版) 2015(02)
- [25].最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用 2011(01)
- [26].基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J]. 长春师范大学学报 2017(12)
- [27].三正则图上的P_3顶点覆盖问题[J]. 杭州电子科技大学学报(自然科学版) 2019(05)
- [28].基于混合优化算法的网络流量有效测量点选择[J]. 计算机应用研究 2009(04)
- [29].模糊环境下的最小权顶点覆盖问题[J]. 计算机应用研究 2012(01)
- [30].粘贴模型在两类特殊问题中的改进算法研究[J]. 计算机科学 2012(S3)
标签：最小权顶点覆盖路问题论文; 迭代贪婪算法论文; 启发式算法论文; 动态规划论文;