秘书问题与计算机模拟.ppt
秘书问题与计算机模拟,南京邮电大学理学院杨振华,问题,设想一个经理要从若干个应聘者中雇用一名秘书.按照某种标准,可用1,2,N分别表示这些应聘者的优劣的绝对名次.1表示最优者,N表示最劣者.假设这些应聘者是逐个到来接受经理面试的，并且应聘者到来的优劣次序是随机的.经理每次会见一名应聘者，面试后决定录用与否.如果录用到当时面试的应聘者，则停止下面的会见，否则面试下一位.,问题,我们还假定,每个当时不被录用的应聘者是不能事后再招回录用的,在经理每一次面试后,他只知道当时的应聘者与先前已面试者比较的相对名次,而不知道当时应聘者的绝对名次.现在要问经理要怎样决定他的录用策略,或者说经理在何时停止他的会见(录用当时的应聘者)是最优的.当然这里最优要有一个标准,通常采用下面两种标准:第一标准:使录用到最优应聘者的概率最大;第二标准:使录用的应聘者的绝对名次尽量的小.,录用策略,所谓录用策略,就是何时录用当时的应聘者.在面试某个应聘者时,经理只能知道两个变量:当时的应聘者是第几个?当时的应聘者在前面的所有应聘者中相对名次是多少?因此,录用策略应由这两个变量决定,即要判定这两个变量满足什么条件时予以录用.,第一标准下录用策略的研究,我们yi(i=1,2,N)用表示第k个应聘者的绝对名次.设经理录用的是第k个应聘者，为了要录用到最好的应聘者，显然应有,即有如下的录用准则：录用到的应聘者必须是已面试者中相对名次第一.,显然,仅有此准则是不够的.比如,面试第一人时,此人的相对名次是第一,但是此时录用到第一名的概率仅为1/N,此概率很小,不宜采用.,第一标准录用策略,在面试过程中,可能会遇到多个相对第一,越往后的第一越可靠.但是我们不可能无限制地往后等待,因为一旦第一名已经面试过而未录用,则再也无法录用到相对第一.因此,录用策略就是:确定一个数G，先面试G个应聘者,这G个人仅用来作为参考标准,在这G个人之后,一旦有比他们名次均高者就予以录用.录用策略用前面所说的两个变量可以描述为:相对名次第一,kG(G待定).,数学模型,在上面的录用策略下,显然不能肯定录用到第一名.我们的目的是使录用到第一名的概率最大.即:,计算机模拟求解,下面用计算机模拟的方法来确定G的值，使得此时录用到第一名的概率最大.对于固定的N，首先给出1到N的随机排列作为个应聘者的绝对名次.下面的程序给出了这一随机排列的一个构造方法：u=TableRandom,i,1,n;uu=Sortu;y=TablePositionu,uui1,1,i,1,n;,Matemataca(ms1),算法,step2,若y=1，则录用失败，否则转下一步；,然后即可对给定的G模拟出录用到第一名的概率，算法如下：,step1,取前G个数作为参考数，令,按上述算法模拟多次,记录成功的次数,则成功的概率为近似地等于成功次数除以总次数.,step3,从第G+1个数开始，一但有某个应聘者的绝对名次yiy（第i个应聘者被录用），则判断yi是否等于1.若是，则表示录用成功；若不是，则录用失败.,求解结果,对于给定的N,将G从0取到N-1,用上面的算法可以求出成功概率P(G),再进行比较,即可求出最优的G.实际求解时,可以先取大的步长,确定最优的G的大致范围,再用小步长进行搜索.N=100,m=5000(模拟次数)时得到的部分结果G 30 31 32 33 34 35 P 0.3682 0.3748 0.3694 0.3690 0.3778 0.3772G 36 37 38 39 40P 0.3686 0.3826 0.3758 0.3790 0.3738,Matemataca(ms2),第一标准的理论求解,秘书问题用理论的方法求解比计算机模拟方法求解较为复杂,但是可以得到一般性的结论.,根据数学模型,我们首先要求出P(G)的表达式.,第一标准的理论求解,根据P(N-1)=1/N以及P(G)的递推关系式可以得到,再比较P(G)与P(G+1)的大小,可以看出,在G比较小时,P(G+1)P(G),在G比较大时P(G+1)P(G),存在一个最大的P(G*).,第一标准的理论求解,设G*满足,且,则,此时的G*是最优的G.,因此,要求得G*,只需要其满足上面的两个不等式,这用计算机是容易求得的.,Matemataca(ms3),G*(N)/N的极限,根据,有,上式左端为 的积分和,此积分等于-ln(G*/N),令其为1,得到G*/N1/e,事实上,有,G*(N)/N的极限,因此,即,而不等式的左边是大于1的,所以有,即,在区间 上,考虑函数f(x)=1/x,显然有,G*(N)/N的极限,根据另一个不等式,类似方法可以得到,因此,显然,进一步可以证明,G*(N)的近似值,由上面的分析,我们可以得到,这一区间的长度为2-1/e,其中最多有两个整数值.在寻找G*时,只要考察这个区间里的整数点就可以了.,这一区间的的中点为(N-0.5)/e,我们可以取最接近于这个数的整数(N-0.5)/e+0.5作为G*(N)的近似值.事实上,这一结果在N107时,仅有两个数是不正确的.,第二标准:使录用的应聘者的绝对名次尽量的小.,第二标准下录用策略的研究,在第二标准下,未必要录用第一名,而是要录用尽量好的名次.,录用策略可以直观的描述为:如果现在的应聘者的绝对名次(期望值)比后面的应聘者的绝对名次(期望值)小,就予以录用.,第二标准下录用策略的研究,我们先对N=5的情形加以讨论.,如果按照录用策略，前4个应聘者都未被招聘，那么必须招聘第5个应聘者.该应聘者的绝对名次的期望值为(1+5)/2=3.,因此，若前三位应聘者均未被录用，经理在面试第4个应聘者时，如果发现他的绝对名次的期望值不大于3，就应该录用.,相对名次绝对名次,那么，如何能知道第4个应聘者绝对名次的期望值呢？显然必须从他在前4个人中的相对名次来判断.,记lk为第k位面试的应聘者在前k个应聘者中的相对名次，fk(l)为第k个应聘者在前k个应聘者中相对名次为l时，他的绝对名次的期望值.,显然,f4(1)3,f4(4)4,因此,若l42,则第4个应聘者应被录用.,录用策略,类似地，存在数b1,b2,b3，使得第k(k=1,2,3)个应聘者的录用标准为：lkbk.显然b1=0，即第一个应聘者绝对不会被录用.,录用策略：给出数组b1,b2,bN.若前k-1个应聘者都未被录用，则第k个应聘者的录用标准为lkbk.,策略数组,策略数组b1,b2,bN显然以下性质:(1)b1=0,bN=N;(2)bkk/2(kN);(3)bk-1bk.,对N=5,由于b1=0,b4=2,b5=5,根据上面的性质,所有可能的策略数组为0,0,0,2,5,0,0,1,2,5,0,1,1,2,5,计算机模拟求解,在N=5时,我们对上面三个策略数组进行模拟,求出录用者的期望名次.其Mathematica程序为:n=5;b=0,0,0,2,5;m=10000;s=0;Do u=TableRandom,i,1,n;uu=Sortu;y=TablePositionu,uui1,1,i,1,n;k=1;WhilePositionSortTableyj,j,1,k,yk1,1bk,k=k+1;s=s+yk,u,1,m;Ns/m,Matemataca(ms4),求解结果,对前面的三个策略数组,我们模拟得到的一个结果(录取者的目次)为0,0,0,2,5:2.40100,0,1,2,5:2.10390,1,1,2,5:2.0483因此,我们的最优策略数组为0,1,1,2,5,在这一策略下录取者的绝对名次的期望值约为2.0483,理论求解,上面的计算机模拟方法对于N比较的的情况不太适用,因为N比较大时,可能的策略数组相当多.下面我们用理论的方法求解.设vk表示前k-1个应聘者未被录用,从第k个应聘者才开始录用时录用到的应聘者的绝对名次的期望值.显然有vN=(N+1)/2.,理论求解,fk(l)为第k个应聘者在前k个应聘者中相对名次为l时，他的绝对名次的期望值.因此,若fk(l)vk+1,则这个应聘者应被录用.令bk=maxl|fk(l)vk+1,则lbk时,第k个应聘者予以录用.只要求出fk(l)和vk的表达式,即可求出bk.,fk(l)的推导,从第k+1个应聘者开始，任何一个应聘者的绝对名次的值小于l的概率为l/(k+1)，因此在前个应聘者中相对名次为l时，他在N个应聘者中的绝对名次的期望值为,vk的推导,在第k个应聘者的相对名次lbk时,该应聘者被录用,否则应从第k+1个应聘者开始录用.,bk的表达式,根据vk+1的结果,即可求得bk.由于vN=(N+1)/2,得到bN-1=N/2.,。,N=5的结果,b5=5,v5=3b4=3*5/6=2,b3=2.4*4/6=1,b2=2.1*3/6=1,b1=2.05*2/6=0,最优策略数组为0,1,1,2,5,录取者的绝对名次的期望值为2.05.,N=100的结果,最优策略数组:0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,6,6,6,7,7,8,8,9,9,10,11,11,12,14,15,17,19,21,25,30,37,50,100录取者的绝对名次的期望值为3.60323,Matemataca(ms5),计算机模拟方法综述,计算机模拟的方法可以求解一些理论上较难求解的数学问题(主要是随机问题).计算机模拟方法常用于以下情况:(1)系统难以建立数学模型,无法用数学公式表示.(2)数学模型过于复杂,而用计算机模拟较为简单.(3)系统运行费用过高,不适合实际运行.(4)检验经典数学方法求解的数学模型.,
