一种新的启发式边排序策略及其性能分析

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

摘要

网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量.由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS(Breadth-First-Search)和DFS (Depth-First-Search).针对边排序问题,从分析基于边界集(Boundary Set)的BDD构建方法BDD-BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略.性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘竹生	浙江师范大学数理与信息工程学院	28	68	6.0	6.0
2	莫毓昌	浙江师范大学数理与信息工程学院	31	87	6.0	7.0
3	钟发荣	浙江师范大学数理与信息工程学院	25	46	4.0	5.0
4	伍欢	浙江师范大学数理与信息工程学院	3	7	2.0	2.0
5	刘轩	浙江师范大学数理与信息工程学院	2	7	2.0	2.0