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

• 作者: 周康 李玉华 殷燕芳 覃磊
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 闭环DNA计算模型 赋权匹配问题 接入实验 删除实验
• 年，卷（期）: 2007,（8）
• 页码范围: 63-66
• 页数: 4页
• 分类号: TP301.6
• 字数: 4762字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2007.08.018

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周康	武汉工业学院数理科学系	69	557	14.0	20.0
2	李玉华	武汉工业学院数理科学系	7	19	3.0	4.0
3	殷燕芳	武汉工业学院机械工程系	21	137	6.0	10.0
4	覃磊	武汉工业学院数理科学系	11	39	5.0	6.0