| 最大权匹配问题的闭环DNA算法 |
| |
| 引用本文： | 周康,殷燕芳,李玉华,覃磊.最大权匹配问题的闭环DNA算法[J].华中科技大学学报(自然科学版),2007,35(8):63-66. |
| |
| 作者姓名： | 周康 殷燕芳 李玉华 覃磊 |
| |
| 作者单位： | 1. 武汉工业学院数理科学系,湖北,武汉,430023
2. 武汉工业学院机械工程系,湖北,武汉,430023 |
| |
| 基金项目： | 国家自然科学基金
,
湖北省自然科学基金
,
湖北省优秀中青年创新团队资助项目
,
湖北省教育厅社科研究基金
,
浙江省自然科学基金 |
| |
| 摘 要： | 给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性.
|
| 关 键 词： | 闭环DNA计算模型 赋权匹配问题 接入实验 删除实验 最大权 匹配问题 闭环 算法复杂度 matching weighted model circle 有效性 最优解 输出 检测实验 电泳实验 删除 条件 约束 合成 组编码 计算模型 赋权 |
| 文章编号： | 1671-4512（2007）08-0063-04 |
| 修稿时间： | 2006-04-03 |
Closed circle DNA model for weighted matching |
| |
| Zhou Kang,Yin Yanfang,Li Yuhua,Qin Lei.Closed circle DNA model for weighted matching[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2007,35(8):63-66. |
| |
| Authors: | Zhou Kang Yin Yanfang Li Yuhua Qin Lei |
| |
| Institution: | a Department of Mathematics and Physics, b Department of Machinery Engineering, Wuhan Polytechnic University, Wuhan 430023, China |
| |
| Abstract: | A kind of strategy dealing with the real number problem in DNA computing is given and proved.First set of real number is replaced with set of rational number in the error field.Then set of minimal integer having relation to the set of rational number is broken out.Weighted matching problem is brought forward.An algorithm of weighted matching problem is put forward basing on model of closed circle DNA computing.In the closed circle DNA algorithm,first three groups of DNA encoding for all edges of graph are encoded,and closed circle DNA initialized is synthesized.Then all kinds of matching are obtained by delete experiment using two adjacent edges as restriction,and all kinds of maximal weighted matching are filtered out by electrophoresis experiment.Finally all optimization solutions are found using detect experiment.Correctness of the algorithm is proved,and complexity of the algorithm is discussed.And an example explains feasibility of the DNA algorithm. |
| |
| Keywords: | model of closed circle DNA computing weighted matching problem insert experiment delete experiment |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
