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

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

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

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

Формулировка[править | править код]

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

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

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

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

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

Варианты задачи[править | править код]

Среди вариантов и обобщений задачи встречаются такие, в которых заранее неизвестно общее количество претендентов, или такие, в которых для каждого претендента можно не только сравнить его с остальными, но и дать ему абсолютную оценку[3].

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

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

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

См. также[править | править код]