請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37694
標題: | 兩個演算法解決最大及最小配對問題 Two Algorithms for Maximum and Minimum Weighted Bipartite Matching |
作者: | Hung-Pin Shih 石鴻賓 |
指導教授: | 呂育道(Yuh-Dauh Lyuu) |
關鍵字: | 配對問題,螞蟻最佳化,權重, Metropolis algorithm,Ant colony optimization,Maximum weighted bipartite matching,Minimum weighted bipartite matching, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37694 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 320.87 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。