最佳约会策略

作者: , 共 1224 字
系列:生活中的数学

查看该系列所有文章

这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。


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

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

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

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

对给定的\(k\),我们可以计算选中最好的人的概率。假设最好的人出现在第\(i\)位(\(i>k\)),我们选中它的概率为\(\frac{k}{i-1}\)。这是因为这等价于前\(i-1\)个人的最高分出现在前\(k\)个人。

这样,选中最好的人的概率为:

$$ \begin{eqnarray} P &=& \sum_{i=k+1}^n \frac{1}{n} \frac{k}{i-1} \\ &=& \frac{k}{n}\sum_{i=k+1}^n \frac{1}{i-1} \\ &\approx & \frac{k}{n} \ln \frac{n}{k} \end{eqnarray} $$

接下来就是一个简单求\(\frac{\n x}{x}\)最大值的问题,其中\(x=\frac{n}{k}\)。对该表达式求导可知在\(x=e\),亦即\(k=\frac{n}{e} \approx 0.37n\)时取到最大值。对于\(n=20\),大约先过滤前\(0.37n\approx 7\)个人时,有最大 40%的概率选中最好的那个人,有接近 70%的概率选中最好或者此好的那个人。

我们还可以证明,在所有可能的策略之中,上面的策略都是最优的。(证明在此:37 rule is optimal)。

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

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

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

Q. E. D.

系列: 生活中的数学 »
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
后一篇:
注:来凑凑热闹,最先在槽边往事看到的,不过网上已经有相当多的讨论
类似文章:
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过\( \frac{u}{n}\sum_{i=u}^{n-1}\frac1i\) ,其中\( u\) 为满足\( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值。这个\( u\) 大约为 37%,最后成功的概率大约为 40%。
最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略
相似度: 0.075
最近看到一个有趣的问题:
相似度: 0.068
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
在 slashdot 上看到一篇科技新闻,两个数学家(其中一个来自于 MIT )和一个计算机学家,在 arXiv 上发表了一篇论文《HOW TO GAMBLE IF YOU』RE IN A HURRY》(PDF 版链接),是最近几天很热门的一条新闻。
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
注:这篇文章是应 You XU 邀请的 guest blog。
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
数学 » 搞笑, 数学之美
来自University of WarwickMike Paterson星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。