最佳约会策略
source link: https://zhiqiang.org/math/best-dating-strategy.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
最佳约会策略
系列：生活中的数学
这个问题有许多不同形式的阐述方式和变种，应用范围也很广。下面应该是比较吸引人和简单的那种，来自姚期智教授的理论计算机（ I ）的授课内容——我是其助教之一。
现假设你在 PIE 上征友，或者以其它方式，选定了某些约会对象，比如n=20n=20 个。约会当然得一个一个来，那么假设
- 可以将所有已约会的对象按优劣排序，但无法得知他们在所有的人里面的排名。在约会过程中，你知道某人是你目前已见到的最好的，但当时还不能确定是不是所有人里面最好的。
- 如果你在约会当时决定放弃某人，后面再没有机会和此人和好——好马不吃回头草。
- 选定意中人后，约会结束——骑驴找马是不道德的。
OK ，现在目标当然是找到你心目中最喜欢的人。关系定得太早，会因为第 2 条假设——精彩的还在后头，定得太晚，会因为第 3 条——而后悔莫及。所以，什么策略才能让你以最大概率找到你最满意的那个人呢？
一个简单而且自然的方法是，待定kk ，与前 kk 个人约会，不做任何选择。继续约会直到遇到比这前kk个人还好的那个人为止。
对给定的kk，我们可以计算选中最好的人的概率。假设最好的人出现在第ii位（i>ki>k），我们选中它的概率为ki−1ki−1。这是因为这等价于前i−1i−1个人的最高分出现在前kk个人。
这样，选中最好的人的概率为：
接下来就是一个简单求\nxx\nxx最大值的问题，其中x=nkx=nk。对该表达式求导可知在x=ex=e，亦即k=ne≈0.37nk=ne≈0.37n时取到最大值。对于n=20n=20，大约先过滤前0.37n≈70.37n≈7个人时，有最大 40%的概率选中最好的那个人，有接近 70%的概率选中最好或者此好的那个人。
我们还可以证明，在所有可能的策略之中，上面的策略都是最优的。（证明在此：37 rule is optimal）。
这个问题在日常生活中有更多应用。比如你打算在 30 岁前结婚，现在 20 岁。那么在 24 岁前先别确定目标， 24 岁以后遇到比之前都好的就可以定下来。这几乎就是你能达到最好的结果了——假设你的候选人在这十年是均匀或者随机出现的。
这种策略也许能说明为何初恋成功率低？
以上所用都是爱情和婚姻的简化模型，没有考虑爱情中的主观因素。所以，请只把它当作一个脑力游戏。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK