一类特殊整数规划问题的DNA计算

被引：16

作者：

王雷

林亚平

李智勇

机构：

[1] 湖南大学计算机与通信学院,湖南大学计算机与通信学院,湖南大学计算机与通信学院长沙,长沙,长沙

来源：

计算机研究与发展 | 2005年 / 08期

基金：

湖南省自然科学基金;

关键词：

DNA计算; 整数规划问题; 荧光标记; 秩; 约束补链;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义.提出了约束方程组的”秩”以及约束方程的3种“约束补链”概念,并基于这些概念,利用在基于表面的DNA计算中采用荧光标记的策略,给出了一类特殊整数规划问题最优解的一种基于DNA计算的求解算法.新算法利用荧光猝灭技术来排除非解,从而得到满足约束条件的所有可行解,最后再通过比较所有可行解的目标函数值来求得问题的所有最优解.算法分析表明,新算法具有解读、编码简单和错误率低的特点.

引用

页码：1431 / 1437

页数：7