指導教授：趙坤茂臺灣大學：資訊工程學研究所邵明偉Shao, Ming-WeiMing-WeiShao2014-11-262018-07-052014-11-262018-07-052014http://ntur.lib.ntu.edu.tw//handle/246246/261546本論文引用王教授所提出的基於可靠性的備份雙中心模式，在這模式中，每個設施 皆有壞掉機率。我們假設此二設施不會同時壞掉，在這前提下一旦有一設施壞掉，另 一設施需負責所有服務。在路徑圖上具權重的備份雙中心問題中，我們想在點帶權重 之路徑圖上架設此二設施，使得權重距離期望值最小。假設路徑圖上有n個點，我們 建立了一個時間複雜度為O(n)的演算法。In this thesis, we apply the reliability-based backup 2-center model proposed by Wang, where each facility may fail with a given probability. Once a facility fails, the other has to be responsible for all the services. We assume that two facilities do not fail at the same time. In the weighted backup 2-center problem on paths, we want to locate two facilities on vertex-weighted paths such that the expected weighted distance is minimized. We construct an O(n)-time algorithm, where n is the number of vertices in the given path.1 Introduction 1 2 Problem De nition and Notation 4 3 The Weighted Backup 2-center Problem on paths 7 3.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Properties of Weighted Backup 2-center . . . . . . . . . . . . . . . . . . . . 9 3.3 The First Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Methods for the enhancement . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 A Faster Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Conclusion 27 4.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27587553 bytesapplication/pdf論文公開時間：2014/08/01論文使用權限：同意有償授權(權利金給回饋學校)圖論權重距離備份雙中心路徑圖位置問題thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/261546/1/ntu-103-R01922128-1.pdf