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

Closed circle DNA model for weighted matching

作　　者：周康[1] 殷燕芳[2] 李玉华[1] 覃磊[1] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023 [2]武汉工业学院机械工程系,湖北武汉430023

出　　处：《华中科技大学学报（自然科学版）》2007年第8期63-66,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60403002);湖北省自然科学基金资助项目(2004ABA031;2005ABA233;2006ABA272);湖北省优秀中青年科技创新团队计划资助项目;湖北省教育厅社科研究基金资助项目(2005q092);浙江省自然科学基金资助项目(ZJNSF-Y105654)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]