计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2008年
12期
2073-2080
,共8页
经典Ramsey数%DNA计算%位序列计算模型
經典Ramsey數%DNA計算%位序列計算模型
경전Ramsey수%DNA계산%위서렬계산모형
Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型.但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型.其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序.文中重点对该模型的机理与使用方法进行了分析研究.
Ramsey數問題是組閤數學迺至整箇數學中最具魅力的研究領域,也是最睏難的數學問題之一.對于經典Ramsey數,至今隻有9箇Ramsey數得到解決.按照傳統的算法,其搜索空間太大,噹前的電子計算機無法勝任.研究錶明,DNA計算在求解睏難的NP-完全問題上優于電子計算機.目前已經建立瞭衆多求解NP-完全問題的DNA計算模型.但未見到用于求解Ramsey數的DNA計算模型.作者建立瞭一種新穎的DNA計算模型,用于一般經典Ramsey數的求解.全文共分兩篇,該文屬首篇,建立瞭一種可適用于DNA計算模式的所謂的求解Ramsey數的位序列計算模型.其中的位序列是以圖的相鄰矩陣下三角陣中行從左到右、列從上到下的排列次序.文中重點對該模型的機理與使用方法進行瞭分析研究.
Ramsey수문제시조합수학내지정개수학중최구매력적연구영역,야시최곤난적수학문제지일.대우경전Ramsey수,지금지유9개Ramsey수득도해결.안조전통적산법,기수색공간태대,당전적전자계산궤무법성임.연구표명,DNA계산재구해곤난적NP-완전문제상우우전자계산궤.목전이경건립료음다구해NP-완전문제적DNA계산모형.단미견도용우구해Ramsey수적DNA계산모형.작자건립료일충신영적DNA계산모형,용우일반경전Ramsey수적구해.전문공분량편,해문속수편,건립료일충가괄용우DNA계산모식적소위적구해Ramsey수적위서렬계산모형.기중적위서렬시이도적상린구진하삼각진중행종좌도우、렬종상도하적배렬차서.문중중점대해모형적궤리여사용방법진행료분석연구.
