时间依赖无向中国邮路问题的分支限界算法

• 作者: 吕凯 孙景昊 肖宏业 谭国真
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 时变网络 中国邮路问题 分支限界 先进先出
• 年，卷（期）: 2011,（2）
• 页码范围: 110-113
• 分类号: TP393
• 字数: 4873字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.02.026

摘要

时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型.当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难.首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds& Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭国真	大连理工大学计算机科学与技术学院	56	946	13.0	29.0
2	孙景昊	大连理工大学计算机科学与技术学院	5	18	3.0	4.0
3	肖宏业	大连理工大学计算机科学与技术学院	1	3	1.0	1.0
4	吕凯	大连理工大学计算机科学与技术学院	1	3	1.0	1.0