x, y, z

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

Сабир Гусейн-Заде

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

Примерно 40 лет тому назад Мартин Гарднер придумал такую задачу: “В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей и королевичей, их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи и королевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего из претендентов?”.

В 1965 году её формулировку и решение рассказал на своём семинаре Е. Б. Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трёх лучших. В таком виде задача была решена лектором при помощи метода, который легко переносится и на ряд близких задач. Так из полушуточной задачи вырос новый раздел математики — теория оптимальной остановки случайных процессов.

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

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

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

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

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

Гусейн-Заде Сабир Меджидович, доктор физико-математических наук, профессор.
Популярные лекции по математике на Малом мехмате МГУ, г. Москва, 30 ноября 2002 г.
Комментарии: 0