Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69909
Title: | 路徑圖上anti-k-centrum 選址問題 The anti-k-centrum location problem on a path |
Authors: | Ming-Hsuan Hsieh 謝名宣 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 路徑圖,定址問題,演算法,動態優先權序列,加權距離,k-level,anti-k-centrum, path,location problem,k-level,anti-k-centrum,kinetic priority queue,algorithm,weighted distance, |
Publication Year : | 2016 |
Degree: | 碩士 |
Abstract: | 我們研究在給定的路徑圖上如何找出一個機構的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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-105-1.pdf Restricted Access | 907.39 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.