Loading AI tools
Задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.
В англоязычной литературе встречается также под названием задачи о секретаре.
Задача может быть сформулирована следующим образом[1]:
- Невеста ищет себе жениха (существует единственное вакантное место).
- Есть известное число претендентов — .
- Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
- Претенденты образуют линейный порядок: асимметричный, транзитивный и любые два сравнимы — о каждом претенденте известно, лучше он или хуже любого из предыдущих.
- Пообщавшись с претендентом, невеста сравнивает его с предыдущими и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет.
- Невеста выигрывает, если она выберет самого лучшего претендента. Выбор даже второго по порядку сравнения — проигрыш.
Требуется найти решение, с наибольшей вероятностью приводящее к выбору самого лучшего претендента.
Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико, оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых (где — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих[2]. При увеличении вероятность выбора наилучшего претендента стремится к , то есть примерно к 37 %.
Задача о разборчивой невесте, по-видимому, была введена в 1949 году Мерриллом М. Фладом, который назвал её проблемой невесты в лекции, которую он прочитал в том же году. Он упоминал ее несколько раз в течение 1950-х годов, например, в выступлении на конференции в Purdue 9 мая 1958 года, и в конечном итоге она стала широко известен в народе, хотя в то время ничего не было опубликовано. В 1958 году он отправил письмо Леонарду Гиллману с копиями дюжине друзей, включая Сэмюэля Карлина и Дж. Роббинса, в котором изложил доказательство оптимальной стратегии с приложением Р. Палермо, который доказал, что среди всех стратегий доминирует стратегия "отклонить первое p безоговорочно, затем принять следующего кандидата, который лучше.
Первая публикация, очевидно, была сделана Мартином Гарднером в журнале Scientific American за февраль 1960 года. Он слышал об этом от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо друг от друга придумали аналогичную задачу в 1958 году; они назвали это «game of googol». Фокс и Марни не знали оптимального решения; Гарднер обратился за советом к Лео Мозеру, который (вместе с Дж. Р. Паундером) предоставил правильный анализ для публикации в журнале. Вскоре после этого несколько математиков написали Гарднеру, чтобы рассказать ему об эквивалентной задаче, о которой они знали по слухам, и все они, скорее всего, сходятся к оригинальной работе Флада.
В 1963 году Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.
1/e-закон наилучшего выбора принадлежит Ф. Томасу Брюссу (1984).
Фергюсон (1989) имеет обширную библиографию и указывает, что подобная (но другая) проблема рассматривалась Артуром Кейли в 1875 году и даже Иоганном Кеплером задолго до этого.
На Конференции Разработчиков Игр 2011 Сергей Орловский рассказал об этой задаче.[3]
Среди вариантов и обобщений задачи встречаются такие, в которых заранее неизвестно общее количество претендентов, или такие, в которых для каждого претендента можно не только сравнить его с остальными, но и дать ему абсолютную оценку[4].
В диссертации Бориса Березовского, впоследствии члена-корреспондента РАН, на соискание ученой степени доктора наук «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищенной в 1983 году, рассматривается обобщение задачи о разборчивой невесте[5].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
