排课表问题的闭环DNA计算模型的算法 被引量：17

1

作者 周康 同小军 刘文斌 《计算机应用》 CSCD 北大核心 2007年第4期991-993,共3页

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和... 排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。 展开更多

关键词 闭环dna计算模型 排课表问题 批删除实验 批分离实验

在线阅读 下载PDF 职称材料

移动Ad Hoc网络QoS路由的闭环DNA计算模型 被引量：2

2

作者 殷脂 叶春明 温蜜 《上海理工大学学报》 CAS 北大核心 2010年第6期593-596,601,共5页

提出针对移动Ad Hoc网络QoS路由问题的闭环DNA计算模型.对每条路径进行弧、费用、探针的3组编码,再采用有目的的终止技术合成所有从起点到终点的弧首尾相连路径,然后通过接入实验和电泳实验得到费用最小路径,并通过检测实验输出所有费... 提出针对移动Ad Hoc网络QoS路由问题的闭环DNA计算模型.对每条路径进行弧、费用、探针的3组编码,再采用有目的的终止技术合成所有从起点到终点的弧首尾相连路径,然后通过接入实验和电泳实验得到费用最小路径,并通过检测实验输出所有费用最小路径,同时给出了算法的生化实现过程.实验结果表明:在不增加算法复杂度情况下获得了QoS路由问题的最优解. 展开更多

关键词 QOS路由 闭环dna计算模型 dna编码 接入实验 单向链路

在线阅读 下载PDF 职称材料

基于闭环DNA计算的最大独立集问题的算法 被引量：12

3

作者 周康 同小军 +1 位作者 刘文斌 许进 《计算机工程》 CAS CSCD 北大核心 2008年第4期40-41,44,共3页

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法... 提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。 展开更多

关键词 闭环dna计算模型 最大独立集问题 删除实验 电泳实验

在线阅读 下载PDF 职称材料

最短路问题的闭环DNA算法 被引量：14

4

作者 周康 同小军 +1 位作者 刘文斌 许进 《系统工程与电子技术》 EI CSCD 北大核心 2008年第3期556-560,共5页

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过... 提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。 展开更多

关键词 闭环dna计算模型 最短路问题 有目的的终止技术 接入实验

在线阅读 下载PDF 职称材料

背包问题的闭环DNA算法 被引量：12

5

作者 周康 同小军 许进 《系统仿真学报》 CAS CSCD 北大核心 2008年第17期4605-4608,共4页

提出了闭环DNA分子的结构多样性,即闭环DNA分子在同一个位置上具有不同的DNA序列。提出了双约束的整数规划背包问题闭环DNA算法,即对变量取值进行DNA编码并形成所有可能解;用批接入实验、电泳实验和批删除实验筛选出可行解,用批接入实... 提出了闭环DNA分子的结构多样性,即闭环DNA分子在同一个位置上具有不同的DNA序列。提出了双约束的整数规划背包问题闭环DNA算法,即对变量取值进行DNA编码并形成所有可能解;用批接入实验、电泳实验和批删除实验筛选出可行解,用批接入实验、电泳实验得到最优解;通过检测实验输出所有最优解。由一个算例说明算法的有效性。针对减少DNA编码和内切酶数量的问题改进了算法;对有特殊要求的背包问题提出了解决方法。 展开更多

关键词 闭环dna计算模型 背包问题 批接入实验 批删除实验

在线阅读 下载PDF 职称材料

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

6

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

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

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

在线阅读 下载PDF 职称材料

0-1规划问题的闭环DNA算法 被引量：5

7

作者 周康 覃磊 +1 位作者 同小军 许进 《系统工程与电子技术》 EI CSCD 北大核心 2009年第4期947-951,共5页

提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成... 提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。 展开更多

关键词 闭环dna计算模型 0-1规划问题 接入实验 删除实验

在线阅读 下载PDF 职称材料

基于闭环DNA的指派问题算法 被引量：9

8

