男人焦点网
首页 >> 养生 >> 正文

最佳约会策略及其证明

日期:2019-07-21 12:21:45 来源:互联网 编辑:小狐 阅读人数:15

最佳约会策略及其证明(图1)

下面的问题来自姚期智教授的理论计算机的授课内容—我是其助教之一:

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

可以将所有已约会的对象按优劣排序,但无法得知他们在所有的人里面的排名。在约会过程中,你知道某人是你目前已见到的最好的,但当时还不能确定是不是所有人里面最好的。

如果你在约会当时决定放弃某人,后面再没有机会和此人和好—好马不吃回头草。

选定意中人后,约会结束—骑驴找马是不道德的。

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

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

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

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

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

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

下面将证明:最佳约会策略里提到策略,忽略前37%的对象,在剩下的对象里挑第一个比前37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过un∑n−1i=u1i,其中u为满足∑n−1i=u1i≥1的最大值。这个u大约为37%,最后成功的概率大约为40%。

首先定义一些符号,∏n表示{1,2,⋯,n}的排列的集合。

我们可以定义排列之间的半有序关系。对于任何两个排列α∈∏a和β∈∏b,如果a≤b并且α的前a项的大小顺序和β一样即对任意1≤i,j≤a都有αi

对任意α∈∏n,令

Fk(α)=β∈∏ks. t.β≤α

下面开始证明。

随机策略是确定性策略的随机组合,所以任何一个随机策略的胜率都不会超过其中最好的确定性策略的胜率。所以我们只需要对确定性策略证明上述胜率上届。

而首先,我们需要对一个约会策略建模。任何一个策略面对一个约会对象的序列,这个序列可视作一个排列组合。策略一项一项检验这个排列组合,并且决定在什么时候停止。假设这个策略在检查α时停止在第k项,那么该策略只知道α的前k项的相对顺序,也就是Fk(α)便决定停止。令Sk∈∏k为所有这样的Fk(α)并令sk=Sk。我们也称S=S1∪S2∪⋯∪Sn为策略的停止集。

显然,对于任意α∈Sk, 都有n!k!个排列比它大。这其中,有(n−1)(k−1)个排列被策略成功找出最大值(即第k项为n)所以策略在第k项停止并成功的概率为:

P=1n!∑k(n−1)(k−1)⋅sk

从上面概率等式看,一个策略的停止集越大越好。现在我们需要指明,这是证明我们结论的关键。一个策略的停止集S并不能无限制的大,它必须满足其中的任意一个排列都不能是另外一个排列的字串,即对任意i如果同为停止集元素的排列α是另一个停止集元素β的子排列,那么当策略在遇到β时,策略将直接停止在第i个元素,不会等到第j个元素才停止,从而β不可能也是停止集合的成员。

从上面的事实,我们计算{1,2,⋯,i}的最后一位为i的排列个数。任何一个属于Sj的排列都可以扩充为(i−1)j!个这样的排列,并且所有这些这样扩充后的排列都互不相同。因此:

∑j=1j−1sj(i−1)j!+si≤(i−1)

令ti=si/i!上式为对任意i

令u为满足∑n−1i=u1i≥1的最大值,以下有:

P==≤=1n∑k=1nktk1n∑i=1n∑j=1i−1tj+iti1−∑j=in−11j1n∑i=u+1n1−∑j=in−11jun∑i=un−11i

等号成立时必须有∀i≤u都有ti=0,亦即策略需忽略前u项,并且∀i>u有∑i−1j=1tj+iti=1,递推可知最佳约会策略是唯一的最优的策略。

∑Gemini

本文相关词条概念解析:

策略

策略(cèlüè),汉语词语,意思是计策、谋略。该词语一般是指可以实现目标的方案集合以及根据形势发展而制定的行动方针和斗争方法,也用来表示有斗争艺术,能注意方式方法。

约会

约会(Dating),是预约会面的一种,原指预先约定时间地点会面的活动。本来约会是指一般人士的预约会面,现在通常指两人谈恋爱。恋爱的约会,香港人称作拍拖,也可称为去街、行街(在粤语中,这些词都有男女约会的意思)。约会是人类求偶活动其中一环,借相处交谈而了解对方。找出配合度,用作考验及选择出一位作为配偶,过程中亦同时培养并巩固爱情。

网友评论
  • 可以叫我帅
    然而医生的修为有高低,中西医对病理理解不同,再加上难以避免的职业病,造成误疹、误判、事故良多
    2019-12-05 07:34 242
  • 天太黑我听
    约会的最佳场所有哪些?
    2019-12-08 16:36 125
  • 我的@乐章4
    不进医院的最佳养生策略是什么?
    2019-12-05 16:17 279
  • 菜菜0613
    世人谈癌色变,动辄放化疗,花光了钱丢了命,因愚昧而丧生,数不胜数
    2019-12-05 12:19 208
  • 倩贻baby
    在顺昌之战、川陕之战、郾城大捷中,都不乏步兵胜骑兵的例子
    2019-12-04 09:44 636
  • yukai12388
    很有情侣特色的网红店可以让女孩子在视觉欣赏方面得到满足,有了好的聊天环境过后两个人才能更浪漫的说话
    2019-12-01 23:44 624
  • 熊熊aaa
    钢铁把心理素质的步兵方阵配以重弩辅助,或者就是用更为强大的骑兵对抗
    2019-12-07 14:31 24