2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Задача о разборчивой невесте
Сообщение18.12.2018, 10:18 


18/12/18
2
Помогите понять условие этой задачи. Я вот никак не могу, мне кажется, есть противоречие. Итак, она должна отбросить первые 37% женихов, а потом выбрать первого такого, который будет лучше любого из предыдущих.
Но!
Вдруг среди тех 37% уже был самый лучший жених? Ведь они выбираются случайным образом? И тогда, получается, она просто не найдет среди оставшихся такого, который был бы лучше!

В чем я не права?

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

    В 1963 году академик РАН Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

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

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение18.12.2018, 10:32 


21/05/16
4292
Аделаида
Alise в сообщении #1362117 писал(а):
В чем я не права?

Вы правы. Она не всегда будет выбирать лучшего жениха. Но вероятность выбрать его самая высокая.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение18.12.2018, 10:43 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Alise в сообщении #1362117 писал(а):
Помогите понять условие этой задачи.
Да, Вы не поняли условие. Цель невесты в этой задаче только одна -- выбрать самого лучшего жениха. По описанной стратегии ей это удастся с ~37% вероятностью. В остальных случаях она либо останется старой девой (если лучший был среди первых перебранных), либо выйдет таки за кого-то и будет всю жизнь жалеть, если потом узнает, что он не был лучшим.

 Профиль  
                  
 
 Posted automatically
Сообщение18.12.2018, 11:11 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- для лучшего понимания стоило бы привести условие задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение18.12.2018, 11:52 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение18.12.2018, 12:55 


05/09/16
11468
Да, интересная задачка.
Изображение
Горизонтальная ось -- сколько процентов женихов пропустит (откажет, но запомнит рейтинг лучшего из них).
Вертикальная ось -- вероятность.
Красный -- останется без жениха.
Желтый -- выйдет замуж, но не за лучшего.
Зеленый - выберет лучшего.

Моделировалось на 100 женихах в наборе, 100 000 случайных наборов по каждому проценту первоначального отсева (т.е. всего 10 млн. наборов). Рейтинги в наборе от 1 до 100 (т.е. без повторов).

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 03:31 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Хм. А если максимизировать не вероятность выбрать самого лучшего, а матожидание рейтинга выбранного жениха? Стратегия измениться или нет?

То есть я хочу, чтобы за миллион попыток выбора из ста женихов средний рейтинг женихов был максимальный. При этом не против, что Ален Делон будет попадаться реже, чем в 37% случаях.

А ещё можно попытаться минимизировать вероятность выбора жениха не из, скажем, топ-10.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 08:27 


05/09/16
11468
Legioner93 в сообщении #1362341 писал(а):
Хм. А если максимизировать не вероятность выбрать самого лучшего, а матожидание рейтинга выбранного жениха? Стратегия измениться или нет?

Очевидно, стратегия будет зависеть от распределения рейтингов женихов (которое к тому же должно быть известно невесте для формирования правильной стратегии).

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 11:35 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Цитата:
Очевидно, стратегия будет зависеть от распределения рейтингов женихов (которое к тому же должно быть известно невесте для формирования правильной стратегии).


Никакого распределения рейтингов нет. Сами рейтинги присутствуют в условии задачи.

Alise в сообщении #1362117 писал(а):
О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.


То есть женихи вполне упорядочены, вот он и рейтинг.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 12:01 


05/09/16
11468
Legioner93 в сообщении #1362385 писал(а):
Никакого распределения рейтингов нет. Сами рейтинги присутствуют в условии задачи.

Тогда не получится ничего сделать с матожиданием.
Legioner93 в сообщении #1362385 писал(а):
То есть женихи вполне упорядочены, вот он и рейтинг.

Например, рейтинги у группы женихов идут от 1 до 99, а лучшего жениха рейтинг 1 000 000.
Или наоборот, рейтинги идут от 999 901 до 1 000 000.
Будут, очевидно, разные стратегии по максимизации матожидания рейтинга, не так ли? Хотя всё и упорядочено.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 12:24 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Невеста может, как и раньше, считать, что все женихи упорядочены по отношению "лучше -- хуже". И только внешний наблюдатель знает, как пронумерованы все 100 женихов в порядке возрастания (этот номер и будем считать рейтингом). Вопрос со стратегией достижения оптимального мат.ожидания выглядит интереснее, чем оригинальная задача, имхо.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 12:35 