作者 周康 同小军 许进 《计算机科学》 CSCD 北大核心 2007年第12期211-213,共3页

给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值,然后通过有目的的终止技术和删除实验得到指派问题的全部可行解,最后通过电泳实验和检测实验... 给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值,然后通过有目的的终止技术和删除实验得到指派问题的全部可行解,最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后,为减少DNA编码数量和缩短DNA编码的码长,讨论了算法的两种改进方法。 展开更多

关键词 闭环dna计算模型 指派问题 删除实验 有目的的终止技术

在线阅读 下载PDF 职称材料

基于DNA计算的指派问题 被引量：3

9

作者 周康 同小军 许进 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2008年第2期35-38,共4页

给出了推广的闭环DNA计算模型及其生化实验.用闭环DNA计算模型设计出了指派问题的DNA算法.对决策变量进行4组DNA编码来存放决策变量和效益值;通过有目的的终止技术和删除实验得到指派问题的全部可行解;通过批接入实验、电泳实验和检测... 给出了推广的闭环DNA计算模型及其生化实验.用闭环DNA计算模型设计出了指派问题的DNA算法.对决策变量进行4组DNA编码来存放决策变量和效益值;通过有目的的终止技术和删除实验得到指派问题的全部可行解;通过批接入实验、电泳实验和检测实验获得最优指派问题的最优解.举例说明了算法的可行性.最后讨论了推广的闭环DNA计算模型的应用前景和不足之处. 展开更多

关键词 指派问题 闭环dna计算模型 批接入实验 有目的的终止技术

在线阅读 下载PDF 职称材料

最大权匹配问题的闭环DNA算法 被引量：1

10

作者 周康 殷燕芳 +1 位作者 李玉华 覃磊 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2007年第8期63-66,共4页

给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编... 给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性. 展开更多

关键词 闭环dna计算模型 赋权匹配问题 接入实验 删除实验

在线阅读 下载PDF 职称材料

最大匹配问题的闭环DNA算法

11

作者 王明春 陈超 许瑞麟 《天津工程师范学院学报》 2007年第4期8-11,共4页

给出了一个解决最大匹配问题的闭环DNA算法模型,并对相应的生化实验做出了说明,实现了仅用删除实验直接构造最大匹配的构想。由于算法仅用到基本删除操作,使得算法的实现简捷、可靠。

关键词 闭环dna计算模型 最大匹配 NP完全问题

在线阅读 下载PDF 职称材料

可满足性问题的闭环DNA算法 被引量：8

12

作者 周康 魏传佳 +1 位作者 刘朔 王防修 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2009年第7期75-78,共4页

给出并证明了可满足性问题有解的一个充分必要条件,即合取范式的成假赋值仅由与简单析取式个数相等的有限个向量决定.在此条件基础上设计出用这些向量对初始赋值进行筛除的可满足性问题过滤算法,该算法的时间复杂性仅与向量个数和维数有... 给出并证明了可满足性问题有解的一个充分必要条件,即合取范式的成假赋值仅由与简单析取式个数相等的有限个向量决定.在此条件基础上设计出用这些向量对初始赋值进行筛除的可满足性问题过滤算法,该算法的时间复杂性仅与向量个数和维数有关.为了在DNA计算模型上实现可满足性问题过滤算法,采用2n维向量的数据结构进行DNA编码代表可满足性问题的赋值;而闭环DNA计算模型的删除实验恰好能够完成对初始赋值的筛选,得到可满足性问题的可行解.最后用闭环DNA计算模型实现了可满足性问题过滤算法,并用实例说明了算法的有效性和可行性. 展开更多

关键词 可满足性问题 闭环dna计算模型 过滤算法 删除实验 接入实验

原文传递

集合覆盖问题闭环DNA算法 被引量：1

13

作者 周康 解智 +1 位作者 魏传佳 易校尉 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2010年第2期21-25,共5页

介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组... 介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性. 展开更多

关键词 dna算法 闭环dna计算模型 集合覆盖问题 检测实验 电泳技术

原文传递