| 广义分子计算模型在整数问题中的应用 |
| |
| 引用本文： | 李艳梅,余文,宁建国. 广义分子计算模型在整数问题中的应用[J]. 北京理工大学学报, 2014, 34(S1): 111-113,146 |
| |
| 作者姓名： | 李艳梅 余文 宁建国 |
| |
| 作者单位： | 北京理工大学爆炸科学与技术国家重点实验室, 北京 100081;北京邮电大学 计算机学院, 智能通信软件多媒体北京市重点实验室, 北京 100876;北京理工大学爆炸科学与技术国家重点实验室, 北京 100081 |
| |
| 基金项目： | 国家自然科学基金资助项目(11272066) |
| |
| 摘 要： | 分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.
|
| 关 键 词： | 分子计算机 图灵机 整数问题 |
| 收稿时间： | 2014-03-20 |
Generalized Molecular Computational Model for NP Problems |
| |
| LI Yan-mei,YU Wen and NING Jian-guo. Generalized Molecular Computational Model for NP Problems[J]. Journal of Beijing Institute of Technology(Natural Science Edition), 2014, 34(S1): 111-113,146 |
| |
| Authors: | LI Yan-mei YU Wen NING Jian-guo |
| |
| Affiliation: | State Key Laboratory of Explosion Science and Technology, Beijing Institute of Technology, Beijing 100081, China;Beijing Key Laboratory of Intelligent Telecommunication Software and Multimedia, School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China;State Key Laboratory of Explosion Science and Technology, Beijing Institute of Technology, Beijing 100081, China |
| |
| Abstract: | DNA computing is a novel parallel computation paradigm. DNA, as the carrier of information and computing, is uncontrollable in biochemical reactions. There are many difficulties and limitations for the construction of a molecular universal computer. Based on the Turing machine and sticker model, a new generalized turing model (GTM) independent of biotechnology and only with an ordinary single tape Turing machine was proposed. Validation tests on the model showed that it can be used to solve the integer programming problem in the polynomial time and has obvious advantages in both computation accuracy and simply coding. |
| |
| Keywords: | molecular computational machine Turing machine integer programming problem |
|
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
|
点击此处可从《北京理工大学学报》下载全文 |
|
