计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2009年
3期
827-831
,共5页
DNA计算%Ramey图%NP完全问题%粘贴模型%剪接模型
DNA計算%Ramey圖%NP完全問題%粘貼模型%剪接模型
DNA계산%Ramey도%NP완전문제%점첩모형%전접모형
Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题.构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外.提出了一个构造对角Ramsey图的递阶式DNA粘贴-剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散.特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性.
Ramsey數問題是一箇著名的組閤優化問題, 同時也是一箇NP完全問題.構造對角Ramsey圖是一箇難處理的計算問題,使用窮舉的算法來構造對角Ramsey圖必然導緻計算量的指數爆炸,窮舉的DNA算法也不例外.提齣瞭一箇構造對角Ramsey圖的遞階式DNA粘貼-剪接算法,該算法通過逐箇添加頂點的思想, 逐步刪除瞭問題的絕大部分非解,在一定程度上緩解瞭問題解的空間擴散.特彆地, 專門針對對角Ramsey數R(5,5)的43階Ramsey圖的構造問題進行瞭計算分析, 分析結果充分地肯定瞭該算法的有效性.
Ramsey수문제시일개저명적조합우화문제, 동시야시일개NP완전문제.구조대각Ramsey도시일개난처리적계산문제,사용궁거적산법래구조대각Ramsey도필연도치계산량적지수폭작,궁거적DNA산법야불예외.제출료일개구조대각Ramsey도적체계식DNA점첩-전접산법,해산법통과축개첨가정점적사상, 축보산제료문제적절대부분비해,재일정정도상완해료문제해적공간확산.특별지, 전문침대대각Ramsey수R(5,5)적43계Ramsey도적구조문제진행료계산분석, 분석결과충분지긍정료해산법적유효성.
