Відмінності між версіями «Задача про перебірливу молодицю»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м (додана Категорія:Послідовні методи з допомогою HotCat)
 
Рядок 1: Рядок 1:
−
'''Задача про перебірливу наречену''', або '''проблема зупинки вибору''' може бути сформульована таким чином:<ref> С.М. Гусейн-Заде. Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003</ref>
 +
'''Задача про перебірливу наречену''', або '''проблема зупинки вибору''' може бути сформульована таким чином:<ref> С.&nbsp;М.&nbsp;Гусейн-Заде. Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003</ref>
 
# Молодиця шукає собі нареченого (існує єдине вакантне місце).
  
# Молодиця шукає собі нареченого (існує єдине вакантне місце).
 
# Є відоме число ''n'' претендентів.
  
# Є відоме число ''n'' претендентів.
Рядок 9: Рядок 9:
 
# Мета: вибрати найкращого претендента.
  
# Мета: вибрати найкращого претендента.
   
−
Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших ''n''/''e'' (де ''e''- [[e (число) | основа натурального логарифма ]]) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх.<ref> С.М. Гусейн-Заде, Разборчивая невеста. с. 18, М.: МЦНМО, 2003</ref> При збільшенні ''n'', ймовірність вибору найкращого претендента прагне до 1/''e'', тобто приблизно до 37 %.
 +
Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших ''n''/''e'' (де ''e''- [[e (число) | основа натурального логарифма ]]) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх.<ref> С.&nbsp;М.&nbsp;Гусейн-Заде, Разборчивая невеста. с. 18, М.: МЦНМО, 2003</ref> При збільшенні ''n'', ймовірність вибору найкращого претендента прагне до 1/''e'', тобто приблизно до 37&nbsp;%.
   
−
==Виведення оптимальної стратегії==
 +
== Виведення оптимальної стратегії ==
 
Оптимальним підходом для цієї задачі є [[Марківський момент часу|правило зупину]]. Згідно з ним, молодиця відмовляє першим ''r'' претендентом (нехай претендент ''M'' буде найкращим серед цих ''r'' претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент ''M''. Для довільного ''r'' розглянемо ймовірність обрання найкращого претендента.
  
Оптимальним підходом для цієї задачі є [[Марківський момент часу|правило зупину]]. Згідно з ним, молодиця відмовляє першим ''r'' претендентом (нехай претендент ''M'' буде найкращим серед цих ''r'' претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент ''M''. Для довільного ''r'' розглянемо ймовірність обрання найкращого претендента.
   
 
Нехай подія <math>B_r</math> полягає в обранні найкращого претендента, а подія <math>A_k</math> полягає в тому, що найкращим є претендент <math>k.</math> Отже, повна ймовірність становить
  
Нехай подія <math>B_r</math> полягає в обранні найкращого претендента, а подія <math>A_k</math> полягає в тому, що найкращим є претендент <math>k.</math> Отже, повна ймовірність становить
−
:<math>\mbox{P}(B_r)= \sum_{k=r+1}^n \mbox{P}(B_r|A_k)\mbox{P}(A_k).</math>
 +
: <math>\mbox{P}(B_r)= \sum_{k=r+1}^n \mbox{P}(B_r|A_k)\mbox{P}(A_k).</math>
   
 
Ми можемо стартувати з <math>r+1,</math> бо якщо найкращий претендент є серед перших <math>r,</math> то молодиця відмовила йому. За умови події <math>A_k,</math> подія <math>B_k</math> відбудеться лише якщо найкращий претендент з перших <math>k-1</math> перебуває серед перших <math>r,</math> яким молодиця відмовила. Тепер, для будь-якого довільного впорядкування <math>k-1</math> різних чисел, ймовірність того, що найбільше з них є серед перших <math>r</math> становить <math>r/(k-1).</math> З цього випливає, що
  
Ми можемо стартувати з <math>r+1,</math> бо якщо найкращий претендент є серед перших <math>r,</math> то молодиця відмовила йому. За умови події <math>A_k,</math> подія <math>B_k</math> відбудеться лише якщо найкращий претендент з перших <math>k-1</math> перебуває серед перших <math>r,</math> яким молодиця відмовила. Тепер, для будь-якого довільного впорядкування <math>k-1</math> різних чисел, ймовірність того, що найбільше з них є серед перших <math>r</math> становить <math>r/(k-1).</math> З цього випливає, що
   
−
:<math>\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}.</math>
 +
: <math>\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}.</math>
   
 
== Див. також ==
  
== Див. також ==
Рядок 28: Рядок 28:
   
 
== Посилання ==
  
== Посилання ==
−
* С. М. Гусейн-Заде. [http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf Разборчивая невеста. Библиотека «Математическое просвещение», том 25, МЦНМО, 2003] ISBN 5-94057-076-3
 +
* С.&nbsp;М.&nbsp;Гусейн-Заде. [http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf Разборчивая невеста. Библиотека «Математическое просвещение», том 25, МЦНМО, 2003] ISBN 5-94057-076-3
−
* С. М. Гусейн-Заде. [http://math.ru/media/lecture/3 Разборчивая невеста]. Видео-лекция. [[Малый мехмат]], МГУ, 30.11.2002.
 +
* С.&nbsp;М.&nbsp;Гусейн-Заде. [http://math.ru/media/lecture/3 Разборчивая невеста]. Видео-лекция. [[Малый мехмат]], МГУ, 30.11.2002.
   
 
{{math-stub}}
  
{{math-stub}}

Поточна версія на 01:42, 17 червня 2018

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

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

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

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

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

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

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

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

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

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

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.
Отримано з https://uk.wikipedia.org/w/index.php?title=Задача_про_перебірливу_молодицю&oldid=22806135