最佳约会策略

zhiqiang三月 10, 2007 自然科学

题外话：最近阅微堂发的都是网友转发的政治方面的文章，不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题，已经被研究了很多年，有许多不同形式的阐述方式和变种，应用范围也很广。下面应该是比较吸引人和简单的那种，来自姚期智教授的理论计算机（I）的授课内容——我是其助教之一。

现假设你在PIE上征友，或者以其它方式，选定了某些约会对象，比如n=20个。约会当然得一个一个来，那么假设

  1. 可以将所有已约会的对象按优劣排序，但无法得知他们在所有的人里面的排名。在约会过程中，你知道某人是你目前已见到的最好的，但当时还不能确定是不是所有人里面最好的。
  2. 如果你在约会当时决定放弃某人，后面再没有机会和此人和好——好马不吃回头草。
  3. 选定意中人后，约会结束——骑驴找马是不道德的。

OK，现在目标当然是找到你心目中最喜欢的人。关系定得太早，会因为第2条假设——精彩的还在后头，定得太晚，会因为第3条——而后悔莫及。所以，什么策略才能让你以最大概率找到你最满意的那个人呢？

一个简单而且自然的方法是，待定k，与前k个人约会，不做任何选择。继续约会直到遇到比这前k个人还好的那个人为止。

通过概率计算得出，这个方法比我们想象中要好得多。通过选取合适的k=n/e\sim 0.37n\sim 7，有接近40%的机会选中最好的那位，有几乎70%的机会选中最好或者次好的那位。

可以证明，上面的策略已经是最优的了。（证明在此：37 rule is optimal，英文）。

这个问题在日常生活中有更多应用。比如你打算在30岁前结婚，现在20岁。那么在24岁前先别确定目标，24岁以后遇到比之前都好的就可以定下来。这几乎就是你能达到最好的结果了——假设你的候选人在这十年是均匀或者随机出现的。

这种策略也许能说明为何初恋成功率低？

以上所用都是爱情和婚姻的简化模型，没有考虑爱情中的主观因素。所以，请只把它当作一个脑力游戏。

