epsilon correct

Есть такой фольклорный фактоид про задачу о разборчивой невесте (в англоязычной литературе её чуть более корректно называют "задачей о секретаре”) в теории оптимального выбора.



Задача даётся в подобной формулировке: дано N элементов (женихов), которые образуют строгий линейный порядок – каждая пара женихов сравнима, и нет ничьих. Женихи приходят в случайном порядке, при этом каждое решение окончательное (какой жених захочет пробовать второй раз, правда же? 💁‍♂️). Нужно разработать алгоритм, чтобы из этого потока выбрать лучшего жениха.



В такой формулировке оптимальная стратегия –

отвергнуть первые 1/ε≈36.8% женихов, а потом – выбрать первого, кто будет лучше всех предыдущих. Этот алгоритм особенно прочно закрепился в self-help книжках от Algorithms to live by до How not to die alone, которые пропагандируют его как универсальную эвристику для решения жизненных задач, и, конечно, поиска партнёра на жизнь. 🥵



Проблема в применении таких эвристик к реальной жизни, конечно, в деталях. В классической формулировке мы сфокусированы на поиске лучшего кандидата, и нас абсолютно не устраивает никакой другой 💔. Можно представить чуть более мягкую и реалистичную версию, когда наша награда за кандидатов распределена равномерно от 0 до 1. Тогда оптимальное время перейти к поиску уменьшается с N/ε до аж √N, что существенно раньше, чем в классической версии.



У проблемы секретаря существует ещё много интересных вариаций, которые до сих пор (!) остаются нерешёнными. Например, моей коллега в 2020 году вывел алгоритм для игры с практически любыми распределениями ценностей женихов, где вероятность выигрыша составляет 51.7%.



Выбирайте с умом! 💡