WikiSort.ru - Не сортированное

Задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.

В англоязычной литературе встречается также под названием задачи секретаря.

Формулировка

Задача может быть сформулирована следующим образом:^[1]

1. Невеста ищет себе жениха (существует единственное вакантное место).
2. Есть известное число претендентов — ${\displaystyle n}$ .
3. Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4. О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.
5. В результате общения с текущим претендентом невеста должна либо ему отказать, либо принять его предложение. Если предложение принято, процесс останавливается, если невеста отказывает жениху, то вернуться к нему позже она не сможет.
6. Цель — выбрать лучшего претендента.

Решения

В 1963 году академик РАН Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых ${\displaystyle n/e}$ (где ${\displaystyle e=2{,}718\,281\ldots }$  — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих^[2]. При увеличении ${\displaystyle n}$ вероятность выбора наилучшего претендента стремится к ${\displaystyle 1/e}$ , то есть примерно к 37 %.

Интересные факты

В диссертации члена-корреспондента РАН Бориса Березовского на соискание ученой степени доктора наук «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищенной в 1983 году, рассматривается обобщение задачи о разборчивой невесте.

Примечания

Ссылки

• С. М. Гусейн-Заде. Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3.
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
• И. Р. Высоцкий, И. В. Ященко Задачи заочных интернет-олимпиад по теории вероятностей и статистике —  МЦНМО, 2017, с.255, 275 — ISBN 978-5-4439-1136-6

Для улучшения этой статьи желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).