算法浅谈——我要怎么才能选到真命天子呢？

点击上方蓝字，和我一起学技术。

在很久很久以前，有一个万人迷。

她从18岁开始就有数不完的追求者，追她的男生一个个在她的窗前排起了长队。但是她挑来挑去，终究不觉得满意。终于，这个万人迷一天天长大，年老色衰，在她门口排队的男生也越来越少。

她开始后悔拒绝男生时的轻率，怀念起了从前的荣光。她也不知道，最后她是会向现实妥协，选择一个看起来远不是那么好的男生共度一生，还是会就这么一直等下去。

这样的故事其实并不罕见，知乎里关于剩男剩女以及婚嫁的问题屡见不鲜。选择配偶也是我们人生当中的必经之路，苏格拉底说过，人生就是一次无法重复的选择，在婚姻这个问题上尤为明显。

那么问题来了，如果我们是故事中的万人迷，我们应该如何选择配偶呢？

即使是真的万人迷，她可以选择的配偶也一定是有限的。我们可以做一个简单的量化，假设她一年平均有30个追求者，她打算28岁结婚。那么从她18岁开始算起，假设她的魅力保持不变，她一共可以遇到300个潜在的配偶。

这个数字对于每个女生而言各有不同，但是它其实并不重要，并不会影响我们的计算过程。为了简化计算，我们就假设它为n。接着，我们再进一步简化模型，假设这n个男生排成一队，一个一个地来发起追求。我们假设女生面临每个追求者的时候只会有两个选择，一是直接拒绝，二是答应追求，从此牵手共度一生。

那么，我们如何来做一个好的决策呢？

和现实中一样，一种比较聪明的做法是，先和前面的一些男生每个人都相处一段时间，做一个了解，摸清这些男生大概的水平底细之后再认真考虑。抽象成数学模型来，就是女生会直接拒绝掉前面k个男生，从第k+1个男生开始一一和前面k个男生比对。当一个比前面k个男生都要好的男生出现的时候，她果断选择接受，从此和他共度一生。

如此一来，这就成了一个数学问题，究竟这个k应该等于多少，才可以使得女生选中所有男生当中最好的那个的概率最大呢？

所以，我们应该怎么求出这个K呢？

对于某个固定的K，我们假设最佳配偶出现在了第i的位置。想让他能被挑选中，必须要保证前面i-1个人中的最好的配偶出现在前K个人当中。这个概率不难计算，是：

。那么，我们对所有的i进行加权求和即可：

我们假设n是一个很大的值，我们可以先算后面的部分。如果n足够大，可以认为

我们令

，

我们对P(K)的求导，令它等于0，可以求出P(K)最大时

。这里的e就是数学当中经常出现的欧拉常数，也叫自然底数，

约等于37%。那么，算到了这个结果，这个问题也就有了答案。

如果你是一个万人迷，那么你应该拒绝掉前面37%的追求者，然后在剩下的63%的男士当中挑选一个比前面都强的作为配偶。那么你选到最佳配偶的概率达到最大值，它的概率为37%。

虽然有了答案，但是我们并不知道这个答案对不对，但是没关系，我们是程序员，可以用代码来模拟。

我们就按照万人迷的配置来设定好了，假设她一生当中会面临300个追求者。我们假设这三百个追求者的好坏层次不齐，按照分数排序，可以得到一个0到299的序号。排名越靠后，说明分数越大，男生越优质，然后我们再对这些男生进行乱序。

import random

def generateBoys():
    boys = [i for i in range(300)]
    random.shuffle(boys)
    return boys

接着我们来编写程序的主体，其实也很简单，我们模拟进行许多次同样的配偶选择，模拟出我们通过这种策略能够选中最佳配偶的概率，代码并不难写：

# iterations 是模拟择偶的次数
def simulation(iterations=10000):
    matched = 0
    for i in range(iterations):
        # 每次都创建新的追求者集合
        boys = generateBoys()
        # 最佳配偶的序号
        best = max(boys)
        maxi = 0
        partner = 0
        # 计算K， K=0.37 * 追求者总数
        pickedNum = int(0.37 * len(boys))
        for j in range(pickedNum):
            maxi = max(maxi, boys[j])
        # 一旦找到比前K个最好的都要好的，就结束
        for j in range(pickedNum, len(boys)):
            if boys[j] > maxi:
                partner = boys[j]
                break
        # 判断是否找到了最佳配偶
        if partner == best:
            matched += 1
    return matched / float(iterations)

最后，我们运行代码，得出的答案是0.3629。当然这也不是一个精确值，也是一个会波动的估算结果。迭代的次数越多，这个得到的结果越逼近真实值。用大量的实验去测算某个事件发生的概率，这个也是统计学上常用的方法。

通过建模，我们把一个抽象的，无从下手的问题，简化成了一个明确的数学问题。通过建立函数求最值的方法，求出了最优解。从结果上来看，如果真有一个姑娘能有这么多追求者，通过一种方法可以拥有37%的概率挑中她的真命天子，也算是非常棒了。

但是数学模型的是理想的，现实和理想总是有些差别。现实中，我们的时间精力是有限的，我们不一定有时间来一一衡量前面追求者的优劣。而且追求者的分布也不一定是随机的，很有可能随着我们自身的变化而变化。比如我们通过自己的努力，去往了更好的学校、公司，那么我们接触到的异性也会更好。

不过尽管如此，这道算法问题对我们还是很有借鉴意义，希望能够给大家带来启发。

今天的文章就到这里，希望大家有所收获。如果喜欢本文，请顺手点个在看或者转发吧。