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

摘要：

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

关键词：网络可靠度、二叉决策图、边界集、边排序

所属期刊栏目：36

分类号：TB114(工程基础科学)

资助基金：国家自然科学基金资助项目61272130;浙江省自然科学基金资助项目Y1100689;浙江省重中之重学科开放课题资助项目ZSDZZZZXK24;浙江省教育厅项目Y201328072

在线出版日期：2014-12-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2119-2127