Ещё задачка к пятнице... мы пока к решению не пришли...

← →
VictorT © (2004-04-23 15:24) [0]

Задача про разборчивую принцессу

Некая привередливая принцесса долго не могла выбрать себе жениха. Наконец папино терпение лопнуло, и он сказал: "Сегодня же пойдёшь под венец!"

Выбор происходит так. На зов короля съехалось ровно N женихов. Женихи выстроились в очередь, по одному предстают перед принцессой, изливают ей душу и демонстрируют свои рыцарские качества и достоинства. После чего немедленно требуют ответа. Получив отказ, оскорблённый жених выбегает из дворца, вскакивает на коня и мчится прочь, так что вернуться к уже рассмотренной кандидатуре у принцессы нет возможности. Если отвергнуты все, то принцесса автоматически выходит замуж за последнего.

Предположим, что принцесса некоторым образом выставляет кандидатам оценку, причём неограниченную сверху, т.е. каким бы хорошим ни был претендент, есть шанс, что найдётся ещё лучше. Цель принцессы - выбрать самого лучшего. Известно только число женихов, про их оценки неизвестно ничего.

Самая простая тактика - выбрать первого попавшегося, с вероятностью 1/N он окажется лучшим. К сожалению, с ростом числа N эта вероятность стремится к нулю.

Вопрос: существует ли лучшая тактика, дающая вероятность, скажем, хотя бы 10% при любом N?

http://deep.webm.ru/forum/reply.php?num=4.1&id=98426

← →
Dmitriy O. © (2004-04-23 15:51) [1]

Методом статистического выборочного анализа.
См "Статистический приемочный контроль по альтернативному признаку"
"Планы статистического приемочного контроля"
Есть методика как на основе определенной статистически достоверной выборки оценить всю партию.
Т.е. имеем партию женихов на основе берем случайную выборку женихов на основании ее оцениваем "Качество" всей партии.
Потом нам остается дождаться жениха который превышает (тут есть небольшой риск) или равняется этому качеству.
Соответственно по закону распределения можно составить таблицу риска т.е. уровень превышения качества партии и вероятность обнаружения такого жениха. Я думаю что нужно взять качество партии+3 сигмы. Тогда мы получим вполне достойного жениха с вероятностью с 99.5 %

← →
pasha_golub © (2004-04-23 15:54) [2]

Dmitriy O. © (23.04.04 15:51) [1]
Ого, во второй раз.

← →
Vit@ly © (2004-04-23 16:01) [3]

> Dmitriy O. © (23.04.04 15:51) [1]
Основная (главная) сложность в определении 3-х сигм. Поскольку (как мне представляется) характеристики женихов не всегда (и зачастую) не являются количественными, и в этом случае необходимо применять непараметрические критерии оценки. А в остальном поностью согласен.

← →
Dmitriy O. © (2004-04-23 16:06) [4]

> Vit@ly © (23.04.04 16:01)
Согласен хотя в условии сказанно:

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

← →
Vit@ly © (2004-04-23 16:11) [5]

> Dmitriy O. © (23.04.04 16:06) [4]
Если условие задачи понимать так, то почти убедил и сдамся

← →
Vit@ly © (2004-04-23 16:24) [6]

Смущает

> После чего немедленно требуют ответа. Получив отказ, оскорблённый
> жених выбегает из дворца, вскакивает на коня и мчится прочь,
> так что вернуться к уже рассмотренной кандидатуре у принцессы
> нет возможности.

и соответсвенно выбор стратегии :(
В такой ситуации, на мой взгляд важен и порядок представления женихов, о котором в постановке задачи я к сожалению ничего для себя не заметил (возможно я и не прав, или автор поста не дословно представил задачу - в чем я сильно для себя сомневаюсь)

← →
Dmitriy O. © (2004-04-23 16:33) [7]

> Vit@ly © (23.04.04 16:24)
То что он (жених) убегает нет ни чего страшного. Кстати такой метод отценки и был разработан имеено для разрушабших методов контроля. Скажем для оценки партии снарядов. Т.е. обьект испытывался и выкидывался (жених уезжает).
Вощем все это разработанно давным давно а применнено американцами еще в 40 годах . Именно они составили так называемые "оперативные планы приема".

← →
Фикус © (2004-04-23 16:37) [8]

Dmitriy O. ©, а ты еще тот жук :)))

