Windows LiveWindows Live™
 
 
Dahua's profile笑对人生，傲立寰宇PhotosBlogLists Tools Help

Blog
    November 08

    约会的规则：确定？随机？

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

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

    下面是译成中文的原题：

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

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

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

    请完成如下问题

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

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

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

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

    10:41 AM | View trackbacks (1) | Blog it

    Comments (18)

    Please wait...
    Sorry, the comment you entered is too long. Please shorten it.
    You didn't enter anything. Please try again.
    Sorry, we can't add your comment right now. Please try again later.
    To add a comment, you need permission from your parent. Ask for permission
    Your parent has turned off comments.
    Sorry, we can't delete your comment right now. Please try again later.
    You've exceeded the maximum number of comments that can be left in one day. Please try again in 24 hours.
    Your account has had the ability to leave comments disabled because our systems indicate that you may be spamming other users. If you believe that your account has been disabled in error please contact Windows Live support.
    Complete the security check below to finish leaving your comment.
    The characters you type in the security check must match the characters in the picture or audio.

    To add a comment, sign in with your Windows Live ID (if you use Hotmail, Messenger, or Xbox LIVE, you have a Windows Live ID). Sign in


    Don't have a Windows Live ID? Sign up
    No namewrote:
    Oct. 23
    Picture of Anonymous
    JWW wrote:
    This day was also considered as a harvest festival since wow goldfruits, vegetables and grain had aoc goldbeen harvested by this time and food was abundant. Food offerings were placed on an altar set up in the courtyard. Apples, pears, peaches, grapes,maple story mesos pomegranates, melons, oranges maplestory mesosand pomelos might be seen. Special foods for the festival included moon cakes, cooked taro and water caltrope, a type of water maple story mesochestnut resembling black buffalo horns. Some people insisted that cooked taro be included because at the time of creation, aoc goldtaro was the first food discovered at night in the moonlight. Of allthese foods, it wow goldcould not be omitted from the Mid-Autumn wow goldFestival.The round moon cakes, measuring about three inches in diameter and one and a half inches in thickness, resembled Western fruitcakes in taste and consistency. These wow goldcakes were made with melon seeds, lotus seeds, almonds, minced meats, bean paste, orange peels and lard. A golden yolk from a salted duck egg was placed at the wow goldcenter of each cake, and the golden brown crust was decorated with symbols of the festival. Traditionally, thirteen moon cakes were piled in a pyramid to symbolize the thirteen moons of a "complete year," that is, twelve wow goldmoons plus one intercalary moon. The Mid-Autumn wow goldFestival is a traditional festivity for both the Han and minority nationalities. The custom of worshipping the moon can be traced back as far as the wow goldancient Xia and Shang Dynasties (2000 B.C.-1066 B.C.). In the Zhou Dynasty(1066 B.C.-221 B.C.), people hold wow goldceremonies to greet winter and worship the moon whenever the Mid-Autumn Festival sets in. It becomes very wow goldprevalent in the Tang Dynasty(618-907 A.D.) that people enjoy and worship the full moon. In the Southern Song Dynasty (1127-1279 A.D.), however, people send round moon cakes to their relatives as gifts in expression wow goldof their best wishes of family reunion. When it becomes dark, they look up at the full silver moon or go sightseeing on lakes to celebrate the festival. Since the Ming (1368-1644 A.D. ) and Qing Dynasties (1644-1911A.D.), the custom of Mid-Autumn Festival celebration becomes unprecedented popular. Together with the celebration there appearwow gold some special customs in different parts of the country, such as burning incense, planting Mid-Autumn trees, lighting lanterns on towers and fire dragon dances. However, the custom of playing under the moon is not so popular as it used to be nowadays, but it is not less popular to enjoy the brightwow gold silver moon. Whenever the festival sets in, people will look up at the full silver moon, drinking wine to celebrate their happy life or thinking of their relatives and friends far from home, and extending all of their best wishes to them.
    Sept. 5
    Picture of Anonymous
    JWW wrote:
    Sept. 5
    gigi wenwrote:
    哇，约会可以不用感性思维的。。。。
    Nov. 23
    Qiao Yuwrote:
    关键是要有一个大的训练集啊
    Nov. 15
    Lynn Daiwrote:
    haha,达哥已经在做这方面的研究了：）加油哦
    Nov. 14
    Xianchao Xianchaowrote:
    居然看到偶们系Herman Chernoff的名字 。。。。。。
    Btw, 似乎选1/e的人出来找一个record person的方法会好些吧。
    Nov. 12
    Cixunwrote:
    对Parents Supervised Couple Matching这篇大作的实验结果很感兴趣
    Nov. 11
    Huan Wangwrote:
    嗯哪，Parents Supervised Couple Matching
    Nov. 10
    Hongwei Harveywrote:
    哈哈,欢子的说法就是纯top-down了,而且加入了interactive method.
     
    Nov. 9
    Hongwei Harveywrote:
    达哥对于数学的理解方式确实特别,呵呵
     
    Nov. 9
    Cixunwrote:
    其实是前生就注定了的。。
    Nov. 9
    Huan Wangwrote:
    恩，找MM忒费事了，相亲才是王道:D
    Nov. 9
    nan yiwrote:
    有点博弈论的感觉
    Nov. 8
    Picture of Anonymous
    Laurel wrote:
    不要苦心孤诣的去选最好的伴侣了，抛硬币又省心效果又好~
    :)
    Nov. 8
    Ming Yangwrote:
    绝对顶随机！
    Nov. 8
    Chris Liangwrote:
    感觉跟穿过麦田选一根最大的麦子的问题一样啊
    Nov. 8
    Yao Xiewrote:
    晕倒...如果dating可以这么来的话就好了....
    Nov. 8

    Trackbacks (1)

    The trackback URL for this entry is:
    http://dahua.spaces.live.com/blog/cns!28AF4251DF30CA42!1817.trak
    Weblogs that reference this entry