通过

2016 年 9 月

第 31 卷，第 9 期

测试运行 - 秘书问题

作者 James McCaffrey

James McCaffrey假设你想要招聘秘书。你的池中有 100 位应聘者，你每天面试一位应聘者。每次面试后，你必须立即决定是否聘用当前应聘者。如果你不聘用应聘者，则无法再将其召回。你没有时间面试所有 100 位候选人，因此你可以使用什么算法来最大化选择最佳应聘者的机会？

我刚才描述的是一个秘书问题示例。针对秘书问题的解决方案有许多重要用途。例如，在机器学习中，时常需要找到以某种方式停止培训的方法，以优化选择最佳预测模型的概率。

秘书问题是更大的问题类（有时称为最佳选择）的一部分，也是最佳停止问题的一部分。据我所知，秘书问题的描述（形式稍有不同）最先于 1960 年发布于美国科学杂志。此问题有几十种有趣的变体。

在本文中，我将向你展示如何使用所谓的 1/e 停止规则来解决秘书问题。了解本文所述观点的一个好方法是，查看图 1 中所示的演示程序。该演示使用 C# 编码，但是如果你愿意使用另一种语言重构代码，应该也不会有太大困难。

秘书问题演示程序运行
图 1 秘书问题演示程序运行

要理解本文的内容，你至少需要拥有中级编程能力，但无需了解秘书问题的一切。本文介绍了演示程序的完整源代码，你还可以从随附的代码下载中获取源代码。

1/e 停止规则

此规则可以从数学角度得到证明，在特定条件下，你可以使用所谓的 1/e 规则或算法在秘书问题中从理论上最大化选择最佳应聘者的概率。在秘书问题环境中，“候选人”一词表示在给定时间点内看到的最佳应聘者。我将“候选人”一词加引号以强调此词的意思与其在中文中的常用意思略有区别，通常候选人和应聘者本质上是同义词。

在以下解释说明中，N 表示应聘者总数，e 表示欧拉常数（约为 2.71828）。在口头上，1/e 规则是“跳过前 N / e 位应聘者，但跟踪最佳候选人。然后聘用出现的第一位候选人。如果跳过前 N / e 位应聘者后未出现新的候选人，则失败且不会聘用任何人。”

一个具体示例将清晰说明此算法。图 2 以图形方式对 1/e 停止算法进行了说明。假设你有 10 位应聘者。每位应聘者（在面试之前，你对他们一无所知）的分级为 0.0 到 9.0，值越高越好。应聘者分级为：

(5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0)
  0    1    2    3    4    5    6    7    8    9

秘书问题的 1/e 算法
图 2 秘书问题的 1/e 算法

应聘者 0 的分级为 5.0 且将首先进行面试；应聘者 1 的分级为 2.0 且将第二个进行面试；以此类推。最佳应聘者的编号是 8，分级为 9.0。

跳过的应聘者数为 N / e = 10 / 2.71828 = 3.6788，如果截断则是 3，如果四舍五入则是 4。事实证明，只要 N 不是非常小，截断和四舍五入没有太大区别。假设截断为 3。

你面试应聘者 0 并认为其分级为 5.0，则此人会成为候选人，因为她具有已知最佳分级（目前为止，只看到此分级）。接下来，你面试应聘者 1 并认为其分级为 2.0，则此人不会变为候选人，因为其分级低于 5.0。你面试应聘者 2 并认为其分级为 7.0，则此人会变为新的候选人。此时，你已面试前 N / e = 3 位应聘者，因此你现在准备雇用首先出现的新候选人。

你面试应聘者 3 并认为其分级为 1.0，则此人不会变为候选人。你面试应聘者 5 并认为其分级为 0.0（哎！ 此人曾是我的同事），因此此人也不会候选人。你面试应聘者 6 并认为其分级为 8.0。这是已知的最高分级，因此会成为候选人，因为你已经面试了前 N / e 位应聘者，你会立即雇用应聘者 6。

请注意，在此示例中 1/e 算法未找到最佳应聘者，但找到了仅次于最佳的应聘者。如果将 1/e 算法用于秘书问题，从 N 位应聘者中选择出最佳应聘者的概率约为 1 / e = 1 / 2.71828 = 0.3679。

演示程序