05/09/16
11468
grizzly
Ну то есть рейтинги распределены равномерно по отрезку, но центр отрезка в произвольном месте.
Ещё нужно понять что делать с неудачными испытаниями, когда выйти замуж не удалось: присвоить какой-то рейтинг надо б. Например нулевой. От этого тоже будет зависеть, если рейтинг невыхода замуж намного меньше рейтинга самого плохого жениха то очевидным выглядит стратегия выйти за первого встречного...

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 12:44 
Заслуженный участник
Аватара пользователя


09/09/14
6328
wrest в сообщении #1362403 писал(а):
Например нулевой.
Да, такой выбор выглядит логично.
wrest в сообщении #1362403 писал(а):
если рейтинг невыхода замуж намного меньше рейтинга самого плохого жениха то очевидным выглядит стратегия выйти за первого встречного...
Вы имели в виду "за последнего встречного"? :D Или я не понял. То есть, даже в этом случае можно рисковать до самого последнего и следить за мат.ожиданием для выбранной стратегии.

-- 19.12.2018, 12:47 --

wrest в сообщении #1362403 писал(а):
но центр отрезка в произвольном месте.
И здесь не совсем понял. Есть 100 женихов. Их порядок в равномерном рейтинге известен всем, кроме невесты.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 13:33 


05/09/16
11468
В общем, если случай невыбора жениха считаем случаем выбора жениха с рейтингом ноль, выбираем из 100 женихов с рейтингами от 1 до 100, то матожидание максимально если пропустить 6 или 7 женихов, а потом выйти за лучшего из предыдущих. Тогда средний рейтинг будет около 87,7

Если считать только случаи когда жених найден и пропускать когда не найден, то надо пропустить 99 и выйти за последнего (если он окажется лучшим чем все предыдущие, конечно) :mrgreen: ну это очевидный случай, так мы гарантируем выход за лучшего.

Теперь допустим что рейтинг невыхода замуж отрицательный и мы это учитываем. Тогда, по мере увеличения "штрафа" надо продвигаться к началу очереди. При штрафе в 50 (рейтинг невыхода замуж равен -50) надо пропустить уже не 6 или 7, а 5. При штрафе в 100, пропустить надо 4. При штрафе 1000, пропустить надо одного. Начиная где-то с 2500, пропускать не надо, выходить надо за первого (тогда средний рейтинг будет 50 с чем-то).

Предположим что рейтинг невыхода замуж положительный. При премии в 25, пропускать надо 7 или 8. При премии 75, пропускать надо 12. При премии 100, пропускать надо 99, а при премии 101 и больше -- ясное дело, пропускать надо всех, замуж не выходить и получить 101 или больше.

-- 19.12.2018, 13:34 --

grizzly в сообщении #1362406 писал(а):
Вы имели в виду "за последнего встречного"? :D Или я не понял.

Ну я проверяю только стратегии "пропустить $n$, затем выйти за лучшего из предыдущих"

-- 19.12.2018, 13:41 --

grizzly в сообщении #1362406 писал(а):
То есть, даже в этом случае можно рисковать до самого последнего и следить за мат.ожиданием для выбранной стратегии.

Если невесте известно только то, что рейтинги женихов упорядочены, и больше ничего, то никакого матожидания невеста вычислять не может. Ей же сообщают только "этот лучше всех предыдущих", "этот не лучше предыдущих", и всё. Какое тут матожидание?

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.12.2018, 13:45 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
wrest в сообщении #1362423 писал(а):
Теперь допустим что рейтинг невыхода замуж отрицательный и мы это учитываем.
Невеста легко избавится от сколь угодно большого штрафа, просто выйдя за последнего :)
Это я к тому, что различных стратегий вообще-то великое множество, они не сводятся к "Пропустить N и выйти за следующего, чей рейтинг больше".

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group