数学研发论坛

 找回密码
 欢迎注册
查看: 131|回复: 9

[讨论] N girls need to be matched with N boys

[复制链接]
发表于 2021-10-7 18:49:48 | 显示全部楼层 |阅读模式

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

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

x
N girls need to be matched with N boys.
When girl "i" is matched with boy "j", this leads to a conflict score of C(i,j). When the C(i,j) are independent and Unif[0,1], the matching that minimises the total conflict score converge to pi^2/6。

Sequentially add a bunch of Red/Green points inside the unit square and compute the optimal matching... Since segments cannot cross (otherwise this could not be an optimal matching), interesting structures emerge。
QQ图片20211007182103.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-8 15:32:46 | 显示全部楼层
这里有个专门解决最小费用完美匹配问题的工具:

https://www.mathworks.com/matlab ... rfect-matching-tool

我不知道好不好使,你可以试一下。

#####

我试了一下,规模为$N=100$的最小费用完美匹配需要跑2分钟。

我用了5个多小时才跑了151遍,结果为$1.61\pm0.02$,与楼主声称的$\pi^2/6\approx 1.64$还是很接近的。

#####

改用C++实现最小费用完美匹配,规模为$N=1000$只需跑1秒钟。

我用了40多分钟就跑了2640遍,结果为$1.641\pm0.002$,与楼主声称的$\pi^2/6\approx 1.645$是相当地接近。

#####

因此楼主的第一个命题通过了实验的验证。

请问楼主这题目是哪来的?

我需要找到原始文献,这样我才能知道,这个命题是否已经有人证出来了。

点评

审稿的一篇国外论文。  发表于 2021-10-13 22:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-14 00:00:36 | 显示全部楼层
那第二个问题,关于火柴棍的长度分布,有些什么美妙的结论吗?

点评

M. Mezard and G. Parisi. On the solution of the random link matching problem. https://bit.ly/3Dk6fG8 D.Aldous. The ζ(2) Limit in the Random Assignment Problem. 给你2个文献,评议论文暂时不能泄密   发表于 2021-10-14 00:44
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-14 00:46:29 | 显示全部楼层
N = 1000
cost = np.random.rand(N,N)
row, col = linear_sum_assignment(cost)
total_cost = cost[row, col].sum()
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-14 00:47:33 | 显示全部楼层
另这一类问题早就有很多人研究了,最为人熟知的“秘书”问题。

点评

Secretary problem  发表于 2021-10-15 18:26
https://en.m.wikipedia.org/wiki/Secretary_problem  发表于 2021-10-15 18:26
秘书问题是不是说,n个人依次面试1个秘书职位,那么最佳候选人会被替换1+1/2+1/3+...+1/n次?  发表于 2021-10-14 10:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-10-24 20:54 , Processed in 0.074711 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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