随机时间依赖网络的K期望寿命最短路径算法研究

• 作者: 刘平郁 赵文杰 郭守堂
• 来源期刊: 电脑与信息技术
• 学科: 工学
• 关键词: STD网络 一致可靠性 可靠优先权.
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 人工智能与算法研究
• 页码范围: 12-15
• 页数: 4页
• 分类号: TP311
• 字数: 3077字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-1228.2009.06.005

摘要

在交通网络和数据网络中,网络特征(如弧的权值、结点耗费等)既具有随机性又具有时间依赖性,这样的网络称之为随机时间依赖网络,简记为STD网络.在实践中,STD网络模型比传统网络模型具有更广泛的应用.由于随机性和时间依赖性引入到网络模型中,使得最短路径问题变得复杂化和多样化,传统的最短路径算法已不再适应这样复杂的网络环境,这就迫使我们寻求新的解决方法.本文解决的问题是,STD网络中,在任意时刻从单源点出发到达单目的地的预先K期望最短路径问题.我们将可靠性理论应用于该问题的求解中,推导出新优势判别法,使得传统判别法中的参数由二维降到一维,减小了路径间不可比较的可能性,既节省了存储空间又加快了搜索速度.然后,设计并实现了求解该问题的K_RELSP算法,并通过试验验证了该算法具有很高的运行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵文杰	中国医科大学高职学院	5	6	1.0	2.0
2	刘平郁		3	4	1.0	2.0
3	郭守堂	高速公路管理局大连管理处	1	1	1.0	1.0