基于可满足解空间的DNA算法——解决最小顶点覆盖问题  

A DNA Algorithm Based on Satisfiable Solution Space——for the Minimum Vertex Cover Problem

作　　者：朱翔鸥[1] 刘文斌[1] 孙川[2] 许进[3] 

机构地区：[1]温州大学计算机科学与工程学院,浙江温州325027 [2]黄石理工学院机电工程系,湖北黄石435003 [3]华中科技大学系统科学研究所,武汉430074

出　　处：《计算机工程与应用》2005年第31期46-48,共3页Computer Engineering and Applications

基　　金：国家自然科学基金项目(编号:60403002)资助

摘　　要：论文给出了基于可满足解空间的最小顶点覆盖问题的DNA算法,该算法直接生成可满足解空间,无须在全体解空间中进行各种过滤过程。在对图中的顶点进行适当的编码后,使用常规的生物操作完成可满足解空间的产生及最终解的分离。最后指出了该算法的优点、存在问题及下一步的研究方向。This paper presents a DNA algorithm for the minimum vertex cover problem which is based on satisfiable solution space.This algorithm builds directly a satisfiable solution space of the problem,so it dosen＇t need to filter in the all and the one,The problem is mapped onto DNA strand and the vertex is coded by DNA sequence.The satisfiable solution is solved by tube operation that performs the basic core processing and extraction that makes the results visible.Finally,this paper discusses the advantages and disadvantages of the algorithm,and also points out the direction for the further research directions.

关 键 词：DNA计算 NP完全问题 顶点覆盖问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]