В понедельник наткнулся в сети на описание забавной задачи (Гарднера).
"В некотором царствепришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?".
Слегка поразмыслив, я нашел довольно простой алгоритм, который, с одной стороны, позволит найти самого лучшего жениха с достаточно высокой вероятностью, а с другой - в случае неудачи - даст по-прежнему довольно хорошего кандидата.
Поискав решение в инете, я нашел 24-страничную брошюрку (www.mccme.ru/mmmf-lectures/books/books/book.25.pdf) с мощным выводом стратегии. Подглядев в конец, я узнал, что великие ученые мужи обещают найти самого лучшего жениха с вероятностью чуть выше 51%. Кого они смогут предложить в оставшихся 49% случаях не понял.
Заинтересовался. За полчаса набросал генератор входного массива женихов и свой алгоритм. После отладки загнал в цикл (до 100 тысяч итераций), чтобы наверняка получить самые разнообразные последовательности. Проверял на разных выборках - в основном от 128 до 16384.
Итоги таковы - лучший жених находится в примерно в 29% случаев. В среднем, предлагаемые женихи попадают в первую десятку лучших. Выход за лучшие 10% происходит примерно в 1.7% случаев, в нижнюю половину попадаем раз в 10000 случаев.
Сегодня с утреца попробовал покрутить некоторые детали алгоритма - качественно картина не меняется. При изменении объема выборки меняется только разброс второстепенных результатов - чем больше выборка, тем мы ближе к максимуму. Вероятность нахождения лучшего практически не меняется.
Есть желающие сразиться, пока я не стал читать книжку ? Выдаю генератор выборки.
4 comments:
Ну а чего, вроде ж классическая задача о разборчивой невесте.
Типа, просмотреть 1/e часть женихов и выбрать затем первого, кто превысит наиболее хорошего из нее, разве нет?
A.J.
Ага, все верно, только с вероятностью (1-1/е) ты получишь полный отстой. А у меня получилось лучше.
эээ
при большом числе испытаний?
Не понял вопрос.
Уточняю. У меня получился несколько более низкий процент выбора самого лучшего жениха, но при это очень хорошие шансы получить парня "из первой десятки" в случае неудачи основного варианта.
Перекрыть вероятность 1/е, согласен, невозможно.
Post a Comment