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

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

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

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

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

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

网络可靠度;二叉决策图;边界集;边排序

1 引言

网络可靠度二叉决策图BDD(Binary Decide Diagram)分析方法包括边排序、等价BDD生成和指标数据计算三个基本过程。其中，等价BDD生成是关键，生成的BDD越小，即BDD尺度(节点数目)越小，可靠度分析方法的性能就越好。Kuo S-Y等人[1～3]利用边扩展EP(Edge Expansion)技术来有效识别同构子网，提出自底向上的紧凑BDD构建方法；Hardy G等人[4,5]利用边界分区(Partition-BS)有效识别同构子网，提出自顶向下的紧凑BDD构建方法，这两种方法在构建过程中存在冗余；Pan Zhu-sheng等人[6]通过识别冗余子网，消除了冗余BDD，进一步改进了性能。然而，BDD的紧凑程度更大程度上依赖边排序质量[7]，不同质量的边排序结果导致BDD尺度跨越几个数量级[8]，高质量的边排序指导生成最为紧凑的BDD。……