請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37694完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 呂育道(Yuh-Dauh Lyuu) | |
| dc.contributor.author | Hung-Pin Shih | en |
| dc.contributor.author | 石鴻賓 | zh_TW |
| dc.date.accessioned | 2021-06-13T15:39:02Z | - |
| dc.date.available | 2013-07-18 | |
| dc.date.copyright | 2008-07-18 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-07-09 | |
| dc.identifier.citation | [1] S. Chib and E. Greenberg. (1995) Understanding the Metropolis-Hasting Algorithm. The American Statistician, Vol. 49, No. 4 (November 1995), pp. 327–335.
[2] J. Munkres. (1957) Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, Vol. 5, No. 1 (March 1957), pp. 32–38. [3] Y. Nakamichi and T. Arita. (2001) Diversity Control in Ant Colony Optimization. Proceedings of the Inaugural Workshop on Artificial Life (AL’01), pp. 70–78, Adelaide, Australia, December 2001. [4] T. St¨utzle, M. Dorigo. (1999) ACO Algorithms for the Traveling Salesman Problem. In K. Miettinen, M. Makela, P. Neittaanmaki, and J. Periaux, editors, Evolutionary Algorithms in Engineering and Computer Science. Wiley, 1999. [5] I, Wegener. (2005) Simulated Annealing Beats Metropolis in Combinatorial Optimization. ICALP 2005. LNCS 3580, pp. 589–601. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37694 | - |
| dc.description.abstract | This thesis applies two algorithms to the maximum and minimum weighted bipartite matching problems. In such matching problems, the maximization and minimization problems are essentially same in that one can be transformed
into the other by replacing the weight on each edge with an inverse of the weight. Depending on the algorithms we used, we will choose the maximization or minimization problems for illustrations. We apply the ant colony optimization (ACO) algorithm on a minimum weighted bipartite matching problem by transforming the problem to a traveling salesman problem (TSP). It may seem that makes the problem more complicated, but in reality it does not. We call this algorithm “ant-matching,” which can solve any weighted bipartite matching problems with or without a perfect matching. Besides, we also apply the Metropolis algorithm to solve the maximum weighted bipartite matching problem. To analyze the performance on these two algorithms, we compare the algorithms with the exact Hungarian algorithm, a well-known combinatorial optimization method for solving the weighted bipartite matching problem. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T15:39:02Z (GMT). No. of bitstreams: 1 ntu-97-R95922165-1.pdf: 328569 bytes, checksum: 4152a985c5518d4cdc4afa4503e5d8ad (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | 1 Introduction 5
2 Preliminaries 6 2.1 Maximum/Minimum Weighted Bipartite Matching . . . . . 6 2.1.1 Weighted Bipartite Graph . . . . . . . . . . . . . 6 2.1.2 Maximum/Minimum Weighted Bipartite Matching . . . . 6 2.2 Ant Colony Optimization . . . . . . . . . . . . . . . 7 2.3 Metropolis Algorithm . . . . . . . . . . . . . . . . 8 3 Maximum/Minimum Weighted Bipartite Matching Problems 10 3.1 ACO Algorithm for Minimum-Weighted Bipartite Matching 10 3.1.1 Transforming Minimum-Weighted Bipartite Matching to Traveling Salesman Problem . . . . . . . . . . . . . . 11 3.1.2 Using ACO Algorithm to Solve Minimum-Weighted Bipartite Matching . . . . . . . . . . . . . . . . . . . 13 3.1.3 The Complexity of Ant-Matching Algorithm . . . . . 14 3.2 Metropolis Algorithm for Maximum-Weighted Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 The Complexity of Metropolis Algorithm . . . . . . 16 4 Experimental Results 17 4.1 Comparison of Complexity . . . . . . . . . . . . . . 17 4.2 Graph Sampling Algorithm . . . . . . . . . . . . . . 18 4.3 Results . . . . . . . . . . . . . . . . . . . . . . . 18 4.3.1 Results on Complete Bipartite Graphs . . . . . . . 19 4.3.2 Results on Sparse Bipartite Graphs . . . . . . . . 20 4.3.3 Results on Ant-Matching Algorithm . . . . . . . . . 23 4.3.4 Results on Metropolis Algorithm . . . . . . . . . . 25 5 Conclusions 35 Bibliography 36 | |
| dc.language.iso | en | |
| dc.subject | 螞蟻最佳化 | zh_TW |
| dc.subject | 權重 | zh_TW |
| dc.subject | 配對問題 | zh_TW |
| dc.subject | Metropolis algorithm | en |
| dc.subject | Minimum weighted bipartite matching | en |
| dc.subject | Maximum weighted bipartite matching | en |
| dc.subject | Ant colony optimization | en |
| dc.title | 兩個演算法解決最大及最小配對問題 | zh_TW |
| dc.title | Two Algorithms for Maximum and Minimum Weighted Bipartite Matching | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 金國興(Guo-Xing Jin),戴天時(Tian-Shyr Dai) | |
| dc.subject.keyword | 配對問題,螞蟻最佳化,權重, | zh_TW |
| dc.subject.keyword | Metropolis algorithm,Ant colony optimization,Maximum weighted bipartite matching,Minimum weighted bipartite matching, | en |
| dc.relation.page | 36 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-07-09 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf 未授權公開取用 | 320.87 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。