一种新的求解最小生成树问题的DNA算法

A New DNA Algorithm Solving Minimum Spanning Tree Problem

基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,并且描述了MSTP解的计算过程。

Bio-intelligent computing based on biochemical reactions is a hotspot in recent research of computing field.DNA computing is a computing model by using DNA molecule and biochemical reaction.Because of the advantages of DNA computing, such as parallelism and mass storage, it can be used to solve complex problem.In this paper, a method to solve minimum spanning tree problem based on DNA computing is proposed.The encoding method and solving process are described in the paper.