最小顶点覆盖问题的改进粘贴模型 被引量：9

1

作者 董亚非 张家秀 +1 位作者 殷志祥 许进 《电子与信息学报》 EI CSCD 北大核心 2005年第4期556-560,共5页

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学 反应作为计算工具的先例,具有广阔的应用前景。本文简单回顾了DNA计算的发展,并简要介绍了分子计算的一 种模型--粘贴模型。最后我们利用粘... DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学 反应作为计算工具的先例,具有广阔的应用前景。本文简单回顾了DNA计算的发展,并简要介绍了分子计算的一 种模型--粘贴模型。最后我们利用粘贴模型的基本原理,运用荧光标记技术,提出了最小顶点覆盖问题的表面技 术解决方案。 展开更多

关键词 DNA计算 粘贴模型 荧光标记技术 最小顶点覆盖问题

在线阅读 下载PDF 职称材料

求图的最小顶点覆盖集的一个近似算法 被引量：8

2

作者 闫兴篡 殷建平 +1 位作者 蔡志平 刘湘辉 《哈尔滨工业大学学报》 EI CAS CSCD 北大核心 2008年第7期1131-1135,共5页

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略... 已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充. 展开更多

关键词 最小顶点覆盖集 近似算法 近似比 运行时间 NP难问题

在线阅读 下载PDF 职称材料

最小顶点覆盖快速降阶算法 被引量：9

3

作者 宁爱兵 马良 熊小华 《小型微型计算机系统》 CSCD 北大核心 2008年第7期1282-1285,共4页

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该... 通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析. 展开更多

关键词 最小顶点覆盖问题 降阶算法 度 完全图

在线阅读 下载PDF 职称材料

最小顶点覆盖问题的闭环DNA算法 被引量：28

4

作者 周康 许进 《计算机工程与应用》 CSCD 北大核心 2006年第20期7-9,28,共4页

提出了闭环DNA计算模型的基本概念及其基本生化实验,并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造顶点覆盖补集的构想;再通过电泳实验得到最小顶点覆盖的补集,由补集得到最小顶点覆盖... 提出了闭环DNA计算模型的基本概念及其基本生化实验,并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造顶点覆盖补集的构想;再通过电泳实验得到最小顶点覆盖的补集,由补集得到最小顶点覆盖。这使得算法的设计独特而新颖;由于算法仅用到基本的生化实验,这使得算法的实现简捷、可靠。 展开更多

关键词 闭环DNA计算模型 最小顶点覆盖问题 补集 删除实验

在线阅读 下载PDF 职称材料

一种混合化学反应优化算法求解最小顶点覆盖问题 被引量：1

5

作者 郑光勇 徐雨明 +1 位作者 李肯立 孙士兵 《计算机应用研究》 CSCD 北大核心 2016年第9期2669-2672,共4页

最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法... 最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。 展开更多

关键词 最小顶点覆盖问题 组合优化 无向图 化学反应优化 贪心算法

在线阅读 下载PDF 职称材料

图的最小顶点覆盖的粘贴DNA计算模型 被引量：3

6

作者 聂晓艳 耿俊 汤建钢 《首都师范大学学报（自然科学版）》 2013年第1期7-12,共6页

本文在对经典粘贴模型以及全信息化的粘贴DNA计算模型的基本方法进行充分讨论的基础上,提出一种用粘贴DNA计算模型解决图的最小顶点覆盖问题的新方案,将数学问题的求解同并行生物操作有效结合.

关键词 DNA计算 粘贴模型 最小顶点覆盖问题

在线阅读 下载PDF 职称材料

一种增量式约简方法求解最小顶点覆盖问题 被引量：2

7

作者 占善华 谢小军 《计算机应用研究》 CSCD 北大核心 2018年第12期3685-3688,共4页

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约... 最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。 展开更多

关键词 增量式约简 最小顶点覆盖 最小属性约简 大规模图

在线阅读 下载PDF 职称材料

最小顶点覆盖问题的竞争决策算法 被引量：7

8

作者 金婷婷 王波 宁爱兵 《计算机工程与应用》 CSCD 北大核心 2011年第1期32-34,共3页

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来达到优化目的的新型寻优算法。采用竞争决策算法原理,利用竞争决策算法的通用模型,求解图的最小顶点覆盖问题。

关键词 竞争决策算法 最小顶点覆盖 竞争力函数 决策函数

在线阅读 下载PDF 职称材料

最小顶点覆盖问题的加权分治算法 被引量：5

9

作者 陈吉珍 宁爱兵 +2 位作者 支志兵 王永斐 张惠珍 《运筹与管理》 CSSCI CSCD 北大核心 2015年第5期151-155,共5页

最小顶点覆盖问题是组合优化中经典NP—Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设... 最小顶点覆盖问题是组合优化中经典NP—Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O（1．255n），优于常规分析下的时间复杂度O（1．325n）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。 展开更多

关键词 图论 算法复杂性 加权分治技术 分支降阶技术 最小顶点覆盖

在线阅读 下载PDF 职称材料

一种求解平面图的最小顶点覆盖算法 被引量：3

10

作者 吴春 朱国魂 +1 位作者 谢玉忠 林宏 《计算机系统应用》 2010年第9期97-100,共4页

最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独... 最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。 展开更多

关键词 点覆盖 最小顶点覆盖 最大独立集 平面图 邻域

在线阅读 下载PDF 职称材料

单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法 被引量：5

11

作者 丁文婷 徐涛 杨国庆 《噪声与振动控制》 CSCD 2012年第3期166-170,共5页

