2016 年 9 月

第 31 卷,第 9 期

本文章是由機器翻譯。

測試回合 - 秘書問題

James McCaffrey

James McCaffrey假設您想要雇用秘書。您有 100 求職者集區和一個每日的應徵者面試。每個面試之後,您必須立即決定僱用目前的應徵者。如果您沒有雇用應徵者,您無法呼叫她上一步]。您沒有時間訪問 100 候選項目,因此何種演算法可以使用最大化選取最佳的應徵者的機會?

什麼前述是秘書問題的其中一個範例。秘書問題的解決方案有許多重要的用途。比方說,在機器學習,就通常必須想出一些方法來停止訓練中一種最佳化選取最佳的預測模型的機率。

秘書問題屬於較大類別的問題有時也稱為 [最佳的選擇問題,以及屬於所謂的最佳停止的問題。我所知的最佳,第一次已在科學美國雜誌中 1960年發行秘書問題 (以稍有不同的形式) 的描述。有許多有趣的變化的問題。

在本文中,我將說明如何解決使用所謂的 1/e 停止規則秘書問題。請參閱這篇文章向其中的好方法是檢查示範程式中的 [圖 1。我使用自動程式碼示範使用 C# 中,但您應該可以順利重構另一種語言的程式碼,如果您想。

執行秘書問題示範程式
[圖 1 執行秘書問題示範程式

本文假設您有至少中繼程式設計能力,但不會假設您知道秘書問題。示範程式的完整原始程式碼顯示在本文中,您也可以取得來源附帶的程式碼下載中。

1/e 停止規則

它可以以數學方式證明這一點,某些情況下,您可以理論上最大化選取最佳的應徵者秘書問題中,使用了稱為演算法的 1/e 規則的機率。在內容中秘書問題,詞彙候選表示最佳應徵者看到特定時點的時間。我改成大寫文字強調 word 有不同的意義,比標準英文,其中候選和應徵者是基本上是同義的候選項。

在下列說明,N 代表總數求職者,而 e 代表歐拉常數,也就是大約 2.71828。就 1/e 規則是,「 跳過前 n 個 / e 求職者,但追蹤的最佳候選。然後雇用第一次的應徵者會出現。如果沒有新的候選項目會顯示前 n 個之後 / 略過 e 求職者,然後失敗,而且沒有人雇用。 」

具體的範例,請清除此演算法。1/e 停止演算法會以圖形方式在說明 [圖 2。假設您有 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 的分級,並將訪問了第二個。然後依此類推。最佳的應徵者是等級為 9.0 的人員 8。

略過的應用程式的數字是 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 (Ouch ! 我用過這位人員),便不候選項目,或是。訪談應徵者 6,並尋找 8.0 的分級。這是最高評等所見,以便可加以候選項目,因為您已完成前 n 個 / e 求職者,您會立即雇用應徵者 6。

請注意在此範例中,找不到最佳的應徵者的 1/e 演算法,但是找第二個最佳應徵者。如果您使用的 1/e 演算法秘書問題時,您將會從 N 求職者選取最佳的應徵者的機率為大約 1 / e = 1 / 2.71828 = 0.3679。

示範程式

若要建立示範程式,我啟動 Visual Studio 進行新 C# 主控台應用程式名為 SecretaryProblem。示範程式有沒有顯著的.NET 相依性,以便能使用任何版本的 Visual Studio。在方案總管] 視窗中,範本程式碼載入之後我以滑鼠右鍵按一下檔案 Program.cs,並重新命名了更具描述性的 SecretaryProblemProgram.cs,Visual Studio 會自動重新類別程式命名為我。在編輯器視窗的頂端,我移除了所有 using 陳述式參考不必要的命名空間,但只是一個參考至最上層系統命名空間會保留。

示範程式有兩個部分。在 Main 方法中的前幾行說明時套用到特定的秘書問題範例具有 10 名申請者的 1/e 演算法。示範第二個部分說明的模擬,其中 1/e 演算法在執行 10000 次的 100 名申請者。

金鑰的第一個部分示範呼叫程式碼行如下︰

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 型別陣列,其中索引代表應徵者識別碼,而資料格的值代表申請者的等級設定。秘書問題的基本版本假設所有的應徵者評等不同,因此可能沒有繫結。

程式定義的 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"));

程式定義的模擬方法接受求職者的固定的數。替代的設計是要讓模擬,即可隨機選取每個試用版中的 [應用程式的數目。在幕後呼叫 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 傳遞給選取。變數 numSkip 是同時追蹤最佳應徵者到目前為止略過初始應用程式的數目。如果您想要捨入而不是截斷,您可以撰寫︰

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

變數的候選是最佳的應徵者在任何時間點所示的招聘程序期間的時間,且變數 bestRating 候選相關聯的分級。兩個變數會初始化為值的第一個應徵者,而不是使用空的值,例如-1 和-1.0,分別。

變數評等代表目前的應徵者的評等,而是只是為了方便閱讀。布林值變數 readyToHire 處理的第一個 numSkip 1 求職者,如果為 true,則設為 true 之後。

選取方法的主體是簡短且相當簡單︰

...
  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,沒有任何其餘的六個求職者會被視為候選。找到沒有候選人時選取方法傳回空值-1。

模擬方法

高層級的虛擬程式碼中的模擬方法是︰

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

模擬的方法定義的開頭︰

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;
...

如先前所述,求職者及評等會儲存在陣列,其中的陣列索引是應徵者的識別碼,而資料格的值是評等中。資料格 0 中的值設定為 0.0,資料格 1 中的值設定為 1.0,依此類推。例如,如果有 N = 100 求職者,應徵者識別碼是 0 到 99,最佳的評等是 99.0。

在方法中模擬的主要處理迴圈是︰

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;
}

程式定義的方法,名為隨機排列分級就地使用費雪 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;
  }
}

費雪 Yates 演算法通常用於機器學習和模擬程式隨機播放線性集合中的值。許多程式語言,例如 Python 和 R,包括內建隨機方法做為其標準函式程式庫的一部分。在這裡,程式定義的隨機方法假設類別範圍 Random 物件存在︰

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

分級會隨機之後,處理中的迴圈方法模擬呼叫 Select 方法來選擇使用 1/e 演算法應徵者,並接著選取應徵者會檢查以查看它們是否有最佳的應徵者。

核取時的最佳候選項,會比較兩個浮點數的值完全相等︰

if (rating == optimalRating)
  ++numBestSelected;

這種方法通常是個好主意,因為某些浮點數的值會儲存僅為近似值,以固定的小數位數。比較的-完全為相等的方法是在這個範例中,[確定],但通常您會想要非常接近,而不是完全相等比較。

總結

本文中的資訊會根據主要 2003年研究報告 」 分析啟發式解決方案以最佳的選擇問題的 「 W.Stein、 D.Seale 和 A.Rapoport。您可以找到以 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) 開頭,第三個候選是等級為 8.0 的應徵者 6 這正巧是 1/e 規則相同。其實,候選計數規則不是非常有效的。

「 連續非候選 」 規則會選取出現之後觀察 k 非求職者的第一個候選。例如,假設 k = 3。針對範例求職者和評等,第一個 k 非-候選項目有分級 2.0、 1.0 和 4.0。下一步候選是 8.0 的應徵者 6 等級,即一次,碰巧的是 8.0 的,1/e 規則相同。後續的非候選規則其實能順利運作。

一旦您熟悉秘書問題的一般結構,您會發現很多案例的主要原則所在位置相關。每當您面臨的程式設計工作,包括不確定的停止點,秘書問題的想法可能很有用。


Dr。James McCaffreyRedmond,華盛頓中的 Microsoft Research 的運作方式他曾在包括 Internet Explorer 和 Bing 的數個 Microsoft 產品。Dr.McCaffrey 可以到達jammc@microsoft.com

感謝以下的微軟技術專家對本文的審閱: Chris Lee 和 Kirk Olynyk