N girls need to be matched with N boys
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, 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。 这里有个专门解决最小费用完美匹配问题的工具：
https://www.mathworks.com/matlabcentral/fileexchange/27181-minimum-perfect-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$是相当地接近。
#####
因此楼主的第一个命题通过了实验的验证。
请问楼主这题目是哪来的？
我需要找到原始文献，这样我才能知道，这个命题是否已经有人证出来了。 那第二个问题，关于火柴棍的长度分布，有些什么美妙的结论吗？ N = 1000
cost = np.random.rand(N,N)
row, col = linear_sum_assignment(cost)
total_cost = cost.sum() 另这一类问题早就有很多人研究了，最为人熟知的“秘书”问题。
页:
[1]