动态随机最短路径算法研究

摘要：

静态最短路径问题已经得到很好解决，然而现实中的网络大多具有动态性和随机性．网络弧和节点的状态及耗费不仅具有不确定性且相互关联，弧和节点的耗费都服从一定的概率分布，因此把最短路径问题看作是一个动态随机优化问题更具有一般性．文中分析了网络弧和节点的动态随机特性及其相互关系，定义了动态随机最短路径；给出了动态随机最短路径优化数学模型，提出了一种动态随机最短路径遗传算法；针对网络的拓扑特性设计了高效合理的遗传算子．实验结果表明，文中提出的模型和算法能有效地解决动态随机最短路径问题，可以运用到交通、通信等网络的网络流随机优化问题中．

关键词：最短路径问题、遗传算法、动态随机网络

所属期刊栏目：61

分类号：O415.5(理论物理学)

资助基金：国家高技术研究发展计划2007AA122238;江苏省博士后基金1101016B资助的课题

在线出版日期：2012-10-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1-10