点集最小权值匹配

SAY

求2n个点的最小权值匹配。（即两点组成一条线段，使得n条线段的总长最小）。网上都介绍的是DP算法，效率很低且只对小规模数据适用。

ebirugerxos

猜想：1、若2n个点的tsp问题的结果点集序号为1,2,3……2n,按序号奇偶就分成两组，两组间的最大权值匹配（蓝色连线）取反（黄色连线）即是两组间最小权值匹配。
          2、上述两组间的最大权值匹配连线不会与TSP连线形成局部回路，如图124中1、2、4、5四点即存在局部回路。

agihaku

就算最大权值匹配算出，取反可能有多种情况满足，如图，最优配对为2—3、4—5、1—6。

euogifubize

猜想：2n个点的最小权值匹配即是2n个点的tsp结果中奇偶边或偶奇边总和较小的一组。