为了创建演示程序，我启动了 Visual Studio，并新建了一个名为 SecretaryProblem 的 C# 控制台应用程序项目。该演示程序对 .NET 的依赖程度并不明显，因此，任何 Visual Studio 版本都可以正常运行。加载模板代码后，我在解决方案资源管理器窗口中右键单击文件 Program.cs 并将其重命名为更具描述性的 SecretaryProblemProgram.cs，Visual Studio 将自动重命名 Program 类。在编辑器窗口的顶端，我删除了所有引用不必要的命名空间的 using 语句，仅保留对顶层 System 命名空间的引用。

演示程序分为两部分。第一部分，Main 方法中的数行内容通过示例介绍了 1/e 算法（将此算法应用于具有 10 位应聘者的特定秘书问题）。演示的第二部分模拟了一个场景，即针对 100 位应聘者运行 10,000 次 1/e 算法。

演示的第一部分中，关键的调用代码行为：

double[] ratings =
  new double[] { 5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0 };
Console.WriteLine("Applicant ratings are: \n");
for (int i = 0; i < ratings.Length; ++i)
  Console.Write(ratings[i].ToString("F1") + "  ");
Console.WriteLine("\n");
int selected = Select(ratings, true);  // Verbose

通过将应聘者定义为 double 类型数组来设置问题，其中索引表示应聘者 ID，单元格值表示应聘者的分级。秘书问题的基本版本假设所有应聘者的分级均不同，因此不可能有关系。

程序定义的 Select 方法接受分级数组并使用 1/e 算法来查找和返回所选应聘者的索引。Select 方法有许多打印进度的 WriteLine 语句，如图 1 所示。

演示的第二部分中，关键的调用代码行（可读性次级编辑）为：

int numHiringSessions = 10000;
int numApplicants = 100;
double pBest = Simulation(numApplicants, numHiringSessions);
Console.WriteLine("Simulation prob of best applicant  = " +
  pBest.ToString("F4"));
double pTheory = 1 / Math.E;
Console.WriteLine("Theoretical prob of best applicant = " +
  pTheory.ToString("F4"));

程序定义的 Simulation 方法接受固定数量的应聘者。备用设计是允许 Simulation 在每次试验中随机选择应聘者数量。在幕后，Simulation 方法会循环，调用 Select 方法的非详细版本，同时持续跟踪选择最佳应聘者的次数。

Select 方法

Select 方法的定义开头如下：

static int Select(double[] ratings)
{
  int numApplicants = ratings.Length;
  int numSkip = (int)(numApplicants / Math.E);
  int candidate = 0;  // Best applicant seen
  double bestRating = ratings[0];
  double rating = 0.0;
  bool readyToHire = false;
...

应聘者数量由分级数组中的单元格数确定。通过将额外参数 N 传递给 Select，可使其明确。变量 numSkip 是跟踪最佳应聘者目前为止跳过的初始应聘者数量。如果要四舍五入而不截断，你可以编写：

int numSkip = (int)Math.Round(numApplicants / Math.E);

招聘期间在任何时候变量 candidate 均为最佳应聘者，且变量 bestRating 是与此候选人相关联的分级。这两个变量初始化为第一位应聘者的值，而不会分别使用 -1 和 -1.0 等虚拟值。

变量 rating 表示当前应聘者的分级，只是为了可读性。处理第一位 numSkip-1 应聘者时，布尔变量 readyToHire 为 false，然后会设置为 true。

Select 方法的主体较短且相对简单：

...
  for (int applicant = 0; applicant < numApplicants; ++applicant) {
    rating = ratings[applicant];
    if (applicant >= numSkip) readyToHire = true;
    if (rating > bestRating) {
      candidate = applicant;
      bestRating = rating;
      if (readyToHire == true) return candidate;
    }
  }
  return -1;
}

此方法会分级数组中浏览每位应聘者。对于每位应聘者，如果当前应聘者的分级大于已知的最佳（最高）分级，则当前应聘者变为候选人。布尔变量 readyToHire 为 false 时，候选人会被确定但不会被返回。readyToHire 为 true 时，返回第一位找到的合适候选人，秘书问题中会作出立即雇佣响应。

备用设计是使用两个循环代替单个进程循环，其中第一个循环遍历要跳过的应聘者，第二个循环确定第一位合适的候选人：

// 1. prelim loop
for (int applicant = 0; applicant < numSkip; ++applicant)
{
  // Track best rating seen
}
// 2. hiring loop
for (int applicant = numSkip; applicant < numApplicants; ++applicant)
{
  // Return first Candidate found
}

