Проблемът в дискриминация neveste-)

В определен царство принцеса реших, че е време да се оженят. Ние свиква първенци от целия свят, и е на 1000 претенденти. И всичките първенци са сравними помежду си - за всеки две може да се каже за тях е по-добре; Освен това, съотношението на "по-добре" е преходен. Кандидатите идват на принцесата в даден момент, един по един. Целта на принцеса - вземете най-доброто от младоженеца. тя решава на всяка стъпка, независимо дали това се даден кандидат за съпруг или не. Ако се претендентите в този преглед не свършва. Ако отхвърлена, решението най-накрая (Принцовите хора горди и процесът продължава. Ако в края на принцесата не получи по-добре, а след това се губи (и отива в манастира). Въпросът е при какви стратегии трябва да действат принцеса, за да спечели най-вероятно, т.е. получите най-добрия принц?
PS IMHO оптимална стратегия може да бъде полезно в практиката. Например, ако ще да си купя нещо на пазара, където има много сергии, разположени в един ред (и не искам да се върна).
PPS каза, че повсеместното този проблем се занимава BA Березовски

Junk.
Бота terver

> Ако в края на принцесата не получи по-добре, а след това се губи (и отива в манастир
Какво означава "по-добре"?
Принцеса Най-добрият принц вероятно все още няма да се вероятността от 1/1000 от това, което дори и с помощта на алгоритми - да се подобри значително тази цифра няма да работи.

Да, принцесата трябва да пропусне първите н / д конярите (т.е., N = 1000 около 368 души просто да ги наизустяват за бъдещо сравнение, а след това тя трябва да избере първото, което е по-добре от всички свои предшественици.

много подобен на истината
правим Лагутин в класирането казали

Ура]
Аз съм се познае.
Остава само да чуя обосновката на този факт.

И за нас, ако не греша, Bulinskiy на първата лекция

Какво означава "по-добре"?
". [.] Е преходен"; - "И всичките първенци са сравними помежду си за всеки две може да се каже за тях е по-добре [.] Освен това, съотношението на" по-добре (C) Това означава, че сред първенците са най-добрите.
Принцеса Най-добрият принц вероятно все още няма да се вероятността от 1/1000 от това, което дори и с помощта на алгоритми - да се подобри значително тази цифра няма да работи.
Когато оптималната стратегия за спечелване на вероятност от около 0368, т.е. значително по-висока.

Благодаря ви, почитан като нещо през свободното си време
PS-Offtopic: SM Хюсеин-Zade четем angem

PS IMHO оптимална стратегия може да бъде полезно в практиката. Например, ако ще да си купя нещо на пазара, където има много сергии, разположени в един ред (и не искам да се върна). Напразно. Къмпинг все още е по-малко от хиляда, ако не и по-малко.

> За 0.368
Къде е този номер?
368 души са изчезнали точно, и по този начин остава възможност - че vybiresh, например, втората прохладата, а не първата.

368 души са изчезнали точно, и по този начин остава възможност - че vybiresh, например, втората прохладата, а не първата. Аз не виждам никакво противоречие с факта, че вероятността за печалба е равна на 0,368.
Къде е този номер? Ще се опитам да обясня идеята за решението. 2 функции се разглеждат. Първо г (т) - вероятността, че кандидатът за тон стъпка би било най-доброто от всички останали кандидати, при условие, че той е по-добре от всички предишните. Второ, функция H (т определя като шанса за спечелване в случай че булката преминава първите Т коняри, и от етап т + 1 действа на оптималната стратегия. Очевидно е, ж функция (т) линейно нараства, и Н (т) . - монотонно намалява предположим, че функциите пресичат в някакъв момент t_0 (не непременно число), след това очевидно оптималната стратегия за принцеса следва: първо прескачане [t_0] (число част) на участниците, и като се излиза от [t_0] един акт на това. стратегия: да изберете първия принцът да бъде по-добре, отколкото всички предишни факти. Matic, всички редуцира до изчисление функция H (Т) Изчисленията показват, че t_0 = п / е (където Е -. база напрежение логаритми и съответно вероятността за спечелване условие повторение оптимална стратегия от тази стъпка - .. 1 / е (материя че з (т) / г (т)

LN (п / т) (и следователно приблизително равни на Н (т) / г (т) = 1 за п / т

Какво ще се промени, ако искаме да спечелим достатъчно, за да могат да си избират най-добрите, но един от pervyk м-най-добре?

Интересен въпрос е споменато в края на книгата, която е малко засегнати. Например, за m = 2 и голяма п (брой Grooms) оптимална стратегия (в което максималната вероятност за получаване на един от двата Х-1-добрите кандидати без значение коя от тях) принцеса е както следва. Напред приблизително 34,7% от участниците в търга, следните приблизително 32% (плътта до 66.7%), за да даде съгласие за брака само за тези, които са най-предишния, а останалите 33,3% от участниците в търга и да се споразумеят за втория качеството сред вече са преминали , В този случай, вероятността за спечелване (ако п -> \ infty) е приблизително равно на 0,574.

> По-п
Защо ми е необходим голям п?

Така например, когато п = 9, m = 2, вероятността за спечелване е възможно да се изчисли приблизително 0.65. Обикновено разтвор (дори и когато m = 1) на предположението, че п е достатъчно голям, като се използва при крайна сума на интеграл се заменя с (така се появява номер д). Т.е. п = 1000 е избрана от тези съображения; всъщност ценности t_0 / N и вероятността за спечелване не се различават от лимита.