Задача о разборчивой невесте

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формулировка[править | править исходный текст]

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

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

Решения[править | править исходный текст]

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

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

Интересные факты[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. С. М. Гусейн-Заде, Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003
  2. С. М. Гусейн-Заде, Разборчивая невеста, с. 18, М.: МЦНМО, 2003

Ссылки[править | править исходный текст]