Математик Леонард Эйлер выбирает вам невесту. Или жениха
Есть старая проблема, у которой много названий: «задача секретаря», «выбор супруга» или «задача наилучшего выбора». В общих чертах задача звучит так:
- нам нужно выбрать одного человека, который лучше всех подходит под наши требования;
- мы знаем количество кандидатов — N;
- с кандидатами мы общаемся в случайном порядке;
- после каждого общения мы должны сразу принять решение — подходит нам этот человек или нет. Если подходит — все остальные сразу уходят и мы с ними уже не сможем пообщаться. Если не подходит — уходит этот человек, больше с ним общаться нельзя;
- есть ли алгоритм, который позволит выбрать максимально лучшего в такой ситуации?
Разберём разные подходы к решению и посмотрим, есть ли алгоритм, который позволит сделать это максимально эффективно.
Правильный ответ по-житейски
Лучшее решение этой задачи — отказаться её решать в таких рамках.
Нужно выбрать невесту? Рассмотри все варианты, поговори со всеми, сходи со всеми на свидания, выбери одну, начните отношения, съездите вместе в отпуск, поживите вместе. Если в целом окей — женитесь, если нет — начни сначала.
Нужно выбрать ассистента? Опубликуй вакансию, собери отклики, прочитай всё, выставь оценки откликам, прособеседуй лучших, выбери одного, дай испытательный срок. Если получилось — работай с ним, если нет — обратись к следующему по списку.
Чтобы выбрать наилучшим образом, нужно изучить все варианты, определить критерии выбора, создать для себя какие-то измеримые шкалы, всё измерить, принять решение и дать себе возможность откатиться. Всё. Это правильный ответ.
Ломайте систему и не соглашайтесь на навязанные рамки.
Алгоритм: выбираем первого кандидата
Самый простой вариант — всегда выбирать первого кандидата. С точки зрения эффективности это плохое решение: чем больше кандидатов, тем меньше вероятность того, что мы выберем достаточно хорошего.
Если общее количество кандидатов равно N, то вероятность того, что первый кандидат окажется лучшим равен 1/N. Если у нас сто кандидатов, то вероятность успеха — 1/100, то есть 1%. Это мало, поэтому переходим к другим стратегиям.
Алгоритм с числом Эйлера
Единственное, что мы можем контролировать, кроме уровня текущего кандидата — это количество тех, кому мы уже отказали. Это можно использовать как для выяснения уровня кандидатов, так и для повышения вероятности выбора наилучшего из них.
Математики из разных стран думали над решением этой задачи и вот к каким выводам они пришли:
- Определяем количество кандидатов — N.
- Выбираем из них первые R кандидатов — собеседуем их и запоминаем уровень самого толкового среди них. При этом отказываем всем после собеседования.
- Уровень наилучшего кандидата из первых R человек принимаем за базовый уровень.
- Начинаем смотреть остальных кандидатов.
- Первый кандидат, чей уровень превышает наш базовый уровень, — это наш кандидат и мы его нанимаем.
В общем виде это выглядит так:
Самое сложное — это определить то самое количество первых кандидатов R, которым мы точно откажем. Для этого математики вычислили такую формулу. Если не знаете, что означает значок Σ, — это знак суммы в математике, про это у нас есть отдельная статья.
Если с этой формулой дальше сделать разную математическую магию, то мы получим:
R = N/e,
где e — это число Эйлера, которое примерно равно 2,7182818284. Это значит, что если у нас 100 кандидатов, нам нужно отказать примерно 38 людям, а начиная с 39-го — брать того, чей уровень выше базового.
Алгоритм для неизвестного числа кандидатов
В жизни гораздо чаще встречается ситуация, когда мы не знаем заранее, сколько кандидатов у нас есть. Может оказаться так, что они закончатся раньше, чем мы приступим к реализации нашей стратегии. И так как мы не знаем, сколько кандидатов будет всего, то не сможем оценить первую четверть, потому что неизвестно, когда эта четверть заканчивается.
Чтобы выйти из этой ситуации, придумали такое:
Мы не знаем, сколько у нас кандидатов, но знаем время, в течение которого должны принять решение. Это значит, что мы можем посчитать время, которое у нас есть, и разделить его на число Эйлера. За это время мы находим наилучшего кандидата и используем его уровень как базовый.
Получается, что если у нас на наём есть месяц, то примерно 10 дней мы отсматриваем кандидатов и отказываем им, при этом помечаем себе уровень наилучшего кандидата из тех, что были. А начиная со второй декады собеседуем всех, кто пришёл, и сразу берём первого, кто выше найденного базового уровня. Но это мы сильно упростили, конечно, в формулах там всё гораздо сложнее.
Например, за первые дни мы выяснили, что наилучший кандидат, который у нас был, получил виртуальные 5 из 10 баллов по нашей оценке. Начиная с 11 числа мы ищем того, кто будет выше этих 5 баллов, — и берём первого, кто подходит по этому критерию.
Что дальше
В следующий раз попробуем сделать симуляцию такого алгоритма — с графиками, разными параметрами и кандидатами. Заодно сравним, насколько хорошо теория работает на практике.
