k最短可靠路径及其优化问题

发布时间：2021-03-19 20:32

　　k最短路径在边失效模型中,存在一个等长路径的选择问题,基于可靠性的选择是有效的解决方案。这里提出了一种k最短路径限制下的可靠性模型来度量k最短路径,进一步把等长路径的选择问题转化为一个可靠性优化问题,即选择使得可靠性最大的k最短路径。最终通过设计近似算法有效地解决了优化问题,实例证明了该算法的有效性。 

【文章来源】：现代电子技术. 2020,43(23)北大核心

【文章页数】：4 页

【部分图文】：

网络G和子网络

网络G

图2 网络G表1表示对应不同k的三种算法的CPU运行时间。当k很小时，算法1具有最短的CPU运行时间，但是随着k的增加，时间将更长。算法2具有最长的CPU运行时间，并且随着k的增加，时间将更长，因为Rst (G)的计算是NP难问题。虽然当k=6时算法3的CPU运行时间比算法1长，但算法3的CPU运行时间随着k的增加没有太大变化。

【参考文献】：
期刊论文
[1]基于可靠性在结构健康监测系统中的备份点布控研究[J]. 诸震亚,邵方明.  现代电子技术. 2019(04)
[2]空间通信中的网络可靠性分析[J]. 李云飞.  现代电子技术. 2012(23)



本文编号：3090183