A New Universal Generating Function Method to Search for all Minimal Paths Generate in Networks

應用新型通用生成函數尋找網路圖形中最小路徑之研究

李慧文

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2014年)

摘要

在日常生活中有許多系統都是網路架構的應用，像是基地台配置，電力傳輸系統等等。系統能否運作順暢，網路可靠度的評估是一個非常重要的衡量指標，所以估算網路可靠度成為了一個非常重要的問題。而最小路徑集合是估算網路可靠度基本的工具之一，由於網路可靠度的評估是一個NP-hard問題，在先前的研究中，我們已經可以運用通用生成函數找出網路圖形中所有最小路徑，但當在原始的網路圖形中新增或減少一條邊的時候，必須再重頭執行一次演算法的所有流程。因為在現實世界裡的網路圖型幾乎都是非常複雜的，所以每次運算都會花很長的時間。
本研究提供一種特定的通用生成函數，由於特定通用生成函數旨在應用來找尋出增加或減少路徑後所獲得或失去的最小路徑，所以能夠藉由將沒有影響的因子盡可能在特定通用生成函數的 中移除，以簡化 的計算，使運算的複雜度大幅降低，減少運算所需時間。最後將用一個例子去說明增加或減少一條邊後網路圖型將會獲得或損失哪些最小路徑，再以此計算增加或減少路徑後網路可靠度的變化。

關鍵字

特定通用生成函數 ； 最小路徑 ； 網路可靠度

參考文獻

1.Ahuja, S.P. Performance based reliability optimization for computer networks. in Southeastcon '97. Engineering new New Century., Proceedings. IEEE. 1997.

2.Aven, T., Availability evaluation of oil/gas production and transportation systems. Reliability Engineering, 1987. 18(1): p. 35-44.

3.Hongshan, Z., Z. Chao, and H. Ren. Power transmission network vulnerable region identifying based on complex network theory. in Electric Utility Deregulation and Restructuring and Power Technologies, 2008. DRPT 2008. Third International Conference on. 2008.

5.Wei-Chang, Y., A Simple Heuristic Algorithm for Generating All Minimal Paths. Reliability, IEEE Transactions on, 2007. 56(3): p. 488-494.

6.Wei-Chang, Y., The Extension of Universal Generating Function Method to Search for all one-to-many d-Minimal Paths of Acyclic Multi-State-Arc Flow-Conservation Networks. Reliability, IEEE Transactions on, 2008. 57(1): p. 94-102.