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

A novel heuristic edge ordering strategy and its performance analysis

作　　者：潘竹生[1] 莫毓昌[1] 钟发荣[1] 刘轩[1] 伍欢[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《计算机工程与科学》2014年第11期2119-2127,共9页Computer Engineering & Science

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

摘　　要：网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量。由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS(Breadth-First-Search)和DFS(Depth-First-Search)。针对边排序问题,从分析基于边界集(Boundary Set)的BDD构建方法 BDD-BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略。性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间。The computational complexity of the BDD （Binary Decision Diagram） based network reliability method is linear correlated to the size of BDD that heavily depends on the quality of edge ordering.Because it is still NP-hard to find the optimum edge ordering,heuristic ordering methods such as BFS （Breadth-First-Search） or DFS （Depth-First-Search） are commonly used in practice.For the edge ordering strategy,boundary set is first used to analyze the characteristics of constructing BDD,and then a high performance edge ordering strategy based on the boundary set is proposed.Several experiments show that the new strategy outperforms the classic methods such as DFS and BFS.The results extend new space for network reliability analysis method using BDD in large-scale networks.

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

分 类 号：TB114[理学—概率论与数理统计]