边排序质量影响因素研究.pdf
网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量.因此边排序问题是网络可靠度BDD分析方法的重要问题.由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS(BreadthFirstSearch)和DFS(DepthFirstSearch),它们适用不同类型的网络.然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据.本文利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和节点数目之间的关系.实验结果表明"边界长度BSL与BDD尺度具有正相关性",即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值.这为特定网络选择(或设计)高性能边排序提供了重要的参考依据.
作者：潘竹生莫毓昌
作者单位：浙江师范大学数理与信息工程学院金华321004
母体文献：2015全国理论计算机科学学术年会论文集
会议名称：2015全国理论计算机科学学术年会
会议时间：2015年10月30日
会议地点：金华
主办单位：中国计算机学会
语种：chi
分类号：
关键词：网络可靠度 边排序质量 边界长度 节点数目
在线出版日期：2017年7月25日
基金项目：
相似文献
相关博文
- 文件大小:
- 2.17 MB
- 下载次数:
- 60
-
高速下载
|
|
