计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2014年
6期
1253-1262
,共10页
周旭%周炎涛%欧阳艾嘉%李肯立
週旭%週炎濤%歐暘艾嘉%李肯立
주욱%주염도%구양애가%리긍립
DNA计算%Tile自组装模型%最大团问题%NP完全问题%并行计算
DNA計算%Tile自組裝模型%最大糰問題%NP完全問題%併行計算
DNA계산%Tile자조장모형%최대단문제%NP완전문제%병행계산
DNA%computing%Tile%self-assembly%model%maximum%clique%problem%NP-complete%problem%parallel%computing
Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n～2n,求解成功率由0.5～增加至0.5”～0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.
Tile自組裝模型憑藉其納米屬性、自組裝、可編程等特點,引起瞭科學界的廣汎關註.然而隨著Tile自組裝模型的深入研究,可擴展性問題已成為其進一步髮展的巨大障礙.為此,首先提齣瞭一種最大糰問題Tile自組裝高效模型.該模型主要由TileDual子繫統、初始配置子繫統及檢測子繫統三大部分構成.其中TileDual子繫統的設計中引入瞭啟髮式算法的設計思想,提齣瞭TileDual分子對的概唸.通過與已有基于窮舉策略的研究成果對比髮現:模型不僅具有Tile自組裝模型的優點,而且將求解圖G0最大糰問題所需的解空間規模由2n0減少至1.712n～2n,求解成功率由0.5～增加至0.5”～0.57n,其中n0為圖G0中的頂點數,n為預處理後得到的圖G的頂點數,且n0≤n.因此,所提齣的模型在減少解空間規模的同時還可以提高生物併行計算解的精確性.
Tile자조장모형빙차기납미속성、자조장、가편정등특점,인기료과학계적엄범관주.연이수착Tile자조장모형적심입연구,가확전성문제이성위기진일보발전적거대장애.위차,수선제출료일충최대단문제Tile자조장고효모형.해모형주요유TileDual자계통、초시배치자계통급검측자계통삼대부분구성.기중TileDual자계통적설계중인입료계발식산법적설계사상,제출료TileDual분자대적개념.통과여이유기우궁거책략적연구성과대비발현:모형불부구유Tile자조장모형적우점,이차장구해도G0최대단문제소수적해공간규모유2n0감소지1.712n～2n,구해성공솔유0.5～증가지0.5”～0.57n,기중n0위도G0중적정점수,n위예처리후득도적도G적정점수,차n0≤n.인차,소제출적모형재감소해공간규모적동시환가이제고생물병행계산해적정학성.
