【摘要】 网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量。因此,边排序问题是网络可靠度BDD分析方法的重要问题。由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS和DFS,它们适用不同类型的网络。然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据。利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和BDD尺度(节点数目)之间的关系。实验结果表明,边界长度BSL与BDD尺度具有正相关性,即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值。这为特定网络选择(或设计)高性能边排序提供了重要的参考依据。更多还原

【Abstract】 The computational complexity of network reliability analysis based on the Binary Decision Diagram(BDD)is closely related to the size of BDD,which depends crucially on the quality of edge ordering.So it is of importance to find the best edge ordering that attempts to minimize the memory using BDD manipulation.However,it is still NP-hard to find the optimal edge ordering.In practice,heuristic ordering methods such as Breadth-First-Search(BFS)or Depth-First-Search(DFS),which are suitable for different types of networks,are commonly used.Unfortunately,no formal guidelines or factors which determine the quality of edge ordering are available for choosing a better heuristic approach for the given network.In this work,characterizing the Boundary Set Length(BSL)as the quality of edge ordering,we reveal the relationship between the BSL and the size of BDD.Empirical studies show that the BSL has positive correlation with the size of BDD.This means the smaller the BSL of an edge ordering,the smaller the size of BDD model generated.In most cases,the size of the BDD can get(or be close to)the extreme value when the BSL has its extreme one.This conclusion is useful for choosing or designing high performance edge ordering for a given network.更多还原