论文部分内容阅读
带约束路由算法问题一直是通信领域的热点问题。然而，多数特殊约束路由问题为NP-完全问题，除非NP=P，否则无法给出多项式时间算法。对于这些问题，已经出现各种伪多项式算法，但这些算法必须在一定的限制条件内才能保证算法时间效率。1994年Adleman博士首次提出了DNA计算的概念,并设计了DNA算法成功解决了7个顶点的哈密尔顿路径问题，显示了DNA计算解决复杂问题的巨大潜力。由于路由问题的特点，可以利用DNA计算高度的并行性将问题的时间复杂度转化为DNA分子链的空间复杂度，从而在多项式时间内得出问题的精确解。本文提出一套通用的路由问题的DNA编码方案，并对两种特殊的带约束路由问题进行DNA计算算法设计。指定结点路由问题可一般性地定义为带指定结点约束的最短路径问题，是一个NP难问题。本文提出一种将电子计算机算法与DNA计算算法相结合的方法求解指定结点路由问题。算法由转化算法，源宿结点搜索切割算法，转化图结果搜索算法和结果读取算法共四个子算法组成。分析结果表明：执行算法的电子计算机部分可显著减少参与生化反应的DNA链的数量，在试管内DNA链数恒定的情况下，增加了可解决问题的结点和链路的规模。算法的DNA计算部分对最短路径进行并行搜索，可以在多项式时间内得出问题的解。链路分离路径对可用于保障网络传输稳定性，增加传输带宽和实现负载均衡。本文对计算链路分离路径对的电子计算机算法LIDOMPA算法进行算法优化改进，提出基于DNA计算的高效并行算法。该算法主要由最短路径搜索算法，路径分类算法，链路分离路径构造算法组成。在DNA计算中，可以将LIDOMPA算法中多个需要指数时间复杂度的操作改进为多项式时间。本文主要探讨了DNA计算针对两种特定约束路由问题的算法，并为其它路由问题的DNA计算编码和基本操作提供了通用方案。只要未来关于DNA计算的生物技术走向成熟，DNA计算完全可以在路由问题中发挥更大的作用。