点集最小权值匹配

aimisiyou · 发表于 2020-1-30 21:09:07

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 aimisiyou 于 2020-1-30 21:17 编辑

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

aimisiyou · 发表于 2020-1-30 22:09:56

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

aimisiyou · 发表于 2020-1-30 23:52:06

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

aimisiyou · 发表于 2020-1-31 00:22:36

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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 点集最小权值匹配