解释

一个老板希望雇佣一名秘书，目前有100位候选人。这个老板平时的面试经验十分丰富， 他能够根据每个人的面试表现给出合理的能力估值。在每一次面试结束后，老板有两个选择，雇佣或者拒绝，而且拒绝之后不能反悔。老板的终极目标是雇佣所有这些候选人中最出色的那一位。

在维基百科中，对于该类问题的定义为：

1 只能选一个

2 有n 个候选人， 而且n 是已知数

3 所有的候选人是可以根据能力值进行排序的

4 面试结束后，需要立即做出接受或者拒绝的决定，并且决定之后不能撤销

5 每一次的接受或者拒绝的决定，是根据目前已经面试结束的整体状况做出的

6 最终的目标是提高选中最优候选人的几率

我们在日常生活中，经常会遇到类似的选择场景，买东西，做选择，当我们犹豫不决的时候，就会十分需要这种最优停止策略。也许无法保证一定能做出最好的选择， 但是可以提高做出最好选择的几率。

Java程序进行模拟

首先创建SecretaryProblem类

import java.util.Random;
 
public class SecretaryProblem {
 
 private double[] candidates;
 private double best = Double.MIN_VALUE;
 private final Random random;
 
 private SecretaryProblem(Random random){
 this.random = random;
 }
 
 /**
 * Generating random secretary problem based on a given size
 * @param size
 * @return
 */
 static SecretaryProblem generate(int size, Random random){
 SecretaryProblem sp = new SecretaryProblem(random);
 sp.candidates = new double[size];
 for(int i = 0; i < size; i++){
 double v = sp.random.nextDouble();
 if(sp.best < v)
 sp.best = v;
 sp.candidates[i] = v;
 }
 return sp;
 }
 
 public double[] getCandidates() {
 return candidates;
 }
 
 public double getBest() {
 return best;
 }
}

最优的策略是不停的面试候选人，然后停在某个特定的位置，对已经面试过得候选人做考评，接下来，录用第一个遇到的强于之前所有人的候选人。此逻辑在 SecretaryProblemSolver 中实现。

public final class SecretaryProblemSolver {
 
 private SecretaryProblemSolver(){}
 
 /**
 * Solving the secretary problem by committing to the best so far
 * after specified hire point
 * @param sp
 * @param hirePoint
 * @return
 */
 public static boolean simpleSolve(SecretaryProblem sp, int hirePoint){
 double bestSoFar = Double.MIN_VALUE;
 for(int i = 0; i < sp.getCandidates().length; i++){
 if(sp.getCandidates()[i] > bestSoFar) {
 bestSoFar = sp.getCandidates()[i];
 if(i > hirePoint)
 return bestSoFar == sp.getBest();
 }
 }
 return sp.getCandidates()[sp.getCandidates().length-1] == sp.getBest();
 }
}

使用Main 方法进行测试

import java.util.Random;
 
public class Main {

 public static void main(String[] arg){
 System.out.println("Welcome to the secretary problem");
 
 final int problemSize = 100;
 final double sampleSize = 100000;
 final Random random = new Random(7);
 
 for(int i = 1; i < problemSize; i++){
 double success = 0;
 for(int j = 1; j < sampleSize; j++){
 SecretaryProblem sp = SecretaryProblem.generate(problemSize, random);
 boolean solved = SecretaryProblemSolver.simpleSolve(sp, i);
 if(solved)
 success++;
 }
 System.out.println(i+", "+success/sampleSize);
 }
 }
}

结论

在程序中，反复测试了特定的停止点，从1-100 都作为停止点进行测试。发现停止点在大概37的时候，选中的成功率最高，在37%左右。

道理

通过结论就很容易理解了这个问题的最优解。我们应该考察了37%的候选人之后，在做决定，而且选中最优候选人的几率是37%。我们的Java 程序已经暴力验证了这一点。

为什么是37%呢？因为1/e 的值就是 0.367879。这个值就是神奇的最优停止点，具体学习可以看看维基百科

https://en.wikipedia.org/wiki/Secretary_problem#1/e-law_of_best_choice

当然，无论候选人是100，还是1000，这个37%都适用。

使用了严格数学方法的建模过程可以在短时间内帮助我们洞悉一些规律，否则我们需要更长的时间去探索。

本文是以下文章的阅读理解

https://www.e4developer.com/2018/09/09/simulating-the-secretary-problem-with-java/