中国邮递员问题的DNA计算

DNA computation for Chinese Postman Problem

提出了"虚拟权值"和"虚拟节点"的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解;然后,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。算法分析表明,新算法具有易于解读、编码简单等特点。

Such new concepts as virtual weight and virtual node were proposed, and based on which, a novel algorithm based on DNA computation was designed to solve the Chinese Postman Problem （CPP）. In the new proposed algorithm, all the feasible solutions of the CPP were obtained by utilizing the Polymerase Chain Reaction （PCR） techniques to eliminate false solutions from all the possible solutions, and then, the optimal solutions were extracted from those feasible solutions by; utilizing surface-based techniques for DNA computation and fluorescence-labeling. The results indicate that the new algorithm has good characteristics such as simple encoding and readability.