TCS课堂笔记：最佳约会策略

zhiqiangMarch 10, 2007 科学精华区

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

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

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

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

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

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

可以证明，上面的策略已经是最优的了。

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

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

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

婚姻模型 理论计算机笔记 策略 约会

你可能感兴趣的

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, Anonymous 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]