关于, , »
  • 37-rule-is-optimal Theorem: Any protocol of date problem has success probability less than \(\frac{u}{n}\sum\limits_{i=u}^{n-1}\frac1i\) which is about \(37\%\). Here \(u\) is the biggest number such that \(\sum_{i=u}^...
  • 摸箱子问题以及在Static data structure problems上的应用 以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆...
  • 征集3个人分蛋糕的方法 Yao在课程《理论计算机II》的第一节课上提到的一个问题： 三个人如何平分一块蛋糕？ 要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自...
  • TCS: 拜占庭将军问题 (The Byzantine Generals Problem) 这个问题在Yao的理论计算机课上整整讨论了2节课。它是一个算法设计问题，也极具趣味性。下面是它的一些介绍和解决方案([1])。 拜占庭帝国就是5...
  • 飞机加油问题 珍爱生命，远离政治。今天我们讨论一个数学问题。 这个问题的一个基本版本是说，有N架完全相同的飞机停留在一个机场，每一架最多装的油可以支...
  • "完美"的洗牌次数 - 7次 在大家玩牌的时候，每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌，但多少次洗牌才是正当的呢？就我多次打牌的观察，...
  • 硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
  • 帽子游戏一 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们...
  • 帽子游戏二 这个题目听说是MSRA的面试题。 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
  • 策略游戏：医生和病人（I） 我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想...
25条留言 -> 跳到留言表格
  • At 2007.03.10 21:48, Eric You XU said:

    Hoho, 一个online algorithm 的浪漫版本。

    [Reply]
    • At 2007.03.10 23:25, zhiqiang said:

      :) 对啊，这不就是一个online algorithm么，你知道这个1/e的low bound（如果是的话）被证明过么？

      [Reply]
      • At 2007.03.11 23:52, zhiqiang said:

        我自己给了个证明: 1/e已经是最好的了

        [Reply]
      • At 2007.03.12 01:29, dribblejj said:

        you are in UWashington.....hoho. I hope oneday I can be there and work with David Baker

        [Reply]
      • At 2007.03.10 23:04, sog said:

        我cao，

        这么喜欢把简单问题复杂化阿？

        [Reply]
        • At 2007.03.11 01:55, dribblejj said:

          我开始相信老板的那句话，其实数学是可以用来在mm面前炫的:DD
          我觉得所有的应用数学领域，model是最大的问题。还有你这个猪头，光说不练，怎么还没有看到你在pielove争友

          [Reply]
          • At 2007.03.11 21:41, Zig said:

            haha，诤友诤友

            [Reply]
            • At 2007.03.14 14:03, 匿名 said:

              哈哈，神也一起去诤友吧

              [Reply]
          • At 2007.03.11 21:36, Uvo said:

            哈哈，数学的妙用，不错。我觉得这是化繁为简。

            [Reply]
            • At 2007.03.12 05:59, inspire said:

              先对mm作用friend函数 然后再作用girl 函数
              得到g(f(x)) =gf(x)

              [Reply]
              • At 2007.03.13 12:14, Dai Qiang said:

                这个模型的前提是：衡量MM的好坏的index是序列值。如果MM的好坏是连续分数，比如只有3个MM的简单情况，双儿>教主夫人>太后，显然其中的差距是不等的，MM多了后就存在魅力index分布型的问题。 问题是不是要复杂些呢？

                [Reply]
                • At 2007.03.13 15:06, Dai Qiang said:

                  “继续约会直到遇到比这前k个人还好的那个人为止。”
                  仔细想了下，发现这个策略有个大问题。
                  如果最好的已经在前k个人中出现过了，而可怜的兄弟还在k后面的人中找更好的人。结果一无所获，白了少年头。
                  这个概率应该是k/n。也就是说40%

                  [Reply]
                  • At 2007.03.13 19:19, zhiqiang said:

                    你说的没错，会有60％＋的概率找不到最好的那个人—— 只有40％的概率能找到The Right，这个文章里面说的很清楚。

                    而且文章中的方法也已经是最好的了。

                    你上面说的考虑魅力分布问题，这个就是另外一个问题了，你也可以想一下啊。

                    [Reply]
                  • At 2007.03.14 10:20, Dai Qiang said:

                    呵呵，正在想，难啊！

                    [Reply]
                    • At 2007.03.16 10:46, 前博客 said:

                      好强好强 还是随缘吧 哈哈

                      [Reply]
                      • At 2007.03.18 16:42, rex said:

                        纳什用泡妞理论研究出了,得了诺贝尔奖,看来楼主也快了.
                        不信就看

                        [Reply]
                        • At 2007.05.01 05:53, You XU said:

                          换Blog地址了, 偶不在UWashington, 我在Washington University, 两所学校超级难区别, 而且排名也差不多, 常混淆人.
                          两种不同的策略, 我想想哪个好 :)

                          [Reply]
                          • At 2007.07.01 01:42, YOYO said:

                            泡个妞那么复杂啊...

                            [Reply]
                            • At 2007.11.11 06:19, maninblack said:

                              Washington U的本科排名比UWashington强不少，UWashington的cs比Washington U强的多

                              [Reply]
                              • At 2007.11.11 06:23, maninblack said:

                                其实这个candidate是均匀分布的假定下，这个策略可以稍微修改一下：
                                考察前ｋ个candidate保留其中最好的m个

                                [Reply]
                                • At 2008.04.13 16:24, andy said:

                                  关系定得太早，会因为第2条假设——精彩的还在后头，定得太晚，会因为第3条——而后悔莫及

                                  两个反了吧 ，应该是
                                  关系定得太早，会因为第3条假设——精彩的还在后头，定得太晚，会因为第2条——而后悔莫及

                                  [Reply]
                                  • At 2008.06.24 16:24, Yuanyuan said:

                                    这是个问题····

                                    [Reply]
                                    • At 2008.08.19 16:59, 严酷的魔王 said:

                                      关于这个问题还有一篇比较好的文章，台大的：http://episte.math.ntu.edu.tw/articles/sm/sm_03_05_1/index.html

                                      [Reply]
                                      • At 2009.01.06 18:52, lxrm said:

                                        　┆　┆Ｄ┆来┆都┆　┆
                                        　┆　┆　┆所┆可┆呵┆
                                        　┆　┆　┆　┆以┆呵┆
                                        　┆　┆　┆：┆算┆，┆
                                        　┆　┆　┆－┆出┆这┆

                                        [Reply]
                                        • At 2010.05.14 14:50, wuzhengkai said:

                                          考虑取第lnN个比前面的人都大的？

                                          [Reply]
                                          (Required)
                                          (Required, not published)

                                            B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
                                          «
                                          »
                                          guest | 注册 | 管理 | English | 繁體 | https

                                          阅微堂

                                          zhiqiang's personal blog
                                          Loading...
                                          Loading...
                                          Loading...