一种基于DNA计算的指定结点路由算法

• 作者: 李仁发 李肯立 杨磊 黄启鑫
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: DNA计算 松散指定路由 指定结点路由 MPLS ASON
• 年，卷（期）: 2009,（12）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 2373-2381
• 页数: 9页
• 分类号: TP301
• 字数: 8533字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.02373

摘要

带指定结点约束的路由问题是一个NP难问题,该问题是电信行业路山智能化和交通电力运输等领域的关键问题之一.基于DNA计算的高度并行性,文中提出一种将电子计算机与DNA计算机相结合的方法求解指定结点路由问题.算法由转化算法Transform()、首末结点搜索切割算法FirstEndSearcher()、转化图结果搜索算法DNASearcher()和结果读取算法ResultReader()共4个子算法组成.分析表明:算法的电子计算机部分缩小了问题结点和边的规模,从而使解决问题所需的DNA分子链数数量级从O((n-2)!)减少至O((m-2)!)(n≥2为图中结点数,m≥2为图中指定必经结点数).算法的DNA计算机部分采用了有针对性的DNA编码新方案,提高了边权值编码的信噪比,通过一系列生物操作,筛选出问题的精确解.和单纯DNA超级计算或电子计算机指定结点路由算法相比,文中算法可显著扩大理论上待求解问题的规模.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李仁发	湖南大学计算机与通信学院	468	4582	30.0	44.0
2	杨磊	湖南大学计算机与通信学院	29	97	5.0	7.0
3	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
4	黄启鑫	湖南大学计算机与通信学院	1	4	1.0	1.0