对赋权图上经典优化问题的DNA计算方法进行探讨,改进原有DNA计算模型中的权值编码方法,提出一些新的DNA编码方法及DNA算法.具体地说,通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法,通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法.通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法.所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力.%This paper discusses DNA computing methods of classical optimization problems on weighted graph.By improving the methods of encoding weights in the previous DNA computing model,this paper proposes some new DNA encoding methods and DNA algorithms for optimiza-tion problems.Specifically,by designing the relative length graph of a weighted and undirected graph,it gives a DNA encoding method and DNA algorithm based on relative length graph for the traveling salesman problem; by designing the general line graph of a weighted and undirected graph,gives a DNA encoding method and DNA algorithm based on general line graph for the Chi-nese postman problem; by selecting the best one of reverse complement alignments of DNA se-quences,gives a DNA encoding method and DNA algorithm based on reverse complement alignment for the minimum spanning tree problem; by designing an improved polynomial trans-formation from the vertex cover problem to the Hamilton circle problem,gives a DNA encoding method and DNA algorithm based on polynomial transformation for the vertex cover problem.The proposed DNA computing methods improve the capability of representing and dealing with data in DNA computing.
展开▼
