求解最短路径问题的DNA动态规划算法

DNA dynamic programmimg algorithm for solving the shortest path problem

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。

The shortest path problem is a problem of combinatorial optimization,many problems in transportation,engineering and management can be solved by being converted to the shortest path problem.We give a DNA dynamic programmimg algorithm for solving the shortest path problem using DNA computing of a new parallel model in this paper,it only needs 7n-1 1 biological operations at most.