- Задача о разборчивой невесте
-
Задача о разборчивой невесте, или проблема остановки выбора может быть сформулирована следующим образом:[1]
- Невеста ищет себе жениха (существует единственное вакантное место).
- Есть известное число n претендентов.
- Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
- О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.
- В результате общения с текущим претендентом невеста должна ему отказать либо принять его предложение. Если предложение принято, процесс останавливается.
- Цель: выбрать лучшего претендента.
Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в отклонении всех первых n/e (где e = 2,781… — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих.[2] При увеличении n, вероятность выбора наилучшего претендента стремится к 1/e, то есть примерно к 37%.
Примечания
Ссылки
- С. М. Гусейн-Заде Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3
- С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
Для улучшения этой статьи желательно?: - Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
Категория:- Теория принятия решений
Wikimedia Foundation. 2010.