为监测和分析中小型机场附近噪声污染状况,提出一种基于单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法。该方法以大量网格点作为候选监测点,形成顶点集合,利用INM噪声预测软件计算各顶点在每个噪声事件发生时的噪声值,根... 为监测和分析中小型机场附近噪声污染状况,提出一种基于单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法。该方法以大量网格点作为候选监测点,形成顶点集合,利用INM噪声预测软件计算各顶点在每个噪声事件发生时的噪声值,根据单个飞机噪声事件的限值确定各顶点监测到的噪声事件,从而建立最小顶点覆盖模型,然后采用改进的贪心算法求得近似最优解,使得顶点能覆盖所有噪声事件并且个数最少,实验证明改进的贪心算法比传统的贪心算法得到的解更优,需要的监测点更少。 展开更多

关键词 声学 最小顶点覆盖 贪心算法 监测点分布 飞机噪声事件

在线阅读 下载PDF 职称材料

求一般图的最小顶点覆盖集问题的混合贪婪算法 被引量：6

12

作者 吕健康 张国基 《科学技术与工程》 2010年第20期4891-4895,共5页

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大。根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法。该... 现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大。根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法。该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为 O( | V | 2) ,执行效果较好,性能近似比不大于 4/3,接近已知的可能的近似比下界 1. 166 6,低于 2005 年认为最低的近似比 1. 361,是图的最小顶点覆盖问题算法的一个较好的补充。 展开更多

关键词 最小顶点覆盖集 复杂度分析 混合贪婪算法

在线阅读 下载PDF 职称材料

基于DNA自组装模型解决图的最小顶点覆盖问题 被引量：2

13

作者 郭洪敏 殷志祥 《安徽理工大学学报（自然科学版）》 CAS 2015年第3期17-20,共4页

在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。... 在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。 展开更多

关键词 最小顶点覆盖 DNA自组装模型 可满足性问题

在线阅读 下载PDF 职称材料

改进的最小顶点覆盖问题的贪婪算法 被引量：1

14

作者 张楠 张升 《内蒙古师范大学学报（自然科学汉文版）》 CAS 北大核心 2012年第2期206-210,共5页

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完... 通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2). 展开更多

关键词 最小顶点覆盖问题 贪婪算法 顶点的度 访问标记 减治法

在线阅读 下载PDF 职称材料

加权最小顶点覆盖的加权分治算法

15

作者 王永斐 宁爱兵 +2 位作者 陈吉珍 胡琳琳 杨晓芳 《小型微型计算机系统》 CSCD 北大核心 2015年第5期1082-1084,共3页

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为... 加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性. 展开更多

关键词 加权分治技术 加权最小顶点覆盖问题 分支降阶技术 算法复杂性

在线阅读 下载PDF 职称材料

3度图的最小顶点覆盖问题的多项式时间算法

16

作者 支志兵 宁爱兵 +1 位作者 胡琳琳 张惠珍 《数学理论与应用》 2014年第3期114-120,共7页

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.

关键词 最小顶点覆盖 多项式时间算法

在线阅读 下载PDF 职称材料

基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型 被引量：2

17

作者 巩成艳 殷志祥 赵鑫月 《长春师范大学学报》 2017年第12期29-33,共5页

DNA自组装技术为DNA计算的发展带来了一些新的启发。目前,解决各种NP完全问题的方法有多种多样的计算模型,其中有些是非常有用的,可以解决复杂的NP完全问题。在本文中,在自组装纳米颗粒探针的基础上,介绍了关于最小顶点覆盖问题的一种新... DNA自组装技术为DNA计算的发展带来了一些新的启发。目前,解决各种NP完全问题的方法有多种多样的计算模型,其中有些是非常有用的,可以解决复杂的NP完全问题。在本文中,在自组装纳米颗粒探针的基础上,介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合,编码在自组装纳米探针的识别区,通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型,该模型具有方便、灵敏、稳定性高的优点。 展开更多

关键词 DNA计算 自组装 纳米颗粒 最小顶点覆盖问题

在线阅读 下载PDF 职称材料

基于DNA步行者求解最小顶点覆盖问题的计算模型

18

作者 赵鑫月 殷志祥 《广州大学学报（自然科学版）》 CAS 2020年第1期28-33,共6页

DNA步行者作为一类可执行复杂操作的新兴动态DNA纳米机器,可以在纳米尺度上以可控的方式在指定轨道内行走.文章将DNA步行者用于解决最小顶点覆盖问题,首先构造出全部顶点覆盖,用删除实验得到顶点覆盖的补集,再通过荧光探针N-甲基卟啉二... DNA步行者作为一类可执行复杂操作的新兴动态DNA纳米机器,可以在纳米尺度上以可控的方式在指定轨道内行走.文章将DNA步行者用于解决最小顶点覆盖问题,首先构造出全部顶点覆盖,用删除实验得到顶点覆盖的补集,再通过荧光探针N-甲基卟啉二丙酸(NMM)特异性识别G-四链体结构,产生荧光,最终得到最小顶点覆盖.该模型设计独特新颖,通用性好,操作简单,运行效率更高. 展开更多

关键词 DNA步行者 最小顶点覆盖 G-四链体结构

在线阅读 下载PDF 职称材料

图的最小顶点覆盖问题的链置换模型

19

作者 张春露 殷志祥 《佳木斯大学学报（自然科学版）》 CAS 2018年第2期277-280,共4页

针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。

关键词 DNA计算 最小顶点覆盖 链置换

在线阅读 下载PDF 职称材料

最小连通顶点覆盖问题的降阶回溯算法

20

作者 曾宾 宁爱兵 +2 位作者 付振星 李之桥 张惠珍 《运筹与管理》 CSSCI CSCD 北大核心 2024年第3期28-34,共7页

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问... 本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。 展开更多

关键词 最小连通顶点覆盖 上界子算法 下界子算法 回溯子算法

在线阅读 下载PDF 职称材料