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

Rumata

В некотором царстве принцесса решила, что ей пора выходить замуж. Созвали принцев со всего света, и явилось 1000 претендентов. Причем все принцы сравнимы с друг другом - про любых двух можно сказать кто из них лучше; кроме того, отношение "быть лучше" транзитивно. Претенденты входят к принцессе по очереди, по одному. Цель принцессы - выбрать самого лучшего жениха. На каждом шаге она решает, берет ли она данного претендента в мужья или нет. Если берет, то на этом смотр претендентов заканчивается. Если же отвергает, то это решение окончательно (принцы люди гордые и процесс продолжается. Если в конце концов принцесса не получает лучшего, то она проиграла (и уходит в монастырь). Спрашивается, по какой стратегии нужно действовать принцессе, чтобы с наибольшей вероятностью выиграть, т.е. получить самого лучшего принца?
PS Оптимальная стратегия ИМХО может пригодиться на практике. Например, если мы собираемся что-то купить на рынке, где много торговых палаток, расположенных в ряд (и при этом не хотим возвращаться назад).
PPS Говорят, что обобщением этой задачи занимался сам Б.А. Березовский

Forsit

Старье.
Ботаем тервер

antcatt77

> Если в конце концов принцесса не получает лучшего, то она проиграла (и уходит в монастырь
Что значит "лучшего"?
принцесса Самого лучшего принца скорее всего все равно не получит, вероятность 1/1000, при чем даже используя алгоритмы - сильно улучшить этот показатель не получится.

dimaxd

Тока ответ помню (смутно, мб ошибаюсь): надо просмотреть первые n/e (где n -- число претендентов, e=2,7... -- число "е") претендентов, а потом выбрать из последущих первого же жениха, который лучше каждого претендента из первой группы.

Rumata

Да, принцесса должна пропустить первых n/e женихов (т.е. при n=1000 примерно 368 человек только запоминая их для будущего сравнения, а дальше она должна выбрать первого же, который лучше всех своих предшественников.

Smintz

очень похоже на правду
нам это Лагутин на зачёте рассказывал

dimaxd

Ура ;]
Угадал.
Осталось только услышать обоснование сего факта.

dimaxd

А нам, если не ошибаюсь, Булинский на первой же лекции

Rumata

Что значит "лучшего"?

"[...] Причем все принцы сравнимы с друг другом - про любых двух можно сказать кто из них лучше; кроме того, отношение "быть лучше" транзитивно.[...]" (с) Значит, среди принцев есть лучший.
принцесса Самого лучшего принца скорее всего все равно не получит, вероятность 1/1000, при чем даже используя алгоритмы - сильно улучшить этот показатель не получится.

При оптимальной стратегии вероятность выигрыша примерно 0,368, т.е. существенно выше.

Rumata

Вот ссылка на книжку: http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf

dimaxd

Спасибо, почитаю как-нибудь на досуге
ЗЫ-Оффтопик: С.М. Гусейн-Заде у нас читал ангем

stm7543347

PS Оптимальная стратегия ИМХО может пригодиться на практике. Например, если мы собираемся что-то купить на рынке, где много торговых палаток, расположенных в ряд (и при этом не хотим возвращаться назад).
Зря. Палаток всё же меньше тысячи, если не много меньше.

antcatt77

> примерно 0,368
Откуда взялось это число?
368 человек точно пропущены, а при этом еще остается возможность - что выбирешь, например, второго по крутости, а не первого.

Rumata

368 человек точно пропущены, а при этом еще остается возможность - что выбирешь, например, второго по крутости, а не первого.
не вижу противоречия с тем, что вероятность выигрыша равна 0,368.
Откуда взялось это число?
Попробую изложить идею решения. Рассматриваются 2 функции. Во-первых g(t) - вероятность того, что претендент на шаге t окажется лучше всех других претендентов, при условии что он лучше всех предыдущих. Во-вторых, функция h(t определяемая как вероятность выигрыша в том случае, если невеста пропускает первых t женихов, а начиная с шага t+1 действует по оптимальной стратегии. Очевидно, функция g(t) линейная возрастающая, а h(t) - монотонно убывающая. Допустим, что эти функции пересекаются в некоторой точке t_0 (не обязательно целой). Тогда очевидно оптимальная стратегия для принцессы такова: пропустить первых [t_0] (целая часть) претендентов, а начиная с [t_0]+1 действовать по такой стратегии: выбрать первого принца, который будет лучше всех предыдущих. Фактически, все сводится к вычислению функции h(t). Вычисления показывают, что t_0=n/e (где e - основание нат. логарифмов и соответственно вероятность выигрыша при условии следования оптимальной стратегии начиная с этого шага - 1/e. (Дело в том, что h(t)/g(t)~ln(n/t) (приблизительно равно а значит h(t)/g(t)=1 при n/t~e => t_0~n/e). Подробности можно посмотреть в книжке: http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf

antcatt77

Что изменится, если нам для выигрыша достаточно выбрать не самого лучшего, а одного из первык m-лучших?

Rumata

Интересный вопрос В конце упоминавшейся книжки он немного затрагивается. Например, для m=2 и большом n (число женихов) оптимальная стратегия (при которой максимальна вероятность получения одного из 1-х двух лучших претендентов, не важно какого из них) принцессы состоит в следующем. Пропустить приблизительно 34,7% претендентов, из следующих приблизительно 32% (плоть до 66,7%) давать согласие на брак только тому, кто лучше всех предыдущих, а из оставшихся 33,3% претендентов соглашаться и на второго по качеству среди уже прошедших. При этом вероятность выигрыша (при n->\infty) приблизительно равна 0,574.

antcatt77

> большом n
Почему необходимо большое n?

Rumata

Ну например при n=9, m=2 вероятность выигрыша будет как можно посчитать примерно 0,65. Вообще в решении (даже при m=1) предположение о том, что n достаточно велико, используется например при замене конечной суммы на интеграл (так появляется число e). Т.е. n=1000 было выбрано из этих соображений; фактически при этом значения t_0/n и вероятности выигрыша не отличаются от предельных.
Оставить комментарий
Имя или ник:
Комментарий: