![](https://csdnimg.cn/release/download_crawler_static/19697648/bg1.jpg)
收稿日期:20131122;修回日期:20131229 基金项目:国家自然科学基金资助项目(11272066)
作者简介:李艳梅(1981),女,河北石家庄人,博士研究生,主要研究方向为工程与科学计算(13581530612@163.com);余文(1964),男,副教
授,主要研究方向为计算机理论、分子计算、人工智能;宁建国(1963),男,博导,主要研究方向为计算力学、高性能计算.
一种广义分子计算模型及其在 NP问题中的应用
李艳梅
1
,余 文
2
,宁建国
1
(1.北京理工大学 机电学院 爆炸科学与技术国家重点实验室,北京 100081;2.北京邮电大学 计算机学院 智能
通信软件多媒体北京市重点实验室,北京 100876)
摘 要:目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他
类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵
机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。
实验说明了该模型能够在多项式时间求解 NP完全的满足性问题(SAT),比现有分子计算模型在计算准确性和
通用性上存在明显优势。
关键词:广义分子计算模型;图灵机;SAT问题
中图分类号:TP301 文献标志码:A 文章编号:10013695(2014)11335304
doi
:10.3969/j.issn.10013695.2014.11.035
GeneralizedmolecularcomputationalmodelforNPproblems
LIYanmei
1
,YUWen
2
,NINGJianguo
1
(1.StateKeyLaboratoryofExplosiveScience& Technology,CollegeofMechatronicalEngineering,BeijingInstituteofTechnology,Beijing
100081,China;2.BeijingKeyLaboratoryofIntelligentTelecommunicationSoftware&Multimedia,CollegeofComputer,BeijingUniversityof
Posts&Telecommunications,Beijing100876,China)
Abstract:DNAcomputingisanovelparallelcomputationparadigm.Existingmodelsweremostlybasedonmolecularbiologi
caltechnologyanddifferentfromthetraditionalcomputers
,theywerelessuniversalthantraditionalones,sothealgorithmora
DNAcomputerjustforonekindofproblemcouldnotbetransplantedtosolveotherproblemswithoutanymodification.This
paperputforwardanewgeneralizedmolecularcomputationalmodel(designatedbyGMCM)basedonTuringmachine,which
didnotrelyonbiotechnologyandincludedanordinarysingletapeTuringmachine
,afinitewriteonlytape,andaspecial
workingtape.Throughthetopologicalmappingbetweenthewriteonlytapeandthewokringtape,itcouldrealizereadorwrite
inparallel.ValidationtestprovesthatGMCMcansolvethesatisfiabilityprobleminapolynomialtimeandhasobviousadvan
tagescomparedwithexsitingDNAcomputeroncomputationaccuracyanduniversalproperty.
Keywords:generalizedmolecularcomputationalmodel;Turingmachine;satisfiabilityproblem
!
引言
最早提出分子计算思想的是 Feynman
[1]
,他构建了亚微观
尺度计算机;
1973年,Bennett
[2]
设想构建了一种用酶来催化的
分子图灵机,它以极低的能量代价在遗传物质如
DNA上执行计
算过程。但由于当时技术水平较低,这些设想没有引起人们足
够的重视。直到 1994年,Adleman
[3]
博士利用现代分子生物技
术,提出了有向哈密顿路问题(
directedHamiltonianpathprob
lem,DHHP)的 DNA计算方法,并在 DNA溶液中成功地进行了
实验,在国际上引起了巨大的反响,开创了 DNA计算的新纪元。
脱氧核糖核酸(DNA)存在于每个生物体,它是遗传信息
存储的媒介,由称之为核苷酸的单元组成。按照其包含的不同
碱基可以分为腺嘌呤、胞嘧啶、胸腺嘧啶、鸟嘌呤,简称 A、C、
T、G。单核苷酸基对端对端连接在一起组成 DNA双链,其中 A
和 T、C和 G互补(WatsonCrick补)。两个互补的单链 DNA在
生化反应的退火进程中将会连接在一起,组成双链螺旋。
分子计算又称
DNA计算,其基本思想是:利用 DNA特殊
的双螺旋结构和碱基互补配对规律对信息编码,把要运算的对
象映射成
DNA分子链,在生物酶的作用下,生成各种数据池。
然后按照一定的规则将原始问题的数据运算高度并行地映射
成
DNA分子链的可控的生化过程;最后利用分子生物技术如
聚合链反应 PCR等检测所需要的运算结果。DNA计算的核心
问题是将经过编码后的
DNA链作为输入,在试管内或其他载
体上经过一定时间完成控制的生物化学反应,以此来完成运
算,使得从反应后的产物中能得到全部的解空间。
分子计算是一种基于空间的处理模式,它通过高效的信息
编码和巨大的并行存储及处理系统,能同时生成、处理和存储
指数个数据,实现指数的加速计算和时空复杂性转换,能同时
可求得问题的全体解集和快速求解
NP问题。
DNA计算在理论、应用和实验方面都取得了较大的进步。
各种分子计算模型,如剪接模型
[4~7]
、粘贴模型
[8]
、发夹分子计
算模型
[9]
、基于质粒的计算模型
[10]
、自组装模型和 DNA链置
换模型
[11~18]
等模型被提出,并应用在解决 NP
[19~24]
、密码、医
学等方面,很多模型被证明是计算完备的。
DNA作为信息的载体,存储容量是非常大的,但是容器中
DNA存在不可控性,故其产生伪解的可能性很高。并且目前
第 31卷第 11期
2014年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.31No.11
Nov.2014