韋伯問題之避障趨近解

10.29428/9789860544169.201801.0043

詹景裕；鄔宗羲；呂紹偉；林獻堂

韋伯點 ； 避障

NCS 2017 全國計算機會議

2017（2018 / 01 / 01）

227 - 231

繁體中文

著名的韋伯問題在工業工程及地理資訊系統上是個重要的課題，在實際的應用面上，可以選定倉庫的位置，使倉庫和消費者間的距離總和最小化。我們提出的方法以三角網格法和Wave Propagation 的概念並結合Visibility Graph 與Ahuja-Dijkstra 最短路徑找出避障之韋伯點趨近解。其中，總時間複雜度為0(kn^3)，其中k 與n 分別為三角剖分的次數與來源點的數目。