秘书问题与计算机模拟ppt课件.ppt

《秘书问题与计算机模拟ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、秘书问题与计算机模拟南京邮电大学理学院杨振华问题设想一个经理要从若干个应聘者中雇用一名秘书.按照某种标准,可用1,2,···,N分别表示这些应聘者的优劣的绝对名次.1表示最优者,N表示最劣者.假设这些应聘者是逐个到来接受经理面试的，并且应聘者到来的优劣次序是随机的.经理每次会见一名应聘者，面试后决定录用与否.如果录用到当时面试的应聘者，则停止下面的会见，否则面试下一位.问题我们还假定,每个当时不被录用的应聘者是不能事后再招回录用的,在经理每一次面试后,他只知道当时的应聘者与先前已面试者比较的相对名次,而不知道当时应聘者的绝对名次.现在要问经理要怎样决定他

2、的录用策略,或者说经理在何时停止他的会见(录用当时的应聘者)是最优的.当然这里最优要有一个标准,通常采用下面两种标准:第一标准:使录用到最优应聘者的概率最大;第二标准:使录用的应聘者的绝对名次尽量的小.录用策略所谓录用策略,就是何时录用当时的应聘者.在面试某个应聘者时,经理只能知道两个变量:当时的应聘者是第几个?当时的应聘者在前面的所有应聘者中相对名次是多少?因此,录用策略应由这两个变量决定,即要判定这两个变量满足什么条件时予以录用.第一标准下录用策略的研究我们yi(i=1,2,···,N)用表示第k个应聘者的绝对名次.设经理录用的是第k个应聘者，为了要

3、录用到最好的应聘者，显然应有即有如下的录用准则：录用到的应聘者必须是已面试者中相对名次第一.显然,仅有此准则是不够的.比如,面试第一人时,此人的相对名次是第一,但是此时录用到第一名的概率仅为1/N,此概率很小,不宜采用.第一标准录用策略在面试过程中,可能会遇到多个相对第一,越往后的第一越可靠.但是我们不可能无限制地往后等待,因为一旦第一名已经面试过而未录用,则再也无法录用到相对第一.因此,录用策略就是:确定一个数G，先面试G个应聘者,这G个人仅用来作为参考标准,在这G个人之后,一旦有比他们名次均高者就予以录用.录用策略用前面所说的两个变量可以描述为:相对

4、名次第一,k≥G(G待定).数学模型在上面的录用策略下,显然不能肯定录用到第一名.我们的目的是使录用到第一名的概率最大.即:计算机模拟求解下面用计算机模拟的方法来确定G的值，使得此时录用到第一名的概率最大.对于固定的N，首先给出1到N的随机排列作为个应聘者的绝对名次.下面的程序给出了这一随机排列的一个构造方法：u=Table[Random[],{i,1,n}];uu=Sort[u];y=Table[Position[u,uu[[i]]][[1,1]],{i,1,n}];Matemataca(ms1)算法step2,若y=1，则录用失败，否则转下一步；然后

5、即可对给定的G模拟出录用到第一名的概率，算法如下：step1,取前G个数作为参考数，令按上述算法模拟多次,记录成功的次数,则成功的概率为近似地等于成功次数除以总次数.step3,从第G+1个数开始，一但有某个应聘者的绝对名次yi

6、03132333435P0.36820.37480.36940.36900.37780.3772G3637383940P0.36860.38260.37580.37900.3738Matemataca(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)

7、P(G*).第一标准的理论求解设G*满足且则此时的G*是最优的G.因此,要求得G*,只需要其满足上面的两个不等式,这用计算机是容易求得的.Matemataca(ms3)G*(N)/N的极限根据有上式左端为的积分和此积分等于-ln(G*/N)令其为1,得到G*/N≈1/e事实上,有G*(N)/N的极限因此即而不等式的左边是大于1的,所以有即在区间上,考虑函数f(x)=1/x,显然有G*(N)/N的极限根据另一个不等式,类似方法可以得到因此显然进一步可以证明G*(N)的近似值由上面的分析,我们可以得到这一区间的长度为2-1/e,其中最多有两个整数值.在寻找G

8、*时,只要考察这个区间里的整数点就可以了.这一区间的的中点为(N-0.5)/e,