很有意思的一篇文章，权当消遣了，呵呵

来自：http://dahua.spaces.live.com

 

 

有些朋友似乎想看看这里的算法作业。恩，很多都是针对算法领域的一些专门问题，不太适合在这说。不过，正好上周的作业里面有一道题目很经典，呵呵。

题材嘛，就是关于约会和选择恋人的策略——其实大家发现搞算法的那帮人想问题和普通人还真不太一样——这里说的是经典算法，不是Learning算法。

下面是译成中文的原题：

考虑一个选择终身伴侣的问题。假设你要从k个候选人里面选择一个人作为你的终身伴侣（嗯，MIT的学生通常在这个方面比较势利）。你可以选择先和某个人约会一段时间，衡量一下你和这个人的适合程度，然后做出一个重要决定——你究竟要选择这个人永结同心，还是和他或者她彻底分手。作为一个负责人的人，你必须遵循这样的规则，在和一个人没有彻底分手之前，你不能选择约会其他人。如果你选择和一个人彻底分手，你将再也没有机会重新选择他或者她。而且，请你明白，在你约会一个人之前，你不可能了解关于他或者她的信息，或者对其做出判断。

你的目标是尽量选择最合适的人做伴侣。这里面的困境在于，如果你决定接纳当前这位作为终身伴侣，那么你将丧失选择更好的人选的机会；反之，如果你决定和他或者她分手，那么你将可能错失一个最好的人选。

在你做出最终决定之后，你会有机会见到全部的候选人，这样你就知道你选择的那个人究竟在这些人里面排名多少。如果你用了一个好的策略，你很可能最后会发现你的终身伴侣排名很靠前，如果你用了一个不好的策略，你有很大的机会发现其实你找了个排名很后的。

请完成如下问题

1. 请证明任何确定性的决策过程在最坏的情况下都是非常糟的。也就是说，无论候选人的人数是多少，无论你选择什么样的决策过程，都存在一种候选人序列，使得依据这种策略选择出来的人是里面最差的。
2. 请设计一种随机策略，使得无论有多少候选人，你都起码有25%的机会选到最好的那位作为终身伴侣。
3. 为了实现你对于伴侣的高期望，请设计一种随机策略使得你选择的候选人的实际排名尽可能靠前。这种策略至少应该保证，无论候选人的数量k有多大，你都可以以非常高的概率选到排在前 12 log(k) 名的人。（注：这道题其实问的东西要难一点，设计的要求更高，这里放宽了一点要求）
4. 请据此评论在MIT谈恋爱的后果。

解答写起来公式多一些，这里不多叙述了。这里简要分析一下而已。

1. 这种最差例子很容易找的。大概意思就是，无论你有什么样的策略和算法，我都可以找个人——这个家伙可能对你恨之入骨，呵呵。让他追踪你的决策过程，他模拟运行你的算法，如果你的算法第一个不接受，他第二个找一个差一点的，第二个还不接受，他就往序列里面排进更差的作为第三个，直到算法接受了某一个后，他往序列后面排进特别好的。然后你开始拿你的算法去这样构造出来的序列里面挑伴侣，保证挑到最差的。
2. 这个算法有点那个。你把你的候选人随机分成参考集和目标集，各占一半。你先把参考集的人逐个约会一遍，每约会一个分手一个——告诉对方他或者她是拿来训练你的model的——唉，不知道那个人会不会第二天拿把刀来砍你。然后你在目标集玩真的。一直约会下去，直到找到一个人比参考集的全部人都好的，就把这个人选为终身伴侣。如果，直到最后一个你还没碰上，你就选最后一个作为伴侣。因为你划分参考集和目标集是靠抛硬币划分的，那么你有四分之一的机会出现这样的情况：第一名的出现在目标中，第二名出现在参考集中，这样按照你的规则，在这种情况，必然会选择最好那个。所以你选择最好的机会是四分之一。
3. 这个题目有点复杂，不多说了。需要用Chernoff不等式。
4. 嘿嘿。。。。。。

整个问题最后的结论是——不要苦心孤诣的去选最好的伴侣了，抛硬币又省心效果又好，哈哈。