Поделиться через

  • Статья

Сентябрь 2016

Том 31, номер 9

Тесты - Задача о секретаре

Джеймс Маккафри | Сентябрь 2016

Исходный код можно скачать по ссылке.

Джеймс МаккафриДопустим, вы хотите нанять секретаря. У вас есть пул из 100 соискателей, и вы интервьюируете по одному соискателю в день. После каждого интервью вы должны немедленно решить, нанять текущего соискателя или нет. Если вы не нанимаете соискателя, то не можете вызвать его повторно. У вас нет времени на интервью всех 100 кандидатов, поэтому возникает вопрос: какой алгоритм может максимизировать ваш шанс на выбор лучшего соискателя?

То, что я сейчас описал, является одним из примеров задачи о секретаре (Secretary Problem). Решения этой задачи имеют множество важных применений. Например, в машинном обучении часто требуется придумать какой-то подход для прекращения обучения, который позволит оптимизировать вероятность отбора лучшей модели прогнозирования.

Задача о секретаре является частью более крупного класса задач, иногда называемых задачами лучшего выбора (best choice problems), а также частью того, что называют задачами оптимальной остановки (optimal stopping problems). Насколько мне известно, описание задачи о секретаре (в несколько иной форме) было впервые опубликовано в журнале «Scientific American» в 1960 году. Существуют десятки интересных вариаций этой задачи.

В этой статье я покажу, как подойти к задаче о секретаре, используя так называемое правило остановки 1/e (1/e stopping rule). Хороший способ получить представление о том, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1. Я кодировал эту программу на C#, но у вас не должно возникнуть никаких проблем с рефакторингом кода под другой язык, если вы того пожелаете.

Прогон демонстрационной программы SecretaryProblem
Рис. 1. Прогон демонстрационной программы SecretaryProblem

В этой статье предполагается, что вы умеете программировать хотя бы на среднем уровне, но вам не известна задача о секретаре. Полный исходный код демонстрационной программы вы найдете в пакете сопутствующего кода.

Правило остановки 1/e

Можно математически доказать, что при определенных условиях теоретически вы в состоянии максимизировать вероятность выбора лучшего соискателя в задаче о секретаре, используя так называемое правило или алгоритм 1/e. В контексте задачи о секретаре термин «Кандидат» (Candidate) подразумевает лучшего соискателя, найденного на данный момент времени. Я написал слово «Candidate» с большой буквы, чтобы подчеркнуть, что это слово имеет смысл, отличный от того, который вкладывают в обычном языке, где кандидат и соискатель фактически синонимы.

В следующем объяснении 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 для задачи о секретаре

numSkip = 10 / 2.71828 = 3 numSkip = 10 / 2.71828 = 3
Best applicant rating = 7.0 Рейтинг лучшего соискателя = 7.0
First applicant with better rating = applicant 6 Первый соискатель с лучшим рейтингом = соискатель 6

Соискатель 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, поэтому он не становится Кандидатом. То же самое происходит с соискателем 4. Вы интервьюируете соискателя 5 и находите, что его рейтинг 0.0 (ой, а я работал с ним!), так что он тоже не становится Кандидатом. Вы интервьюируете соискателя 6 и находите, что его рейтинг 8.0. Это высший рейтинг из числа встречавшихся ранее, поэтому он становится Кандидатом, и, поскольку вы миновали первых N/e соискателей, вы сразу же нанимаете соискателя 6.

Заметьте, что алгоритм 1/e не нашел в этом примере лучшего соискателя, но все же обнаружил второго по рейтингу. Если вы применяете алгоритм 1/e для задачи о секретаре, вероятность того, что вы выберете лучшего из N соискателей, равна примерно 1 / e = 1 / 2.71828 = 0.3679.

Демонстрационная программа

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект SecretaryProblem. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio. После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный SecretaryProblemProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

Демонстрационная программа имеет две части. Первые несколько строк в методе Main иллюстрируют алгоритм 1/e при его применении к конкретному примеру задачи о секретаре с 10 соискателями. Вторая часть демонстрации иллюстрирует симуляцию, где алгоритм 1/e выполняется 10 000 раз со 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);

Задача подготавливается определением соискателей как массива типа double, где индекс представляет идентификатор соискателя, а значение ячейки — рейтинг соискателя. Базовая версия задачи о секретаре предполагает, что рейтинги всех соискателей различаются, поэтому равных результатов не может быть.

Определенный в программе метод Select принимает массив rating и использует алгоритм 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 выполняет цикл, вызывая версию метода Select, которая не выводит подробных сведений, и в то же время отслеживает, сколько раз был выбран лучший соискатель.

Метод Select

Определение этого метода начинается с:

