邮递员问题的DNA计算模型  

作　　者：张春露 

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001

出　　处：《科学技术创新》2018年第3期66-67,共2页Scientific and Technological Innovation

基　　金：国家自然科学基金项目资助(61702008)

摘　　要：中国邮递员问题是求邮递员从邮局出发,走遍他所管辖的每条街道,将信件送到后返回回邮局的最短路线,将邮递员问题用图论的语言描述,本文采用把数学问题转换到DNA链上的算法,对给定图G中的每条边进行编码,并编码出连接DNA链,生成问题的解的DNA链,及相应的生物操作把最终链分离,本文给出的一种DNA编码方法,并设计一种用6个顶点求解的中国邮递员问题的算法,证明提出的DNA计算方式的算法有效可行。Chinese postman problem is to find the postman from the post office of the streets around his jurisdiction, the shortest route will be returned back to the letter to the post office, the postman problem with graph description language, the mathematical problem is transformed into DNA chain algorithm, encoding for each given in figure G edge connection and encod- ing DNA chain, generation of DNA solutions and the corresponding biological chain, the chain operation of the final separation, a DNA encoding method is presented, and a design with 6 vertices for the Chinese postman problem show that the proposed DNA algorithm, calculation method. The algorithm is effective and feasible.

关 键 词：DNA计算 邮递员问题 编码 DNA链 

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