你的位置:首页 > 操作系统

[操作系统]算法导论之在线雇用问题


问题:假设你需要雇用一名新的办公室助理。你先前的雇用尝试都以失败告终,所以你决定找一个雇用代理。雇用代理每天给你推荐一个应聘者。你会面试这个人,然后决定要不要雇用他。你必须付给雇用代理一小笔费用来面试应聘者。要真正地雇用一个应聘者则要花更多的钱,因为你必须辞掉目前的办公室助理,还要付一大笔中介费给雇用代理。你的诺言是在任何时候,都要找到最佳人选来担任这项职务。因此,你决定在面试完每个应聘者后,如果这个应聘者比目前的办公助理更有资格,你就会辞掉目前的办公室助理,然后聘请这个新的应聘者。你愿意为这种策略而付出费用,但希望能够预测这种费用会是多少。

我们来考虑这个问题的一个变形。假设现在我们不希望面试所有的应聘者来找到最好的一个,也不希望因为不断有更好的申请者出现而不停地雇用新人解雇旧人。我们愿意雇用接近最好的应聘者,只雇用一次。我们必须遵守公司的一个要求:在每次面试后,必须或者立即提供职位给应聘者,或者告诉应聘者他们将无法得到这份工作。在最小化面试次数和最大化雇用应聘者的质量两方面如何取得平衡?

解答:

可以通过以下方式来对这个问题建模。在面试一个应聘者之后,我们能够给他一个分数;令score(i)表示给第i位应聘者的分数,并且假设没有两个应聘者的分数相同。在面试j个应聘者之后,我们知道其中哪一个分数最高,但是不知道在剩余的n-j个应聘者中会不会有更高分数的应聘者。我们决定采用这样一个策略:选择一个正整数k<n,面试前k个应聘者然后拒绝他们,再雇用其后比前面的应聘者有更高分数的第一个应聘者。如果结果是最好的应聘者在前k个面试的之中,那么我们将雇用第n个应聘者。这个策略形式化地表示在如下所示的过程ONLINEMAXIMUM(k,n)中,该过程返回的是我们希望雇用的应聘者的下标值。

/*** * @param k 前k个被拒绝的应聘者* @param n 总共n个应聘者* @return*/int ONLINEMAXIMUM(int k, int n){	int[] score = new int[n];1	int bestscore = -999999;2	for(int i = 1; i < k; i++){3		if(score[i] > bestscore){4			bestscore = score[i];		}	}5	for (int i = k+1; i < n; i++) {6		if(score[i] > bestscore){7			return i;		}	}8	return n;}

对每一个可能的k值,我们希望确定雇用到最好的应聘者的概率。然后选择最佳的k值,并用此值来实现这个策略。先假设k是固定的。令M(j)=maxa<=i<=b{score(i)}表示应聘者a到b中的最高分数。令S表示我们成功选择最好的应聘者的事件,Si表示当最好的应聘者是第i个面试者时成功的事件。由于不同的Si不相交,有

       n

Pr{S}=∑ Pr{Si}。注意到当最好的应聘者是前k个应聘者中的一个时,我们不会成功,有

     i=1

Pr{Si}=0,i=1,2,...,k。于是得到

     n

Pr{S}=∑ Pr{Si}                    (公式2)

      i=k+1

现在我们来计算Pr{Si}。为了当第i个应聘者是最好的时成功,有两件事情必须发生。首先,最好的应聘者必须在位置i上,用事件Bi表示。其次,算法不能选择在位置k+1到i-1中的任何一个应聘者,而这个选择仅发生在当j满足k+1<=j<=i-1时,程序第6行有score[j]<bestscore。(因为分数是唯一的,可以忽略score[j]=bestscore的可能性。)换言之,所有score[k+1]到score[i-1]的值都必须小于M(k);如果其中有大于M(k)的数,将返回第一个大于M(k)的数的下标。用Oi表示在位置k+1到i-1中没有任何应聘者被选取的事件。幸运的是,事件Bi和Oi是独立的。事件Oi只依赖于位置1到i-1中数值的相对次序,而Bi只依赖于位置i的数值是否大于所有其他位置的数值。位置1到i-1中各数值的相对次序如何,并不应影响位置i的值是否大于位置1到i-1中的所有数值,而且位置i的值也不会影响位置1到i-1中值的次序。因此,应用公式1得

Pr{Si}=Pr{Bi∩Oi}=Pr{Bi}Pr{Oi}

Pr{Bi}的概率显然是1/n,因为最大值等可能地是n个位置中的任何一个。如果事件Oi要发生,在位置1到i-1中的最大值必须在前k个位置的一个,而且最大值等可能地是i-1个位置中的任何一个。因此,Pr{Oi}=k/(i-1),Pr{Si}=k/(n(i-1))。利用公式2有

           n             n                    n                    n-1

Pr{S}=∑ Pr{Si}= ∑ k/(n(i-1)) = k/n ∑ 1/(i-1) = k/n ∑ 1/i

         i=k+1       i=k+1                 i=k+1              i=k

我们利用积分来近似约束这个和数的上界和下界。根据不等式公式3,有

                n-1

nk1/xdx<=∑ 1/i<=∫n-1k-11/xdx

                i=k

解这些定积分可以得到下面的界:

k/n(lnn-lnk)<=Pr{S}<=k/n(ln(n-1)-ln(k-1))

这提供了Pr{S}的一个相当紧确的界。由于我们希望最大化成功的概率,因而主要关注如何选取k的值,使其能够最大化Pr{S}的下界。(除此之外,下界表达式比上界表达式容易最大化。)将表达式(k/n)(lnn-lnk)对k求导,得

1/n(lnn-lnk-1)

令此导数等于0,我们看到当lnk=lnn-1=ln(n/e),或等价地,当k=n/e时,概率的下界最大化。因此,如果用k=n/e来实现我们的策略,则可以以至少为1/e的概率,成功地雇用到最有资格的应聘者。

 

 

公式1:Pr{A∩B}=Pr{A}Pr{B}

公式3:

当f(k)单调递减时,可以使用积分来计算界

                      n

mn+1f(x)dx<=∑ f(k)<=∫nm-1f(x)dx

                     k=m