上海信息港
育儿
当前位置:首页 > 育儿

最好约会策略及其证明出世

发布时间:2020-09-25 07:34:05 编辑:笔名
最好约会策略及其证明

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

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

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

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

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

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

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

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

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

<小叮当001 1327p>这类策略也许能说明为什么初恋成功率低?

<预计明年下半年形势会逐渐好转。p>以上所用都是爱情和婚姻的简化模型,没有推敲爱情中的主观因素。所以,请只把它当作一个脑力游戏。

下面将证明:最好约会策略里提到策略,忽视前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}的最后1名为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),是预约会面的一种,原指预先约定时间地点会面的活动。本来约会是指一般人士的预约会面,现在通常指两人谈恋爱。恋爱的约会,香港人称作拍拖,也可称为去街、行街(在粤语中,这些词都有男女约会的意思)。约会是人类求偶活动其中一环,借相处交谈而了解对方。找出配合度,用作考验及选择出一名作为配偶,进程中亦同时培养并巩固爱情。

一个疗程的复方鳖甲软肝片多少钱
复方鳖甲软肝片疗效怎么样
软肝片全疗程用药的注意事项
复方鳖甲软肝片在天津能买到吗
友情链接