算法趣谈(1)——秘书问题与37%法则

假如你是一家公司的老板，你要找一个秘书。假设有 \(N\) 个候选者应聘，每个候选者都有能力值。而你能做的是应聘完一个候选者后，获得他的能力值，然后立刻选择要不要选其作为你的秘书。如果你选择了该候选者，那么应聘结束，剩下的候选者也就不必再看了；如果你不选该候选者，那么你就不能回头再来选择这个人了。那么，你该采取什么样的策略，才能最大化你选到最优候选者(能力值最大)的概率呢？

这是一个经典的在线算法的例子，也被称为候选人问题，结婚问题等等。计院 著名课程 高级数据结构与算法分析(俗称ADS)中也有对此的讨论。一个经典且正确的思路是我们必须先看一部分人，残忍的拒绝他们，看完之后我们对这批人的水平有了大概的了解，然后选择下一个比他们都要优秀的人作为最终的秘书。那么我们该拒绝多少人才比较合适呢？

首先最优候选人处在第 \(i\) 个的概率都是 \(\frac1N\) ，假设我们选择放弃 \(m\) 个人，那么想要选到最优的候选人就要满足：在面试他之前我们不能选了别人。还记得我们的策略是说选择第一个比前 \(m\) 个人都要优秀的候选者吗，也就是说前 \(i-1\) 个人中最优秀的那个得在前面 \(m\) 个人里面，不然我们就会选择这个人而不是第 \(i\) 号位的最优人选。而前 \(i-1\) 个人最优秀的那个在前 \(m\) 人中的概率显然是 \(\frac{m}{i-1}\)，所以我们得到最终概率就是对其进行求和，即为：

\[P=\frac mN\sum_{i=m+1}^N\frac1{i-1}\]

注意这里的 \(i\) 是从 \(m+1\) 开始的，因为前 \(m\) 个人我们放弃了所以如果最有候选人在前 \(m\) 个人里面，我们选中的概率即为0。而我们熟悉的近似式 \(\sum\frac1i\approx \ln i\) 告诉我们：

\(P\approx\frac mN(\ln N-\ln m)=-\frac mN\ln\frac mN\) 对其进行求导可以得到 \(\frac mN=\frac1e\) 时，概率最大，为 \(\frac1e\).

如果有了解过这个问题的同学到这一步想必都是熟悉的，我们得到了 \(\frac1e\) 的优雅答案，而 \(\frac1e\) 约等于 37%，也就有了我们平常所说的 37%法则。

但是其实问题还没完，我们只证明了如果我们的策略是选择一部分人并放弃掉，然后选择下一个比这些人都优秀的人的话，那么当人数趋于正无穷时，放弃的人比例最优值是 \(\frac1e\) ，但我们想要证明的是任意一个策略，最终能选到最优秀的人的概率都不会比我们上面的方法更高，即我们的策略是最优的 。 举个例子，我们可以选择第二个比这些人都优秀的人，可以选择下一个比半数放弃的人都要优秀的人，甚至可以直接选择第一个人(当然这肯定是不靠谱的)。

而这个问题同样早就被解决了，我们介绍Beckmann在1990年Dynamic Programming and the Secretary Problem中提出的基于动态规划的分析。

首先我们介绍两个非常重要的函数/数列，它们能帮助我们解决问题：

\(v_m\) 是已经看过 \(m\) 个候选者而且我们没有选第 \(m\) 个候选者的情况下，我们能选中最优候选者的概率。

\(u_m\) 是已经看过 \(m\) 个候选者而且第 \(m\) 个候选者是目前最优的情况下，我们能选中最优候选者的概率。

假设我们的策略是最优的，那么我们可以得到以下两个式子：

\[v_m=\frac m{m+1}v_{m+1}+\frac1{m+1}u_{m+1}\]

若第 \(m\) 个候选者没有被选择，第 \(m+1\) 候选者要么是目前为止最好的(概率为 \(\frac1{m+1}\))，要么不是(概率为 \(\frac{m}{m+1}\))。如果不是，那么选中最好的概率就变成 \(v_{m+1}\)，因为最优解一定不会选择第 \(m+1\) 个候选者；而如果是的话，概率就自然变成我们所定义的 \(u_m\).

\[u_m=\max(\frac mN,v_m)\]

如果已经看过 \(m\) 个候选者而且第 \(m\) 个候选者是目前最优的情况下(\(u_m\) 的定义)，那么我们的选择就变成了我们要选择该候选者或者继续。如果选择这个候选者，那么我们能选择最优候选者的概率就是 \(\frac mN\)，因为我们总共看过 \(m\) 个人且我们选择的其中最好的；而如果继续下去，概率就变成了 \(v_m\)，正如我们定义的那样。

有趣的是，这两个式子已经 完全描述 了最优解的结构，我们可以将所有值都解出来。根据定义 \(v_N=0,u_N=1\)，那么我们可以推出

\[v_{N-1}=\frac{N-1}Nv_N+\frac1Nu_N=\frac1N\\ u_{N-1}=\max(\frac{N-1}N,v_{N-1})=\frac{N-1}N\]

继续写下去我们可以发现规律，在 \(\frac mN\ge v_m\) 即 \(u_m=\frac mN\) 的时候利用数学归纳法不难证明：

\[v_m=\frac mN(\frac1m+\frac1{m+1}+\dots+\frac1{N-1})\\ u_m=\frac mN\max(1,\frac1m+\frac1{m+1}+\dots+\frac1{N-1})\]

而随着 \(m\) 的减小，\(u_m\) 中 \(\frac1m+\dots+\frac1{N-1}\) 也会越来越大最终超过1，我们令最后一个不超过1的值为 \(m^*\)，即

\[\sum_{i=m^*}^{N-1}\frac1i\le1<\sum_{i=m^*-1}^{N-1}\frac1i\]

从这里开始，我们上文归纳出的式子不再适用，但事情实际上更简单了，因为 \(u_m\) 从现在开始就等于 \(v_m\)，而更好的是由于这一点 \(v_m=v_{m+1}\) 从而 \(u_0=v_0=v_{m^*-1}\). 它的意思是当 \(m\) 小到一定程度上的时候，\(u_m\) 就是 \(v_m\)，由它们的定义我们知道这就是说如果看的候选者太少了，那么即使你是目前最好的候选者，也不会选择你。极端情况下我们很容易理解这件事，如果我们只看了一个人，那么这个人当然是目前最好的候选者，

相信读者已经发现了， \(m^*\) 其实就对应着我们所说的放弃的那一部分人。注意到 \(v_0\) 的意思是在我们什么都还没看的时候，能选中最优解的概率，那就是我们所求的答案! \(v_0=v_{m^*-1}=\frac{m^*-1}N(\sum_{m^*-1}^{N-1}{\frac1i})\) 而这和我们上文所说的放弃一部分人然后选则第一个的策略的概率，即式(1)是一致的，这就完成了证明。

总结一下，在秘书问题中，如果想要最大化选到最优者的概率，我们证明了：

• 对于每一个 \(N\) ，放弃一部分人并且选择第一个比这些放弃的人都好的人的这一族算法，都是最优的策略。该放弃的人的比例对应上文的 \(m^*\).
• 当 \(N\to\infty\) 时，最优的放弃比例是 \(\frac1e\)，我们选中最优的人的概率亦为 \(\frac1e\).