static int Select(double[] ratings)
{
  int numApplicants = ratings.Length;
  int numSkip = (int)(numApplicants / Math.E);
  int candidate = 0;  // лучший из встречавшихся соискателей
  double bestRating = ratings[0];
  double rating = 0.0;
  bool readyToHire = false;
...

Количество соискателей определяется числом ячеек в массиве ratings. Вы могли бы делать это явно, передавая дополнительный параметр N в Select. Переменная numSkip — это количество исходных соискателей, которых следует пропустить в процессе отслеживания лучшего соискателя на данный момент. Если бы вы хотели округлить это число, а не усечь, то могли бы написать:

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

Переменная candidate — это лучший соискатель, найденный в любой момент времени в процессе отбора сотрудника, а переменная bestRating — рейтинг, связанный с Кандидатом. Эти две переменные инициализируются значениями для первого соискателя вместо использования имитационных значений, таких как –1 и –1.0 соответственно.

Переменная rating представляет рейтинг текущего соискателя и предназначена просто для удобства чтения. Булева переменная readyToHire равна false при обработке первых numSkip–1 соискателей, а впоследствии устанавливается в 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;
}

Этот метод перебирает все applicant в массиве ratings. Текущий соискатель становится Кандидатом, если его рейтинг выше лучшего найденного на данный момент. Когда булева переменная readyToHire равна false, Кандидаты идентифицированы, но не возвращаются. Если readyToHire равна true, возвращается первый найденный Кандидат, что соответствует немедленному найму в задаче о секретаре.

Альтернативный дизайн — использовать два цикла вместо одного цикла обработки, где первый перебирает соискателей для пропуска, а второй выявляет первого доступного Кандидата:

// 1. Предварительный цикл
for (int applicant = 0; applicant < numSkip; ++applicant)
{
  // Отслеживаем лучший из найденных рейтингов
}

// 2. Цикл найма
for (int applicant = numSkip; applicant <
  numApplicants; ++applicant)
{
  // Возвращаем первого найденного Кандидата
}

Есть вероятность того, что после первых 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

На высокоуровневом псевдокоде этот метод выглядит так:

Генерируем соискателей и рейтинги
Определяем оптимальный рейтинг
Присваиваем number_times_best_applicant_selected = 0

Цикл numTrials раз
  Задаем случайный порядок соискателей
  Выбираем соискателя по алгоритму 1/e
  if выбранный соискатель оптимален
    ++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;
...

Как описывалось ранее, соискатели и их рейтинги хранятся в массиве, где индексом является идентификатор соискателя, а значением ячейки — рейтинг. Значение в ячейке 0 задано равным 0.0, в ячейке 1 — 1.0 и т. д. Например, если N = 100 соискателей, идентификаторы соискателей имеют диапазон от 0 до 99, а оптимальный рейтинг равен 99.0.

Основной цикл обработки в методе Simulation выглядит следующим образом:

for (int trial = 0; trial < numTrials; ++trial) {
  Shuffle(ratings);

  int selected = Select(ratings);
  if (selected == -1)  // не удалось выбрать соискателя
    continue;

  double rating = ratings[selected];
  if (rating == optimalRating)
    ++numBestSelected;
}

Определенный в программе метод Shuffle переупорядочивает рейтинги по месту, используя мини-версию алгоритма Фишера–Йетса:

static void Shuffle(double[] ratings)
{
  for (int i = 0; i < ratings.Length; ++i)
  {
    // Случайный индекс в [i, N)
    int ri = rnd.Next(i, ratings.Length);
    double tmp = ratings[i];
    ratings[i] = ratings[ri];
    ratings[ri] = tmp;
  }
}

Алгоритм Фишера–Йетса часто применяется в машинном обучении и в программах симуляции для перетасовки значений в линейном наборе. Многие языки программирования вроде 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;

Этот подход, как правило, — плохая идея, потому что некоторые значения с плавающей точкой хранятся только как приближенные представления до фиксированного количества знаков после десятичной точки. Подход с проверкой на полное равенство годится в этом конкретном примере, но в целом следует сравнивать на близкое соответствие, а не на точное равенство.

Заключение

Информация, представленная в этой статье, основана главным образом на научной статье У. Стейна (W. Stein), Д. Сила (D. Seale) и А. Рапопорта (A. Rapoport) «Analysis of Heuristic Solutions to the Best Choice Problem» за 2003 год. Вы найдете эту статью в PDF-формате в нескольких местах в Интернете. В статье дан математический анализ правила 1/e и двух дополнительных правил.

Правило счетчика кандидатов (candidate count rule) произвольно выбирает n-ого Кандидата. Скажем, если n = 3, будет выбран третий встретившийся Кандидат. В примере, приведенном в начале этой статьи, где 10 соискателей с рейтингами (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. Как оказалось, правило счетчика кандидатов не очень эффективно.

Правило следующего не кандидата (successive non-candidate rule) выбирает первого Кандидата, встреченного после наблюдения k количества не Кандидатов. Пусть k = 3. Для примера с соискателями и рейтингами первые k не Кандидаты имеют рейтинги 2.0, 1.0 и 4.0. Следующий Кандидат является соискателем 6 с рейтингом 8.0, что опять же случайно совпадает с выбираемым по правилу 1/e. Правило следующего не Кандидата, как было найдено, работает довольно хорошо.

Как только вы ознакомитесь с общей структурой задачи о секретаре, вы найдете немало сценариев, где релевантны ключевые принципы этой задачи. Всякий раз, когда вы сталкиваетесь с задачей программирования, включающей неопределенную точку остановки, вам могут пригодиться идеи из решения задачи о секретаре.

Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Крису Ли (Chris Lee) и Кирку Олинику (Kirk Olynyk).