平面上的最小權完美匹配之啟發式演算法

Abstract

在本論文中,我們對於平面上的最小權完美匹配問題提出了幾個不同的啟發式演算法。基於座標平面上的三角不等式性質,提出一個先隨機一組完美匹配並優化它的 local search 演算法,接著在這個算法的基礎上做出許多的改進,最後得出數個還不錯的演算法,在實務上有的可以在和 Blossom 演算法相比下加速數十倍的情況下找出和最佳解誤差不到 2% 的解,或著是在加速數倍的情況下找出誤差 0.5% 左右的的解。

In this thesis, we provide some heuristic algorithms for minimum-weight perfect matching problem on a plane. First, we provide a local search algorithm based on triangle inequality. Then we try many methods to improve this algorithm. Finally we get some good algorithms. One can be 20-30 times faster than Blossom algorithm with 2% error and other one can be 3-4 times faster than Blossom algorithm with 0.5% error.