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

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

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

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

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

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

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

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

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

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

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

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

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

История[править | править код]

Задача о разборчивой невесте, по-видимому, была введена в 1949 году Мерриллом М. Фладом, который назвал ее проблемой невесты в лекции, которую он прочитал в том же году. Он упоминал его несколько раз в течение 1950-х годов, например, в выступлении на конференции в Purdue 9 мая 1958 года, и в конечном итоге он стал широко известен в народе, хотя в то время ничего не было опубликовано. В 1958 году он отправил письмо Леонарду Гиллману с копиями дюжине друзей, включая Сэмюэля Карлина и Дж. Роббинса, в котором изложил доказательство оптимальной стратегии с приложением Р. Палермо, который доказал, что во всех стратегиях доминирует стратегия «отклонить первое p безоговорочно, затем принять следующего кандидата, который лучшe.

Первая публикация, очевидно, была сделана Мартином Гарднером в журнале Scientific American за февраль 1960 года. Он слышал об этом от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо друг от друга придумали аналогичную задачу в 1958 году; они назвали это "game of googol". Фокс и Марни не знали оптимального решения; Гарднер обратился за советом к Лео Мозеру, который (вместе с Дж. Р. Паундером) предоставил правильный анализ для публикации в журнале. Вскоре после этого несколько математиков написали Гарднеру, чтобы рассказать ему об эквивалентной задаче, о которой они слышали по слухам, и все они, скорее всего, сходятся к оригинальной работе Флада.

1/e-закон наилучшего выбора принадлежит Ф. Томасу Брюссу (1984).

Фергюсон (1989) имеет обширную библиографию и указывает, что подобная (но другая) проблема рассматривалась Артуром Кейли в 1875 году и даже Иоганном Кеплером задолго до этого.

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

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