优先级边排序策略及其性能分析  

Priority Edge Ordering Strategy and Performance Analysis

作　　者：潘竹生[1] 莫毓昌[1] 赵建民[1] 

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

出　　处：《计算机科学》2014年第8期81-84,105,共5页Computer Science

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

摘　　要：网络可靠度BDD分析的计算复杂度与BDD尺度线性相关,而BDD尺度依赖边排序策略,边排序问题是BDD网络可靠度分析的重要问题。从网络结构特性出发,设计了优先级边排序策略并深入研究了在该策略下不同排序起点对BDD尺度的影响。实验结果表明:源点和网络中心不是高性能排序起点,最佳排序起点分布在网络边缘,网络中心点为最差排序起点。该结论可为揭示边排序影响BDD尺度的本质以及研究高效启发性边排序策略提供重要参考依据。The computational complexity of BDD-based network reliability analysis linearly depends on the size of BDD which largely depends on the edge ordering strategies. What~ s more, the edge ordering issue is very important to the analysis of BDD-based network reliability. We firstly designed the Priority Edge Ordering Strategy （PEOS） from the characteristics of network structure,and then researched the relationship between the BDD size and different ordering star-ting points with PEOS. The experiment results show that the high-performance starting points are not the source or the center but always located in the boundary of a given network. On the contrary, the center is the worst ordering starting point. These conclusions can provide important reference for the PEOS how to affect the BDD size and how to design a high-performance edge ordering strategy.

关 键 词：网络可靠度 二叉决策图 优先级边排序策略 

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