Задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача из теории принятия решений и теории оптимальной остановки, впервые сформулированная Мартином Гарднером в 1960 году.
В англоязычной литературе также известна как задача о секретаре.
Формулировка Задача может быть сформулирована следующим образом: Невеста ищет себе жениха (существует единственное вакантное место). Число претендентов известно заранее и равно . Невеста встречается с претендентами в случайном порядке, причём с каждым не более одного раза. Всех претендентов можно однозначно упорядочить от лучшего к худшему; после каждой встречи невеста может определить, является ли текущий кандидат лучшим среди уже рассмотренных. То есть они образуют асимметричный и транзитивный линейный порядок. После знакомства с кандидатом невеста либо принимает его предложение, либо отказывает ему. Если предложение принято, процесс завершается. Если кандидат получил отказ, вернуться к нему позже невозможно. Невеста выигрывает, если выбирает лучшего претендента. Выбор даже второго по качеству кандидата считается проигрышем.
Требуется найти стратегию, максимизирующую вероятность выбора лучшего претендента.
Решения Эта задача получила широкую известность, в частности, из-за интересной особенности оптимальной стратегии. Если число кандидатов достаточно велико, оптимальная стратегия заключается в том, чтобы отклонить первых претендентов (где — основание натурального логарифма), а затем выбрать первого кандидата, который окажется лучше всех предыдущих.
При увеличении вероятность выбора наилучшего претендента стремится к .
История Задача о разборчивой невесте была предложена в 1949 году Мерриллом М. Фладом, который назвал её проблемой невесты в одной из своих лекций. В течение 1950-х годов он неоднократно упоминал эту задачу, в том числе в выступлении на конференции в Purdue 9 мая 1958 года, однако опубликованных работ по теме в тот период не появилось.
В 1958 году Флад направил письмо Леонарду Гиллману и нескольким коллегам, включая Сэмюэля Карлина и Дж. Роббинса. В письме содержалось доказательство оптимальной стратегии и приложение Р. Палермо, в котором рассматривалась стратегия «отклонить первые кандидатов безоговорочно, затем принять следующего кандидата, который окажется лучше предыдущих».
Первая известная публикация задачи появилась в феврале 1960 года в журнале Scientific American в статье Мартина Гарднера. Гарднер узнал о задаче от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо сформулировали похожую задачу в 1958 году под названием «game of googol». Оптимальное решение в публикации было представлено Лео Мозером и Дж. Р. Паундером.
Позднее несколько математиков сообщили Гарднеру о сходных задачах, известных им ранее в устной форме.
В 1963 году Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.
1/e-закон наилучшего выбора был сформулирован Ф. Томасом Брюссом в 1984 году.
Фергюсон (1989) приводит обширную библиографию и указывает, что сходная, хотя и отличная по постановке задача рассматривалась Артуром Кейли в 1875 году и, возможно, Иоганном Кеплером значительно раньше.
Варианты задачи Существуют различные варианты и обобщения задачи. В некоторых из них заранее неизвестно общее число претендентов, в других каждому кандидату можно дать не только относительную, но и абсолютную оценку.
В диссертации Бориса Березовского «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищённой в 1983 году на соискание учёной степени доктора наук, рассматривается одно из обобщений задачи о разборчивой невесте.
Примечания
Ссылки
С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002. И. Р. Высоцкий, И. В. Ященко. Задачи заочных интернет-олимпиад по теории вероятностей и статистике. — МЦНМО, 2017. — С. 255, 275. — ISBN 978-5-4439-1136-6. Errata and Addenda.
Категория:Теория принятия решений