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

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

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

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

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

Примечания

  1. С.М. Гусейн-Заде, Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003
  2. С.М. Гусейн-Заде, Разборчивая невеста, с. 18, М.: МЦНМО, 2003

Ссылки



Wikimedia Foundation. 2010.

Поможем решить контрольную работу

Полезное


Смотреть что такое "Задача о разборчивой невесте" в других словарях:

  • Следующий (Передача) — Следующий (англ. Neхt) телепередача американского канала MTV, производства Калисса Продакшнз (Kalissa Productions). Относится к категории так наз. телевизионных свиданий конкурсов. Авторская задумка Каждый выпуск показывает одного главного… …   Википедия

  • Россия. Русский язык и Русская литература: История русской литературы — История русской литературы для удобства обозрения основных явлений ее развития может быть разделена на три периода: I от первых памятников до татарского ига; II до конца XVII века; III до нашего времени. В действительности эти периоды резко не… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Березовский, Борис Абрамович — Борис Абрамович Березовский …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»