边排序质量影响因素研究

• 作者: 潘竹生 莫毓昌
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 网络可靠度 二叉决策图 边界集 边排序
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 2091-2098
• 页数: 8页
• 分类号: TB114
• 字数: 3858字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2015.11.015

摘要

网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量.因此,边排序问题是网络可靠度BDD分析方法的重要问题.由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS和DFS,它们适用不同类型的网络.然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据.利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和BDD尺度(节点数目)之间的关系.实验结果表明,边界长度BSL与BDD尺度具有正相关性,即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值.这为特定网络选择(或设计)高性能边排序提供了重要的参考依据.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘竹生	浙江师范大学数理与信息工程学院	28	68	6.0	6.0
2	莫毓昌	浙江师范大学数理与信息工程学院	31	87	6.0	7.0