N girls need to be matched with N boys

markfang2050

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。

KeyTo9_Fans

这里有个专门解决最小费用完美匹配问题的工具：

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$是相当地接近。

#####

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

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

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

KeyTo9_Fans

那第二个问题，关于火柴棍的长度分布，有些什么美妙的结论吗？

markfang2050

N = 1000
cost = np.random.rand(N,N)
row, col = linear_sum_assignment(cost)
total_cost = cost[row, col].sum()

markfang2050

另这一类问题早就有很多人研究了，最为人熟知的“秘书”问题。