兩個演算法解決最大及最小配對問題

Two Algorithms for Maximum and Minimum Weighted Bipartite Matching

石鴻賓(Hung-Pin Shih)

指導教授 ： 呂育道

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00324

摘要

無資料

關鍵字

配對問題 ； 螞蟻最佳化 ； 權重

並列摘要

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.

並列關鍵字

Metropolis algorithm ； Ant colony optimization ； Maximum weighted bipartite matching ； Minimum weighted bipartite matching

參考文獻

[1] S. Chib and E. Greenberg. (1995) Understanding the Metropolis-Hasting Algorithm. The American Statistician, Vol. 49, No. 4 (November 1995), pp. 327–335.

[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.

[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.