计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
11期
2119-2127
,共9页
潘竹生%莫毓昌%钟发荣%刘轩%伍欢
潘竹生%莫毓昌%鐘髮榮%劉軒%伍歡
반죽생%막육창%종발영%류헌%오환
网络可靠度%二叉决策图%边界集%边排序
網絡可靠度%二扠決策圖%邊界集%邊排序
망락가고도%이차결책도%변계집%변배서
network reliability%binary decision diagram%boundary set%edge ordering
网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量.由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS(Breadth-First-Search)和DFS (Depth-First-Search).针对边排序问题,从分析基于边界集(Boundary Set)的BDD构建方法BDD-BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略.性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间.
網絡可靠度BDD分析方法的計算複雜度與BDD呎度線性相關,而BDD呎度嚴重依賴邊排序質量.由于求解最優邊排序是一箇NP問題,在實際應用中,通常採用啟髮式邊排序策略如BFS(Breadth-First-Search)和DFS (Depth-First-Search).針對邊排序問題,從分析基于邊界集(Boundary Set)的BDD構建方法BDD-BS齣髮,將邊界集思想應用于邊排序過程,提齣瞭一種新的啟髮式邊排序策略.性能分析和大量實驗錶明,新設計的邊排序策略性能優于經典的DFS和BFS策略,該結果為網絡可靠度BDD分析方法在大規模網絡中的應用拓展瞭新的空間.
망락가고도BDD분석방법적계산복잡도여BDD척도선성상관,이BDD척도엄중의뢰변배서질량.유우구해최우변배서시일개NP문제,재실제응용중,통상채용계발식변배서책략여BFS(Breadth-First-Search)화DFS (Depth-First-Search).침대변배서문제,종분석기우변계집(Boundary Set)적BDD구건방법BDD-BS출발,장변계집사상응용우변배서과정,제출료일충신적계발식변배서책략.성능분석화대량실험표명,신설계적변배서책략성능우우경전적DFS화BFS책략,해결과위망락가고도BDD분석방법재대규모망락중적응용탁전료신적공간.
