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

J4 ›› 2014, Vol. 36 ›› Issue (11): 2119-2127.

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

潘竹生,莫毓昌,钟发荣,刘轩,伍欢

(浙江师范大学数理与信息工程学院,浙江金华 321004)

收稿日期:2014-06-15 修回日期:2014-08-13 出版日期:2014-11-25 发布日期:2014-11-25
基金资助:
国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省重中之重学科开放课题资助项目(ZSDZZZZXK24);浙江省教育厅项目（Y201328072）

A novel heuristic edge ordering strategy
and its performance analysis

PAN Zhusheng,MO Yuchang,ZHONG Farong,LIU Xuan,WU Huan

(College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China)

Received:2014-06-15 Revised:2014-08-13 Online:2014-11-25 Published:2014-11-25

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: network reliability;binary decision diagram;boundary set;edge ordering.

潘竹生,莫毓昌,钟发荣,刘轩,伍欢. 一种新的启发式边排序策略及其性能分析[J]. J4, 2014, 36(11): 2119-2127.

PAN Zhusheng,MO Yuchang,ZHONG Farong,LIU Xuan,WU Huan. A novel heuristic edge ordering strategy
and its performance analysis [J]. J4, 2014, 36(11): 2119-2127.

[1]	潘竹生,莫毓昌. 边排序质量影响因素研究[J]. J4, 2015, 37(11): 2091-2098.
[2]	潘竹生,莫毓昌,钟发荣,赵建民. 网络可靠度BDD分析算法的性能改进[J]. J4, 2012, 34(9): 26-32.