《计算机学报》文章摘要   全文下载
  文章题目一种基于DNA计算的指定结点路由算法
  作者杨磊 黄启鑫 李肯立 李仁发
  作者单位(湖南大学计算机与通信学院 长沙 410082)
  发表年份2009
  发表月份12期(2373—2381)
  文章摘要摘要 带指定结点约束的路由问题是一个NP难问题,该问题是电信行业路由智能化和交通电力运输等领域的关键问题之一.基于DNA计算的高度并行性,文中提出一种将电子计算机与DNA计算机相结合的方法求解指定结点路由问题.算法由转化算法Transform()、首末结点搜索切割算法FirstEndSearcher()、转化图结果搜索算法DNASearcher()和结果读取算法ResultReader()共4个子算法组成.分析表明:算法的电子计算机部分缩小了问题结点和边的规模,从而使解决问题所需的DNA分子链数数量级从O((n-2)!)减少至O((m-2)!)(n2为图中结点数,m2为图中指定必经结点数).算法的DNA计算机部分采用了有针对性的DNA编码新方案,提高了边权值编码的信噪比,通过一系列生物操作,筛选出问题的精确解.和单纯DNA超级计算或电子计算机指定结点路由算法相比,文中算法可显著扩大理论上待求解问题的规模. 关键词 DNA计算；松散指定路由；指定结点路由；MPLS ASON 中图法分类号 TP301 DOI号: 10.3724/SP.J.1016.2009.02373