Примерно 60 лет тому
назад М. Гарднер придумал такую задачу: <В некотором царстве,
в некотором государстве пришло время принцессе выбирать себе
жениха. В назначенный день явились1000 царевичей. Их построили в
очередь в случайном порядке и стали по одному приглашать к
принцессе. Про любых двух претендентов принцесса, познакомившись
с ними, может сказать, какой из них лучше. Познакомившись с
претендентом, принцесса может либо принять предложение (и тогда
выбор сделан навсегда), либо отвергнуть его (и тогда претендент
потерян: царевичи гордые и не возвращаются). Какой стратегии
должна придерживаться принцесса, чтобы с наибольшей вероятностью
выбрать лучшего?>.
Задача о "разборчивой невесте", или проблема
остановки выбора может быть сформулирована и следующим образом:
- Владелец патента ищет себе покупателя (существует
единственное вакантное место).
- Есть известное число n претендентов.
- О каждом покупателе можно сказать, лучше он или хуже другого.
- Владелец патента общается с претендентами в случайном
порядке.
- В результате общения владелец патента должен отказать
покупателю либо принять его предложение.
- Решение принимается только исходя из оценки претендента по
сравнению с предыдущими.
- Отвергнутые покупатели не возвращаются.
- Цель: выбрать лучшего покупателя.
Этой задаче было уделено внимание во многом потому, что
оптимальная стратегия имеет интересную особенность. А именно:
если число кандидатов достаточно велико (порядка сотни),
оптимальная стратегия будет заключаться в отклонении всех первых
n/e (где n - основание натурального логагифма)
претендентов и затем выбрать первого, кто будет лучше всех
предыдущих. При увеличении n, вероятность выбора
наилучшего претендента стремится к 1/e, то есть примерно
к 37 %.
Позже с этой задачей оказался связанным очень известный в
современной России человек. Борис Абрамович
Березовский известен как бизнесмен и политический
деятель, но когда-то он был математиком и защитил докторскую
диссертацию по проблемам, связанным как раз с обобщениями этой
задачи.