网络可靠性分析中BFS策略与POS策略的性能比较  

Performance comparison between breadth-first ordering and priority ordering in network reliability analysis

作　　者：伍欢[1] 钟发荣[1] 莫毓昌[1] 潘竹生[1] 曾令国[1] 

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

出　　处：《山东大学学报（工学版）》2015年第2期43-48,共6页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省教育厅一般科研资助项目(Y201328072;Y201328293);浙江省计算机软件与理论重中之重学科开放课题资助项目(ZSDZZZZXK24)

摘　　要：为探究启发式边排序策略性能和网络结构特征的相关性,并建立网络结构特征依赖的边排序策略选择方法,基于4种常用的规则网络对BFS(breadth-first search)和POS(priority ordering search)两种策略的性能展开研究。通过试验分析比较了4种网络下BFS和POS两种策略的BDD(binary decision diagram)尺度与总体运行时间等性能数据。研究结果表明:在规则网络结构中,不同的排序策略适用于不同的网络结构。在Torus和Square网络中BFS策略优于POS策略;在De Bruijn和Nearest-neighbor网络中POS策略普遍优于BFS策略。该结论为特定网络选取最优或次优启发式边排序策略提供了依据。In order to explore the correlation between edge ordering heuristics and characteristics of network structure, and to build the method of selecting heuristic relied on network structure, the performances of breadth-first search and priority ordering search were studied based on four kinds of regular network models. Some performance data, such as binary decision diagram size and runtime under two heuristics, were compared emphatically through the experiments. The experimental results showed that different ordering heuristics fitted different network structures： BFS was generally better than POS in the networks of Torus and Square, and POS was generally better than BFS in the De Bruijn and Nea- rest-neighbor networks. These results could provide reference for choosing the optimal or suboptimal edge ordering heu- ristic for the particular regular network.

关 键 词：边排序策略 规则网络 BDD BFS POS 

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