边排序质量影响因素研究

来源：计算机工程与科学杂志2015年第11期北京时间：

作者：潘竹生,莫毓昌

单位：浙江师范大学数理与信息工程学院，浙江 金华 321004

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

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

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