DNA计算原理在NP-完全问题中的应用

作者：朱清妍; 李锡辉

来源：电脑知识与技术, 2011, (26): 6338-6340.

• DNA计算
• NP-完全问题
• 有向Hamilton路问题
• 最大团与最大独立集问题 DNA computing
• NP complete problem
• With the Hamilton path problem
• Maximum clique and maximum independent set problem

DNA计算是一种利用生物分子间的相互作用来实现并行计算的新的计算模式,具有高度的并行性、巨大的信息存储能力和极低的能耗等优点。该文对DNA计算的一般原理进行了介绍,且介绍了DNA计算原理在解决NP问题方面所取得的进展,并指出了DNA计算中存在的问题。

• 单位
  湖南信息职业技术学院