Ménage问题的一种粘贴DNA算法  

A DNA Sticker Algorithm for the Ménage Problem

作　　者：杨玉星[1,2] 王世英[3] 

机构地区：[1]安阳师范学院计算机与信息工程学院,河南安阳455000 [2]山西大学计算机与信息技术学院,山西太原030006 [3]山西大学数学科学学院,山西太原030006

出　　处：《电子学报》2012年第4期751-755,共5页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60773131;No.61070229);山西省自然科学基金(No.2008011010);CCF中文信息技术开放基金(No.20110102)

摘　　要：解决图论与排列组合难题是DNA计算领域的研究目标之一.为了使用分子生物方法解决Ménage问题,本文给出了Ménage问题的数学模型;并对解决该问题的难点进行了分析,提出一种解决方案,改进了该问题的数学模型;提出一种解决Ménage问题的粘贴DNA算法并简要分析了该算法的复杂度.为了提高效率,引入广义分离和广义多级分离操作;通过一个实例给出了实验操作步骤,对实验进行了模拟.The traditional trend of DNA computing aims at solving computationally intractable problems in the filed of graph theory and permutation and combination.For the objective to solve the Ménage problem with biological operations,this paper gave a mathematical model and analyzed the difficulties of solving the problem with DNA computation.An improved mathematical model of the Ménage Problem to overcome these difficulties was proposed.In order to improve the efficiency,using the extended separation and extended multi-separation operation,this paper proposed a sticker DNA algorithm of the Ménage problem and analyzed the complexity of the algorithm.Consequently,it showed the operation steps and carried out simulation experiments by an instance.

关 键 词：DNA计算 圆周排列 Ménage问题 粘贴模型 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]