2016 年 9 月

# 測試回合 - 秘書問題

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

## 1/e 停止規則

``````(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
``````

[圖 2 秘書問題的 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
``````

``````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 方法

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

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

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

``````// 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
}
``````

## 模擬方法

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

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

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

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

``````if (rating == optimalRating)
++numBestSelected;
``````

## 總結

「 候選計數 」 規則會任意選取第 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