← →
Матлабист (2004-04-23 17:24) [9]

Если можно, математический вывод вероятности... К тому же в условии говориться не о достойном кандидате, а о лучшем... Да, и никаких предположений о равномерности распределения оценки делать не следует --- достаточно знать, что из двух женихов один предпочтительнее и это свойство транзитивно

← →
Матлабист (2004-04-23 17:28) [10]

равномерности = нормальности

← →
Матлабист (2004-04-23 18:45) [11]

Да, еще... Рассуждения Dmitriy O. становятся в корне неверными, если учесть, что оценка N-го кандидата может зависеть от оценок предшествующих кандидатов. Например, если принцесса руководствуется таким правилом:
Оценка первого кандидата = 1.
Если кандидат наилучший среди просмотренных ранне, то его оценка равна оценке прошлого наилучшего кандидата + 1
Если кандидат наихудший, то его оценка равна оценке прошлого наихудшего кандидата, деленной на два
Если новый кандидат попадает между i-м и (i+1)-м кандидатом, то его оценка равна среднему арифметическому оценок i-го и (i+1)-го кандидатов.

Я молчу про то, что в случае 20-ти женихов если в качестве выборки выбрать десять первых (что уже мало), то вероятность того, что наилучший находится в первой половине уже 50%. Там что число 99.5% взято просто от потолка ;)

← →
VictorT © (2004-04-29 12:02) [12]

Ну и? Есть ещё мысли? Рассуждения Дмитрия О. меня не убедили, слишшком туманны... А на дремучих вообще сьехал, когда начал задавать конкретные вопросы...

Из асечного разговора... мож кого натолкнёт на какие-то мысли...

VictorT 27.04.2004 14:17 Задача про разборчивую принцессу Некая привередливая принцесса........................... KnightWill 27.04.2004 14:21 :-))))))) VictorT 27.04.2004 14:21 а решить? KnightWill 27.04.2004 14:37 интересно... я в размышлениях :-) KnightWill 27.04.2004 14:44 м-да... в жизни проще, чем в этой задаче :-) VictorT 27.04.2004 14:44 :))) KnightWill 27.04.2004 15:37 если без формул, то можно тактику предложить такую: сперва принцесса принимает партию женихов в числе M=kN (k<1). всем им даёт отказ, но при этом каждому выставляет оценку Ai (i=1,...,M). На основе этого набора данных можно вычислить среднюю оценку <A> , а так же максимальную из данной выборки: Amax(1,M). Реально жениха ей придётся выбирать из оставшихся N-M=(1-k)N, руководствуясь значениями <A>, Amax(1,M).... При таком подходе вероятность точно не будет стремиться к нулю при бесконечном увеличении N, но тут уже надо писать формулы... :-)) VictorT 27.04.2004 15:38 ну что- то вроде мысли... но окончательного логического завершения в формулах нет... VictorT 27.04.2004 15:39 http://deep.webm.ru/forum/reply.php?num=4.1&id=98426 KnightWill 27.04.2004 15:39 мне надо дать конкретные формулы? VictorT 27.04.2004 15:40 ну, наверно... VictorT 27.04.2004 15:41 ну в общем то нужно док-во, что при такой-то тактике вероятность выбора лучшего есть 10% VictorT 27.04.2004 15:42 > Реально жениха ей придётся выбирать из оставшихся N-M=(1-k)N, руководствуясь значениями <A>, Amax(1,M).... к примеру, как именно руководствоваться? VictorT 27.04.2004 15:44 какой коеф-нт k KnightWill 27.04.2004 15:46 во-первых, стоит подсчитать вероятность того, что Amax(1,M)>Amax(M+1,N) (Amax(1,N) - максимальная оценка, то есть идеальный жених) KnightWill 27.04.2004 15:47 коэффициент k придётся оптимизировать :-) на основе каких уравнений - надо думать :-) KnightWill 27.04.2004 15:48 либо Amax(1,N)=Amax(1,M), либо Amax(1,N)=Amax(M+1,N) :-) VictorT 27.04.2004 15:49 P( Amax(1,M)>Amax(M+1,N)) = M/N KnightWill 27.04.2004 15:49 гут :-) VictorT 27.04.2004 15:50 я вот считал, считал, и в результате всё у меня сократилось :) KnightWill 27.04.2004 15:51 и что 10% действительно такое уникальное число? :-) (во что я не очень-то верю) VictorT 27.04.2004 15:51 ну 10% наверно для примера... KnightWill 27.04.2004 15:52 вобщем, я могу ещё подумать над формулами... критерия, действительно пока нет VictorT 27.04.2004 15:52 я так думаю, что для конкретного N есть какая-то конкретная вероятность... KnightWill 27.04.2004 15:52 есть пока только параметры от которых "можно отталкиваться" KnightWill 27.04.2004 16:51 вообще говоря, не факт, что среди оставшихся N-M женихов будут те, оценки которых окажутся выше <A>. То есть вероятность вообще найти "положительного" (с оценкой Ai> <A>, i=M+1,...,N) - 1/2. Может принцессе стоило бы радоваться уже такому случаю? :-)

