赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。

A DNA Solution to Weighted Hamilton Path Problem

DNA computing is a new computing technique based on the biochemical reaction. Since Adleman's initiative work in 1994, lots of researchers have been attracted to this field. We first introduce the structure of DNA molecules, principle of DNA computing and its implementation method. Then we propose a DNA algorithm to the weighted Hamilton path of the directed graph on the basis of Adleman's work. We also give some discussions about its further application to the undirected graph and about how to express the weight in other situations. Finally, we point out the disadvantages of this algorithm and further research direction of DNA computing. The study result further verifies the feasibility of DNA computing.