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

• 作者: 刘学军 张水舰 杨洋
• 来源期刊: 物理学报
• 学科: 物理学
• 关键词: 最短路径问题 遗传算法 动态随机网络
• 年，卷（期）: 2012,（16）
• 所属期刊栏目: 总论
• 页码范围: 1-10
• 分类号: O415.5
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨洋	南京师范大学虚拟地理环境教育部重点实验室	11	46	3.0	6.0
2	刘学军	南京师范大学虚拟地理环境教育部重点实验室	110	2264	26.0	44.0
3	张水舰	南京师范大学虚拟地理环境教育部重点实验室	1	26	1.0	1.0