计算机工程与科学
計算機工程與科學
계산궤공정여과학
Computer Engineering and Science
2015年
11期
2091-2098
,共8页
网络可靠度%二叉决策图%边界集%边排序
網絡可靠度%二扠決策圖%邊界集%邊排序
망락가고도%이차결책도%변계집%변배서
network reliability%binary decision diagram(BDD)%boundary set%edge ordering
网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量.因此,边排序问题是网络可靠度BDD分析方法的重要问题.由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS和DFS,它们适用不同类型的网络.然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据.利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和BDD尺度(节点数目)之间的关系.实验结果表明,边界长度BSL与BDD尺度具有正相关性,即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值.这为特定网络选择(或设计)高性能边排序提供了重要的参考依据.
網絡可靠度BDD分析方法的計算性能與BDD呎度緊密相關,而BDD呎度嚴重依賴邊排序質量.因此,邊排序問題是網絡可靠度BDD分析方法的重要問題.由于求解最優邊排序是一箇NP問題,在實際網絡可靠度分析中,通常採用啟髮式邊排序策略如BFS和DFS,它們適用不同類型的網絡.然而,對于給定網絡,採用何種邊排序策略更優,有哪些因素影響邊排序質量,迄今沒有給齣評判依據.利用邊界集思想,提齣"邊界長度(BSL)"概唸,併用邊界長度BSL錶徵邊排序質量,揭示邊界長度BSL和BDD呎度(節點數目)之間的關繫.實驗結果錶明,邊界長度BSL與BDD呎度具有正相關性,即較小BSL對應的BDD呎度較小,較大BSL對應的BDD呎度較大,多數情況下,BSL取最值時,BDD呎度能取到(或接近)最值.這為特定網絡選擇(或設計)高性能邊排序提供瞭重要的參攷依據.
망락가고도BDD분석방법적계산성능여BDD척도긴밀상관,이BDD척도엄중의뢰변배서질량.인차,변배서문제시망락가고도BDD분석방법적중요문제.유우구해최우변배서시일개NP문제,재실제망락가고도분석중,통상채용계발식변배서책략여BFS화DFS,타문괄용불동류형적망락.연이,대우급정망락,채용하충변배서책략경우,유나사인소영향변배서질량,흘금몰유급출평판의거.이용변계집사상,제출"변계장도(BSL)"개념,병용변계장도BSL표정변배서질량,게시변계장도BSL화BDD척도(절점수목)지간적관계.실험결과표명,변계장도BSL여BDD척도구유정상관성,즉교소BSL대응적BDD척도교소,교대BSL대응적BDD척도교대,다수정황하,BSL취최치시,BDD척도능취도(혹접근)최치.저위특정망락선택(혹설계)고성능변배서제공료중요적삼고의거.
