請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69909
標題: | 路徑圖上anti-k-centrum 選址問題 The anti-k-centrum location problem on a path |
作者: | Ming-Hsuan Hsieh 謝名宣 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 路徑圖,定址問題,演算法,動態優先權序列,加權距離,k-level,anti-k-centrum, path,location problem,k-level,anti-k-centrum,kinetic priority queue,algorithm,weighted distance, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 我們研究在給定的路徑圖上如何找出一個機構的anti-k-centrum 位址。意思是說,路徑圖上每一頂點到此機構的加權距離,取前k 小的值加總要最大。
我們提出了兩種類似的演算法,第一個演算法我們將所想到的方式一步一步執行,其時間複雜度取決於所使用的k-level 演算法。Timothy 提出一隨機演算法求k-level,時間複雜度為O(n log n + nk1/3),由Dey 證明在最壞狀況下k-level 的轉折點個數為m = O(nk1/3),n是路徑圖的頂點個數,k 是一小於n 的常數。 第二個演算法利用了動態優先權序列來求解,時間複雜度為O(T(n; n + m)),其中T(n;m) = O(m (n)), (n) 表示一逆阿克曼函數。 In this thesis, we plan to find a facility placed on the edge of a given path, which meets the demand constraints of anti-k-centrum location problem. We provide two algorithms to solve the problem. The first algorithm uses k-level algorithm helping us, the time complexity of the first algorithm depends on the speed of constructing the k-level. Timothy showed a randomized algorithm constructing the k-level, that runs an expected time O(n log n + nk1/3), n is the number of vertices on the given path, with the bound by Dey showing that the number of turning points on k-level is m = O(nk1/3) in the worst case. The second algorithm uses an abstract data structure call kinetic priority queue. The time complexity is O(T(n,n+m)),which T(n,m) = O(m (n)), and (n) denote the inverse Ackermann function. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69909 |
DOI: | 10.6342/NTU201800472 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 907.39 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。