呂育道Lyuu, Yuh-Dauh臺灣大學:資訊工程學研究所石鴻賓Shih, Hung-PinHung-PinShih2010-05-182018-07-052010-05-182018-07-052008U0001-0707200811280500http://ntur.lib.ntu.edu.tw//handle/246246/183683This 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 transformednto 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 matchingroblem 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 weightedipartite 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, weompare the algorithms with the exact Hungarian algorithm, a well-known combinatorial optimization method for solving the weighted bipartite matching problem.1 Introduction 5 Preliminaries 6.1 Maximum/Minimum Weighted Bipartite Matching . . . . . 6.1.1 Weighted Bipartite Graph . . . . . . . . . . . . . 6.1.2 Maximum/Minimum Weighted Bipartite Matching . . . . 6.2 Ant Colony Optimization . . . . . . . . . . . . . . . 7.3 Metropolis Algorithm . . . . . . . . . . . . . . . . 8 Maximum/Minimum Weighted Bipartite Matching Problems 10.1 ACO Algorithm for Minimum-Weighted Bipartite Matching 10.1.1 Transforming Minimum-Weighted Bipartite Matchingo Traveling Salesman Problem . . . . . . . . . . . . . . 11.1.2 Using ACO Algorithm to Solve Minimum-Weighted Bipartite Matching . . . . . . . . . . . . . . . . . . . 13.1.3 The Complexity of Ant-Matching Algorithm . . . . . 14.2 Metropolis Algorithm for Maximum-Weighted Bipartiteatching . . . . . . . . . . . . . . . . . . . . . . . . 14.2.1 The Complexity of Metropolis Algorithm . . . . . . 16 Experimental Results 17.1 Comparison of Complexity . . . . . . . . . . . . . . 17.2 Graph Sampling Algorithm . . . . . . . . . . . . . . 18.3 Results . . . . . . . . . . . . . . . . . . . . . . . 18.3.1 Results on Complete Bipartite Graphs . . . . . . . 19.3.2 Results on Sparse Bipartite Graphs . . . . . . . . 20.3.3 Results on Ant-Matching Algorithm . . . . . . . . . 23.3.4 Results on Metropolis Algorithm . . . . . . . . . . 25 Conclusions 35ibliography 36application/pdf328569 bytesapplication/pdfen-US配對問題螞蟻最佳化權重Metropolis algorithmAnt colony optimizationMaximum weighted bipartite matchingMinimum weighted bipartite matchingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183683/1/ntu-97-R95922165-1.pdf