RoBa注:我在出这道题(TOJ 2941 Girl Friend) 的时候,并没有看过这篇文章……我那道题是作了太多简化的,很多地方都理想化了,最后可以得到一个简单的线性dp算法。当然,明显是很不实用的,就算真能准确计算出fitness和成功的概率,最致命的一点是在实际情况下不可能预知那个约会序列。相比之下这篇文章的讨论就更genernal和practical,虽然 还是作了一定简化的。最后结论就是,这个事情最好还是不要用数学来计算了……另外要说的是,MIT果然是MIT,YY的比我深刻多了……

============================低调的分隔线============================


原文地址 http://dahua.spaces.live.com/Blog/cns!28AF4251DF30CA42!1817.entry

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

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

下面是译成中文的原题:

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

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

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

请完成如下问题

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

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

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