必经节点集约束型无环最短路径算法研究

摘要：

有向网络必经节点集约束型无环最短路径问题是一个NP-hard问题,而国内外对于这个问题的研究较少.基于遗传算法和Dijkstra算法,提出了解决问题的方法.将研究问题分解为只含源点、目的节点和必经节点集的非对称TSP问题和消除环路问题,首先通过遗传算法求解TSP问题得到最优必经点序列,而求解的最优必经点序列组成的路径是有环路径,然后通过分段Dijkstra破环策略解决环路问题.经过实例分析验证,算法是有效可行的.

关键词： 有向网络 必经节点 集约束型无环最短路径问题 遗传算法 破环策略

作者: 李东 王丹东 王强

作者单位: 杭州电子科技大学计算机学院,浙江 杭州

会议类型: 国内会议

会议名称: 杭州电子科技大学第九届研究生IT创新学术论坛

会议地点: 杭州

会议语种:中文

页码: 311-320

在线出版日期: 2016-11-23（万方平台首次上网日期，不代表论文的发表时间）