Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68497Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 呂育道(Yuh-Dauh Lyuu) | |
| dc.contributor.author | Yu-Chuan Liu | en |
| dc.contributor.author | 劉育全 | zh_TW |
| dc.date.accessioned | 2021-06-17T02:23:02Z | - |
| dc.date.available | 2021-08-24 | |
| dc.date.copyright | 2017-08-24 | |
| dc.date.issued | 2017 | |
| dc.date.submitted | 2017-08-19 | |
| dc.identifier.citation | Arora, S. (1997). Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of 38th Symposium on Foundations of Computer Science, 1997, Miami Beach, Florida, pages 554–563.
Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh. Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6):791–812. Drake, D. E., and Hougardy, S. (2003a). Linear time local improvements for weighted matchings in graphs. In Proceedings of 2nd International Workshop on Experimental and Efficient Algorithms, 2003, Ascona, Switzerland, pages 107–119. Drake, D. E., and Hougardy, S. (2003b). A simple approximation algorithm for the weighted matching problem. Information Processing Letters, 85(4):211–213. Duan, R., and Pettie, S. (2010). Approximating maximum weight matching in near-linear time. In Proceedings of 51st Symposium on Foundations of Computer Science, 2010, Las Vegas, pages 673–682. Duan, R., and Pettie, S. (2014). Linear-time approximation for maximum weight matching. Journal of the ACM, 61(1):1. Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3):449–467. Gabow, H. N. (1974). Implementation of algorithms for maximum matching on nonbipartite graphs. Department of Computer Science, Stanford University. Gabow, H. N. (1990). Data structures for weighted matching and nearest common ancestors with linking. Department of Computer Science, University of Colorado, Boulder. Gabow, H. N., Galil, Z., and Spencer, T. H. (1984). Efficient implementation of graph algorithms using contraction. In Proceedings of 25th Symposium on Foundations of Computer Science, 1984, Singer Island, Florida, pages 347–357. Galil, Z., Micali, S., and Gabow, H. (1986). An O(EVlogV) algorithm for finding a maximal weighted matching in general graphs. SIAM Journal on Computing, 15(1):120–130. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680. Lawler, E. L. (2001). Combinatorial optimization: networks and matroids. Holt, Rinehart, and Winston, New York. Lin, S., and Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21(2):498–516. Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10):2245–2269. Pettie, S., and Sanders, P. (2004). A simpler linear time 2/3- ε approximation for maximum weight matching. Information Processing Letters, 91(6):271–276. Preis, R. (1999). Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In Proceedings of Symposium on Theoretical Aspects of Computer Science, 1999, Trier, Germany, pages 259–269. Reingold, E. M., and Tarjan, R. E. (1981). On a greedy heuristic for complete matching. SIAM Journal on Computing, 10(4):676–681. Vaidya, P. M. (1989). Geometry helps in matching. SIAM Journal on Computing, 18(6):1201–1225. Varadarajan, K. R. (1998). A divide-and-conquer algorithm for min-cost perfect matching in the plane. In Proceedings of 39th Symposium on Foundations of Computer Science, 1998, Palo Alto, California, pages 320–329. Varadarajan, K. R., and Agarwal, P. K. (1999). Approximation algorithms for bipartite and non-bipartite matching in the plane. In Proceddings of Symposium on Discrete Algorithms, 1999, Baltimore, pages 805–814. Vazirani, V. V. (2013). Approximation algorithms. Springer Science & Business Media. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68497 | - |
| dc.description.abstract | 在本論文中,我們對於平面上的最小權完美匹配問題提出了幾個不同的啟發式演算法。基於座標平面上的三角不等式性質,提出一個先隨機一組完美匹配並優化它的 local search 演算法,接著在這個算法的基礎上做出許多的改進,最後得出數個還不錯的演算法,在實務上有的可以在和 Blossom 演算法相比下加速數十倍的情況下找出和最佳解誤差不到 2% 的解,或著是在加速數倍的情況下找出誤差 0.5% 左右的的解。 | zh_TW |
| dc.description.abstract | In this thesis, we provide some heuristic algorithms for minimum-weight perfect matching problem on a plane. First, we provide a local search algorithm based on triangle inequality. Then we try many methods to improve this algorithm. Finally we get some good algorithms. One can be 20-30 times faster than Blossom algorithm with 2% error and other one can be 3-4 times faster than Blossom algorithm with 0.5% error. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T02:23:02Z (GMT). No. of bitstreams: 1 ntu-106-R04922040-1.pdf: 684297 bytes, checksum: 5e75246bbd02d10ec51c8c2c3eace694 (MD5) Previous issue date: 2017 | en |
| dc.description.tableofcontents | 口試委員會審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 圖目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 表目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 第一章 緒論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 研究目的與方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 相關研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 一般圖最大(最小)權匹配 . . . . . . . . . . . . . . . . . . . 2 1.3.2 平面上的最小權匹配 . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 論文架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 第二章 演算法與實驗分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 2-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 匹配合併 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 模擬退火 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 動態找環 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 動態找環 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.2 動態找環及 2-opt . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3 動態找環 2-opt 篩選匹配演算法 . . . . . . . . . . . . . . . . . 24 2.5 實驗結果分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5.1 匹配合併演算法匹配個數實驗 . . . . . . . . . . . . . . . . . . 27 2.5.2 動態找環 2-opt 匹配合併演算法匹配個數實驗 . . . . . . . . . 27 2.5.3 動態找環 2-opt 篩選匹配演算法匹配個數實驗 . . . . . . . . . 28 2.5.4 整體效能實驗 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 第三章 應用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . 31 第四章 結論與未來展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 未來展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 | |
| dc.language.iso | zh-TW | |
| dc.subject | 近似比 | zh_TW |
| dc.subject | 啟發式演算法 | zh_TW |
| dc.subject | 最小權完美匹配 | zh_TW |
| dc.subject | minimum-weight perfect matching | en |
| dc.subject | heuristic | en |
| dc.subject | approximation ratio | en |
| dc.title | 平面上的最小權完美匹配之啟發式演算法 | zh_TW |
| dc.title | Heuristics for the Minimum-Weight Perfect Matching Problem on a Plane | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 105-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王釧茹(Chuan-Ju Wang),張經略(Ching-Lueh Chang) | |
| dc.subject.keyword | 最小權完美匹配,啟發式演算法,近似比, | zh_TW |
| dc.subject.keyword | minimum-weight perfect matching,heuristic,approximation ratio, | en |
| dc.relation.page | 38 | |
| dc.identifier.doi | 10.6342/NTU201703824 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2017-08-20 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| Appears in Collections: | 資訊工程學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-106-1.pdf Restricted Access | 668.26 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.