摘要
解决图论与排列组合难题是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.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2012年第4期751-755,共5页
Acta Electronica Sinica
基金
国家自然科学基金(No.60773131
No.61070229)
山西省自然科学基金(No.2008011010)
CCF中文信息技术开放基金(No.20110102)
