Задача про перебірливу молодицю

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

  1. Молодиця шукає собі нареченого (існує єдине вакантне місце).
  2. Є відоме число n претендентів.
  3. Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
  4. Молодиця спілкується з претендентами у випадковому порядку.
  5. В результаті спілкування з кожним нареченим молодиця повинна йому відмовити або прийняти його пропозицію.
  6. Рішення приймається тільки виходячи з оцінки претендента в порівнянні з попередніми.
  7. Знехтувані женихи не повертаються.
  8. Мета: вибрати найкращого претендента.

Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших n/e (де e- основа натурального логарифма ) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх.[2] При збільшенні n, ймовірність вибору найкращого претендента прагне до 1/e, тобто приблизно до 37 %.

Виведення оптимальної стратегії[ред.ред. код]

Оптимальним підходом для цієї задачі є правило зупину. Згідно з ним, молодиця відмовляє першим r претендентом (нехай претендент M буде найкращим серед цих r претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент M. Для довільного r розглянемо ймовірність обрання найкращого претендента.

Нехай подія B_r полягає в обранні найкращого претендента, а подія A_k полягає в тому, що найкращим є претендент k. Отже, повна ймовірність становить

\mbox{P}(B_r)= \sum_{k=r+1}^n \mbox{P}(B_r|A_k)\mbox{P}(A_k).

Ми можемо стартувати з r+1, бо якщо найкращий претендент є серед перших r, то молодиця відмовила йому. За умови події A_k, подія B_k відбудеться лише якщо найкращий претендент з перших k-1 перебуває серед перших r, яким молодиця відмовила. Тепер, для будь-якого довільного впорядкування k-1 різних чисел, ймовірність того, що найбільше з них є серед перших r становить r/(k-1). З цього випливає, що

\mbox{P}(B_r) = \sum_{k=r+1}^n\frac{r}{k-1}\cdot \frac{1}{n} = \frac{r}{n}\sum_{j=r}^{n-1}\frac{1}{j}.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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

Посилання[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.