Задача даётся в подобной формулировке: дано
N элементов (женихов), которые образуют строгий линейный порядок – каждая пара женихов сравнима, и нет ничьих. Женихи приходят в случайном порядке, при этом каждое решение окончательное (какой жених захочет пробовать второй раз, правда же? 💁♂️). Нужно разработать алгоритм, чтобы из этого потока выбрать лучшего жениха.В такой формулировке оптимальная стратегия –
отвергнуть первые
1/ε≈36.8% женихов, а потом – выбрать первого, кто будет лучше всех предыдущих. Этот алгоритм особенно прочно закрепился в self-help книжках от Algorithms to live by до How not to die alone, которые пропагандируют его как универсальную эвристику для решения жизненных задач, и, конечно, поиска партнёра на жизнь. 🥵Проблема в применении таких эвристик к реальной жизни, конечно, в деталях. В классической формулировке мы сфокусированы на поиске лучшего кандидата, и нас абсолютно не устраивает никакой другой 💔. Можно представить чуть более мягкую и реалистичную версию, когда наша награда за кандидатов распределена равномерно от 0 до 1. Тогда оптимальное время перейти к поиску уменьшается с
N/ε до аж √N, что существенно раньше, чем в классической версии.У проблемы секретаря существует ещё много интересных вариаций, которые до сих пор (!) остаются нерешёнными. Например, моей коллега в 2020 году вывел алгоритм для игры с практически любыми распределениями ценностей женихов, где вероятность выигрыша составляет 51.7%.
Выбирайте с умом! 💡