有向哈密尔顿路问题的研究

• 作者: 方洁
• 来源期刊: 福建电脑
• 学科: 工学
• 关键词: DNA计算 哈密尔顿回路问题 算法复杂度
• 年，卷（期）: 2011,（1）
• 页码范围: 54-55,34
• 分类号: TP3
• 字数: 4078字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-2782.2011.01.025

摘要

DNA计算是在分子水平上进行的计算,与传统的基于电子计算机的线性计算系统相比较,具有如可并发计算、耗能量小等无法比拟的特点.目前的研究主要集中在一些特定问题上,如NIP完全问题,而这些问题在电子计算机上需要指数时间.本文利用已有的Adleman实验[1]解决有向图哈密尔顿路问题,给出了剪贴计算模型的形式化模型,并从算法复杂性角度分析其复杂性.