請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382
標題: | 路徑圖上權重備份雙中心問題 The Weighted Backup 2-center Problem on Paths |
作者: | Ming-Wei Shao 邵明偉 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 圖論,權重距離,備份雙中心,路徑圖,位置問題, graph theory,weighted distance,backup 2-center,path,location problem, |
出版年 : | 2014 |
學位: | 碩士 |
摘要: | 本論文引用王教授所提出的基於可靠性的備份雙中心模式,在這模式中,每個設施
皆有壞掉機率。我們假設此二設施不會同時壞掉,在這前提下一旦有一設施壞掉,另 一設施需負責所有服務。在路徑圖上具權重的備份雙中心問題中,我們想在點帶權重 之路徑圖上架設此二設施,使得權重距離期望值最小。假設路徑圖上有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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 573.78 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。