(18.207.129.82) 您好!臺灣時間:2021/04/19 20:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:高明達
研究生(外文):GAO, MING-DA
論文名稱:直角距離之m中心問題的演算法
論文名稱(外文):Algorithms for the rectilinear m-center problem
指導教授:李家同李家同引用關係
指導教授(外文):LI, JIA-TONG
學位類別:博士
校院名稱:國立清華大學
系所名稱:計算機管理決策研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:1988
畢業學年度:76
語文別:中文
論文頁數:122
中文關鍵詞:演算法直角距離
相關次數:
  • 被引用被引用:0
  • 點閱點閱:222
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在平面上給n 個帶有權重的需求點,其直角距離之m 中心問題為:求m 個服務點,使
需求點與其最近的服務點的加權直角距離中最大的最小。如需求點的權重皆相同,稱
之為無加權m 中心問題;否則,稱之為加權m 中心問題。直角距離之m 中心問題為最
重要的服務設施設置地點問題之一,適合於模擬城市地區緊急服務設施之設置。
當m 視為輸入參數時,直角距離之m 中心問題已被證明為NP- 完備。在此論文,更進
一步被證明其任何多項式時間的近似演算法的最壞狀況誤差比例大於或等於2,除非
NP=P 。且我們也提出一多項式時間,最壞狀況誤差比例恰為2的近似演算法。
當m 視為常數時,對於無加權直角距離之m 中心問題,m 大於或等於4,我們提出O
(n^(m-2) ㏒ n)時間的演算法,改進前人O (n^(2m-5) ㏒ n) 時間的演算法。對
於加權直角距離之雙中心問題和三中心問題,我們各提出近乎最佳時間複雜度的O (
n ㏒ n)時間的演算法。
概念上,這些演算法都利用需求點集合的上、下、左、右四種極點來限制服務點的選
取範圍以得到相當少數的候選解,而最佳解就在候選解之中。
目錄
摘要
誌謝
Chapter 1. Introduction
Chapter 2. Problem Definition and Notations
Chapter 3. A Review of Previous Research Results
Section 3.1 The Rectilinear 1-Center Problem
Section 3.2 The Unweighted Rectilinear 2-Center and 3-Center Problems
Section 3.3 The Rectilinear m-Center Problem
Chapter 4. Unweighted Rectilinear m-Center Problem, m>_4
Section 4-1 Notations
Section 4-2 An Algorithm for the Unweighted Rectilinear m-Center Problem
Section 4-3 A Modified Algorithm for the Unweighted Rectilinear m-Center Problem
Chapter 5. The Complexity of Approximation Algorithms for the Rectilinear m-Center Problem
Section 5-1 A Review of Previous Work
Section 5-2 Our Reduction
Section 5-3 An Optimal Approximation Algorithm
Chapter 6. Weighted Rectilinear 2-Center and 3-center
Section 6-1 Notations
Section 6-2 Algorithms for the Decision Problems
Section 6-3 Algorithms fro the Optimization Problems
Chapter 7. Concluding Remarks
References
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