数学研发论坛

 找回密码
 欢迎注册
查看: 327|回复: 3

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

[复制链接]
发表于 2020-1-30 21:09:07 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

求2n个点的最小权值匹配。(即两点组成一条线段,使得n条线段的总长最小)。网上都介绍的是DP算法,效率很低且只对小规模数据适用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-30 22:09:56 | 显示全部楼层
猜想:1、若2n个点的tsp问题的结果点集序号为1,2,3……2n,按序号奇偶就分成两组,两组间的最大权值匹配(蓝色连线)取反(黄色连线)即是两组间最小权值匹配。
          2、上述两组间的最大权值匹配连线不会与TSP连线形成局部回路,如图124中1、2、4、5四点即存在局部回路。

123.png
124.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-30 23:52:06 | 显示全部楼层
就算最大权值匹配算出,取反可能有多种情况满足,如图,最优配对为2—3、4—5、1—6。
aa.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-31 00:22:36 | 显示全部楼层
猜想:2n个点的最小权值匹配即是2n个点的tsp结果中奇偶边或偶奇边总和较小的一组。
222.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-4-8 09:32 , Processed in 0.054415 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表