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

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.