Задача о разборчивой невесте
Задача о секретаре, секретарше или секретарях — это математическая задача в теории оптимальной остановки в теории принятия решений, теории вероятностей и статистике. Эта проблема также известна как проблема принцессы и проблема немедленного найма. Внезапно, но в русской литературе она называется задачей о разборчивой невесте.
Контекст данной задачи таков: кто-то хочет нанять секретаря и собеседует по-очереди конечное и известное количество кандидатов. Для каждого он должен решить, брать его на работу или нет. Если это так, он завершает процесс найма, не видя других кандидатов. В противном случае у него нет возможности перезвонить кандидату позже. В контексте этой проблемы рекрутер не имеет доступа к абсолютной ценности кандидатов (например, «этот кандидат имеет оценку 7/10»), он может только сравнивать их (например, «этот кандидат лучше, чем первый но хуже второго).
Цель состоит в том, чтобы определить стратегию, которая максимизирует вероятность найма лучшего кандидата.
На первый взгляд эта задача кажется непреодолимой и даже обманом. Эта проблема на самом деле имеет элегантное математическое решение. Практическая мудрость, вытекающая из данной задачи, обычно теряется на страницах книг по теории вероятностей. Я думаю, что это очень неудачно, потому что есть много ситуаций, в которых знание оптимальной стратегии выбора среди неизвестных альтернатив может быть полезным. Эта стратегия может вам помочь в следующих житейских ситуациях:
Решение снять квартиру в многолюдном городе.
Быстро найти старшую карту во время перетасовки колоды.
Найти недорогой магазин без кучи поездок туда и обратно.
Ну и, наконец, выбрать мужа или жену, не возвращаясь к бывшим ;)
Во всех этих случаях вы не знаете, какие варианты будут следующими. Однако вы можете захотеть принять быстрое, но в то же время справедливое решение. Моя цель — объяснить решение задачи о секретаре в понятных терминах и проиллюстрировать его там, где это необходимо.
Перед лицом полной неопределенности заманчиво полагаться на удачу. Вы можете принять произвольное решение: «все равно я выбираю первый вариант». Неудивительно, что эта случайная стратегия работает плохо. У вас есть достаточно маленький шанс, что первый кандидат будет лучшим. То же самое верно, когда вы всегда выбираете последнего кандидата или всегда кандидата номер 2. Ваши шансы всегда равны для каждой из заранее фиксированных подобных опций.
Случайная стратегия становится все менее и менее полезной по мере увеличения числа кандидатов.
Возможно, вы поняли, что единственная переменная, которую вы контролируете, — это количество вариантов, от которых вы отказались. Ваша стратегия может заключаться только в том, чтобы решить, от скольких вариантов вы хотите отказаться, прежде чем вы действительно начнете принимать решения. Суть подхода в том, что вы хотите подождать достаточно долго, чтобы иметь хорошую отправную точку, а затем выбрать следующего кандидата, который лучше, чем варианты, которые вы уже рассмотрели. Количественно эта стратегия формулируется следующим образом:
Давайте посмотрим на первые X вариантов и отклоним их. Запоминаем лучший вариант. Назовём его B.
Мы продолжаем рассматривать последующие варианты, пока не будет найден первый с оценкой выше B. Мы выбираем этот вариант.
Эта стратегия выглядит многообещающе, но необходимо уточнить одну деталь: от скольких вариантов следует отказаться?
Когда число X слишком велико, вы можете установить более высокие критерии выбора. Но вы также рискуете отказаться от лучшего варианта. Когда число X слишком маленькое, у вас недостаточно точная отправная точка. Скорее всего, вы выберете неоптимальный вариант. Что нам нужно сделать, так это найти оптимальное значение количества отказов, учитывая общее количество кандидатов. Чтобы понять это, требуются достаточно серьёзные знания теории вероятностей. Однако, мы избавим вас этой сложности.
Оптимальная стратегия состоит в том, чтобы пропустить 37% кандидатов (или, точнее, пропорцию 1/e), а затем подождать, пока не будет кандидата лучше, чем все кандидаты из этой первой выборки. Иногда мы говорим о правиле 37%.