Scisne?

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

Гусейн-Заде С. М.

Комментарии: 0

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

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

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

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

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

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