第一位 numSkip 应聘者之后可能不会出现有新的候选人。例如，假设你有八个应聘者，其分级为（7.0、6.0、5.0、4.0、3.0、2.0、1.0、0.0）。变量 numSkip 将设置为 8 / 2.71828 = 2。面试过前两位应聘者之后，最佳分级为 7.0 且剩余的六位应聘者均未被确定为候选人。未找到候选人时，方法 Select 返回虚拟值 -1。

Simulation 方法

在高级语言伪代码中，Simulation 方法为：

generate applicants / ratings
determine optimal rating
set number_times_best_applicant_selected = 0
loop numTrials times
  randomize order of applicants
  select an applicant using 1/e algorithm
  if selected applicant is optimal
    ++number_times_best_applicant_selected
  end-if
end-loop
return number_times_best_applicant_selected / numTrials

Simulate 方法的定义开头如下：

static double Simulation(int numApplicants, int numTrials)
{
  double[] ratings = new double[numApplicants];
  for (int i = 0; i < numApplicants; ++i)
    ratings[i] = (i * 1.0);
  double optimalRating = 1.0 * (numApplicants - 1);
  int numBestSelected = 0;
...

如前所述，应聘者及其分级会存储在数组中，其中数组索引为应聘者的 ID，单元格值为分级。单元格 0 中的值设置为 0.0，单元格 1 中的值设置为 1.0，以此类推。例如，如果存在 N = 100 位应聘者，则应聘者 ID 为 0 到 99 且最佳分级为 99.0。

方法 Simulation 的主进程循环为：

for (int trial = 0; trial < numTrials; ++trial) {
  Shuffle(ratings);
  int selected = Select(ratings);
  if (selected == -1)  // failed to select an applicant
    continue;
  double rating = ratings[selected];
  if (rating == optimalRating)
    ++numBestSelected;
}

程序定义的 Shuffle 方法会使用 Fisher-Yates 微型算法就地重新排列分级：

static void Shuffle(double[] ratings)
{
  for (int i = 0; i < ratings.Length; ++i)
  {
    int ri = rnd.Next(i, ratings.Length);  // random index in [i, N)
    double tmp = ratings[i];
    ratings[i] = ratings[ri];
    ratings[ri] = tmp;
  }
}

Fisher-Yates 算法常用于机器学习和模拟程序以打乱线性集合中值的顺序。许多编程语言（如 Python 和 R）在其标准函数库中纳入内置的 Shuffle 方法。这里，程序定义的 Shuffle 方法假设存在类作用域的 random 对象：

class SecretaryProblemProgram
{
  static Random rnd = new Random(0);
  static void Main(string[] args)
  {
...

随机化分级后，方法 Simulation 中的进程循环会调用 Select 方法以使用 1/e 算法选择应聘者，然后检查所选应聘者是否为最佳人选。

检查最佳候选人时，对比两个浮点值以获得完全相等的值：

if (rating == optimalRating)
  ++numBestSelected;

此方法通常并不适用，因为有些浮点值仅存储为近似值（小数点位数固定）。compare-for-exact-equality 方法非常适用于此特定示例，但通常你想要对比以获得非常接近的值而不是完全相等的值。

总结

本文所述信息主要依据 2003 年研究论文：“Analysis of Heuristic Solutions to the Best Choice Problem”（最佳选择问题启发式解决方案分析），作者 W. Stein, D. Seale 和 A. Rapoport。你可以在 Internet 的多个位置找到此 PDF 格式论文。此论文介绍了 1/e 规则的数学分析及两个其他规则。

“候选人计数”规则任意选择第 n 位候选人。例如，如果 n = 3，则将选择出现的第三位候选人。在本文开头介绍的示例中，应聘者对应的分级为 5.0、2.0、7.0、1.0、4.0、0.0、8.0、3.0、9.0、6.0，第三位候选人是应聘者 6，其分级为 8.0，这恰巧与 1/e 规则相同。结果证明，候选人计数规则并不十分有效。

“后续非候选人”规则在查看到 k 非候选人后选择第一位看到的候选人。例如，假设 k = 3。对于示例应聘者和分级，前 k 位非候选人的分级为 2.0、1.0 和 4.0。下一位候选人为应聘者 6 且其分级为 8.0，两次巧合地与 1/e 规则相同。后续非候选人规则证明可非常好地运行。

一旦熟悉秘书问题的常规结构后，你将会发现有不少方案具有相关的关键原理。无论何时面对涉及不确定停止点的编程任务，秘书问题理论会很有用。

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。

衷心感谢以下 Microsoft 技术专家对本文的审阅： Chris Lee 和 Kirk Olynyk