← →
Vlad Oshin © (2004-04-29 12:25) [13]

Метод испытаний

имеем массив [1..n] of тип_;

цикл_кол-во_ испытаний начать

заполняем массив случайным образом числами, находим среди них МАКСИМУМ, откидываем первых Y<N чисел, запомнив максимум из откинутых. Следующее же число, большее(или равное) из откинутых, ВЫБОР(если такого нет, это испытание уже неудачно, гото 1).
ВЫБОР сравниваем с МАКСИМУМОМ, ведем статистику когда (ВЫБОР=МАКСИМУМ)
1:
цикл_кол-во_ испытаний закончить

вероятность = (кол-во когда ВЫБОР=МАКСИМУМ)/кол-во испытаний

← →
VictorT © (2004-04-29 12:30) [14]

> заполняем массив случайным образом числами, находим среди
> них МАКСИМУМ

Мы не можем это сделать по условиям задачи

← →
Vlad Oshin © (2004-04-29 12:30) [15]

кол-во испытаний положим достаточно большим

← →
Vlad Oshin © (2004-04-29 12:31) [16]

> VictorT © (29.04.04 12:30) [14]

принцесса не может, мы - можем

← →
VictorT © (2004-04-29 12:32) [17]

ой, сорри, протормозил, не понял, что ты вероятность считаешь статистическим методом... та придирка не в счёт

← →
Матлабист (2004-04-29 12:50) [18]

И чему равно при N -> infinity ?

по сути Р(следующее большее за максимальным из X<N = максимальное из N), должно как-то не очень сложно решаться

но я, с 11ого раза теорию вероятности сдавший, в аналитичекских выкладках не вспомню ничего

...забыл даже ту малость латыни, которую не знал (с):)

> Матлабист (29.04.04 12:50) [18]

думаю, N не больше (~6млрд. )/2 :)

ИМХО, при такой постановке задачи ни о какой вероятности речи быть не может. Ее здесь нет.

испытаний 100000

Женихов-, сразу послали-, вероятность
20-,0-,0,05
20-,1-,0,19
20-,2-,0.27
20-,3-,0.32
20-,4-,0.36
20-,5-,0.38
20-,6-,0,4
20-,7-,0,41
20-,8-,0,41
20-,9-,0,4
20-,10-,0,39
20-,11-,0,36
20-,12-,0,34
20-,13-,0,31
20-,14-,0,28
20-,15-,0,24
20-,16-,0,2
20-,17-,0,15
20-,18-,0,1
20-,19-,0,5
20-,20-,0

подозреваю также, что колво женихов не причем
тестил на 50, но писать долго :)
картина стратегии в принципе ясна

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

> 20-,19-,0,5

20-,19-,0,05

> думаю, N не больше (~6млрд. )/2 :)

N не больше (~6млрд. )/2 - 1

ну-ка ее :)

Ещё задачка к пятнице... мы пока к решению не пришли... Найти похожие ветки