一種使用多變數互補方式的網路可靠度改良演算法則

An Improved Algorithm for Calculating the Network Reliability by the Subproduct Inversion

10.29987/CCUHKJE.200606.0007

劉熙海(Hsi-Hai Liu)；張宇舜(Yu-Shun Chang)；吳孟龍(Meng-Lung Wu)

SDP項 ； 同調系統 ； 非同調系統 ； 最小路徑 ； 布林函數

華岡工程學報

20期（2006 / 06 / 01）

55 - 60

繁體中文

本專題提出一種新的演算方法：HLR(Heidtmann-Liu-Revised)演算法則。此演算法是採用多變數互補(Subproduct Inversion)的方式，來計算非同調網路系統的可靠度。這種新的演算法則，可以應用於二進位同調系統與非同調系統中，並且經由此演算法則，可以求得比目前已知之任何演算法則更少項數的SDP(Sum of Disjointed Products)型式。由於在系統可靠度的公式中，SDP項的數目被大幅度的化簡。因此，使得在計算時間上可以被減少許多，尤其在越龐大越複雜的網路系統中，其改善現象會越顯著。

This paper presents a new method, the HLR algorithm, for calculating the reliability of non-coherent network by the subproduct inversion. This new method is applicable for both binary coherent and non-coherent systems, and it produces the least number of SDP term amongst all existing algorithms. Because the number of SDP terms in the binary system reliability formula is considerably reduced, there will be sharp computational saving when processing larger paths of complex binary system.