среда, 19 февраля 2020
12:11

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

все записи пользователя в сообществе asde21as1
Как найти и посчитать количество случаев, когда невеста никого не выбирает, выбирает первого по качеству и т.д., при условии, что невеста выбирает из 5-ти претендентов и согласна на первого и второго по качеству?
Всего 120 вариантов. Но как посчитать, не перебирая все?

@темы: Линейное программирование

URL
Комментарии
19.02.2020 в 14:55

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, а почему запись была закрытой?... это не по правилам сообщества...
URL
19.02.2020 в 14:58

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Если речь о классической постановке такой задачи, то непонятно что такое 120 вариантов... :upset:
URL
19.02.2020 в 18:05

asde21as1
All_ex, 5!=120
Если рассмотреть все возможные случаи.
Например, если первый по качеству будет первый, второй -вторым... 12345
Если пятый по качеству будет первым, четвертый - вторым..... 54321
И так 120 раз. И из них надо без перебора посчитать, сколько случаев, когда невеста никого не выберет, выберет первого по качеству, второго, третьего, четвертого и пятого.
URL
19.02.2020 в 21:46

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, сперва надо определиться со стратегией выбора... а потом уже говорить о вариантах и вероятностях...
Например, если она решила хватать первого встречного, то понятно, что выберет обязательно, и у всех претендентов равные шансы...
Если второго встречного, то... и так далее...
URL
20.02.2020 в 19:23

asde21as1
All_ex, первого всегда пропускает, со второго шага выбирает лучшего, с третьего согласна на второго по качеству.
URL
20.02.2020 в 19:32

asde21as1
All_ex, Невеста выигрывает, когда выбирает либо первого, либо второго по качеству.
t 1 2 3 4 5
g(1) 2/5 7/10 9/10 1 1
g(2) 0 1/10 3/10 3/5 1
h(t) 7/10 7/10 3/5 2/5 0
URL
20.02.2020 в 19:37

asde21as1
All_ex,
n=4:
0 1 2 3 4
m=1 6 11 5 2 0
(6 раз никого не выберет, 11 раз выберет первого, 5 раз второго, два раза третьего, ни разу четвертого)
m=2 2 10 8 4 0
m=3 1 10 8 5 0
URL
20.02.2020 в 19:38

asde21as1
All_ex,
например, в последовательности 1 2 3 4 5 - никого не выбирает
5 4 3 2 1 выбирает четвертого
URL
20.02.2020 в 19:48

asde21as1
All_ex, * первого всегда пропускает, со второго шага выбирает лучшего, с четвертого согласна на второго по качеству.
URL
21.02.2020 в 01:58

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, * первого всегда пропускает, со второго шага выбирает лучшего, с четвертого согласна на второго по качеству.
странная у Вас стратегия... :upset:
а как она может различить первого или второго?... :upset: :upset:
URL
21.02.2020 в 09:37

asde21as1
All_ex, она различает только t, т.е. Шаг, какой он по счету и его качество, т.е. Хуже или лучше он предыдущего. Первый претендент - обучающая выборка всегда.
Вот еще для примера последовательность
35421 невеста выберет 4, т.к. Он лучше 5, но проиграет

35214 выберет второго и выиграет.
Получится ли мне подсказать в ближайшем времени, как все таки их посчитать - кол-во вариантов, кого она выберет из 120
URL
21.02.2020 в 16:37

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
я так и не понял до конца правило остановки алгоритма...
например, она согласна на "второго", но как она его может идентифицировать как "второго"?... только когда он последний в очереди, а "первый" был в обучающей выборке...

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

обучающая = "1" : либо никого не выберет, либо "2" (при условии, что он последний)... итого, "2" - 6 вариантов, никого - 18 вариантов...
обучающая = "2" : всегда выберет "1" - 24 варианта...
обучающая = "3" : выберет либо "1", либо "2" - по 12 вариантов...
обучающая = "4" : выберет "1", "2", или "3" с равными шансами (если "х" стоит первый в очереди или очередь начинается с "5 + х" ) - по 8 вариантов...
обучающая = "5" : выбирает любого с "1" по "4" с равными шансами, в зависимости от того, кто стоит первым в очереди... по 8 вариантов...

итого, у меня получилось (если не обсчитался):
"никого" = 18 вариантов
"5" - 0 вариантов
"4" - 6 вариантов
"3" - 14 вариантов
"2" - 32 вариантов
"1" - 50 вариантов
URL
21.02.2020 в 18:04

asde21as1
All_ex, я так и не понял до конца правило остановки алгоритма...
например, она согласна на "второго", но как она его может идентифицировать как "второго"?... только когда он последний в очереди, а "первый" был в обучающей выборке...
уточню, вдруг это влияет на кол-во вариантов.
1 5 4 3 2 - первый в обучающей выборке, "второй"- последний. Согласно оптимальной стратегии она первого пропускает, со второго берет лучшего из тех, кто был, с четвертого согласна на второго по качеству из тех, кто был, то есть
1 - пропускает
1 5 - пятый хуже первого не согласна
1 5 4 - четвертый хуже первого, но лучше пятого, а это 3-ий шаг, поэтому она еще не согласна
1 5 4 3 - третий - это из пройденных второй по качеству, на него-то она и согласна, но не выигрывает при этом.
и в этом случае мы считаем, что она выбрала третьего

Что касается предложения посмотреть, кто попал в обучающую выборку, я не до конца понял, как все так ловко посчитали.
обучающая = "1" : либо никого не выберет, либо "2" (при условии, что он последний)... итого, "2" - 6 вариантов, никого - 18 вариантов...
можно чуть подробнее хотя бы первый случай объяснить?
URL
21.02.2020 в 22:46

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, 1 5 4 3 - третий - это из пройденных второй по качеству, на него-то она и согласна, но не выигрывает при этом.
ах, во оно как... тогда ответ будет отличаться от моего... как я понимаю отличия будут в пунктах обучающая = "1" и обучающая = "2" ...

я не до конца понял, как все так ловко посчитали.
вроде всё расписано... просто комбинаторно считаете варианты выбора...
URL
23.02.2020 в 21:26

asde21as1
All_ex,
обучающая = "1" либо никого не выберет (6), либо второго, если он последний (6), либо второго, если она на четвертом (6), либо 3-его на четвертом месте (6);
обучающая = "2" : всегда выберет первого (18) и если на четвертом месте 3 (6)
обучающая = "3" : выберет либо "1", либо "2" - по 12 вариантов...
обучающая = "4" : выберет "1", "2", или "3" с равными шансами (если "х" стоит первый в очереди или очередь начинается с "5 + х" ) - по 8 вариантов...
обучающая = "5" : выбирает любого с "1" по "4" с равными шансами, в зависимости от того, кто стоит первым в очереди... по 8 вариантов...

"никого" = 6 вариантов
"5" - 0 вариантов
"4" - 6 вариантов
"3" - 26 вариантов
"2" - 38 вариантов
"1" - 44 вариантов

Вот так получается?
URL
25.02.2020 в 00:49

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
обучающая = "1" либо никого не выберет (6), либо второго, если он последний (6), либо второго, если она на четвертом (6), либо 3-его на четвертом месте (6);
неверно...
либо 3-его на четвертом месте (6) - здесь всего два варианта, поскольку выбор будет сделан только если 2 окажется последним...
либо второго, если он последний (6) - при этом третий не должен быть на четвёртом месте... число вариантов будет другим

обучающая = "2" : всегда выберет первого (18) и если на четвертом месте 3 (6)
тут тоже не верно указано число вариантов... если на четвертом месте 3 (6) - опять же первый должен оказаться на последнем месте...
URL
03.03.2020 в 01:51

asde21as1
All_ex, обучающая = "1" либо никого не выберет (12), либо второго, если он последний, при этом третий не должен быть на четвёртом месте (4), либо второго, если она на четвертом (6), либо 3-его на четвертом месте, только если 2 окажется последним (2);
обучающая = "2" : в выберет первого (18) и если на четвертом месте 3, а первый на последнем (2), никого не выберет, если 1 на последнем (4)
обучающая = "3" : выберет либо "1", либо "2" - по 12 вариантов...
обучающая = "4" : выберет "1", "2", или "3" с равными шансами (если "х" стоит первый в очереди или очередь начинается с "5 + х" ) - по 8 вариантов...
обучающая = "5" : выбирает любого с "1" по "4" с равными шансами, в зависимости от того, кто стоит первым в очереди... по 6 вариантов...

"никого" = вариантов 12+4=16
"5" - 0 вариантов
"4" - вариантов 8
"3" - вариантов 2+8+6=16
"2" - вариантов 4+6+12+8+6=36
"1" - вариантов 18+12+8+6=44
URL
03.03.2020 в 09:45

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, обучающая = "2" : в выберет первого (18) и если на четвертом месте 3, а первый на последнем (2), никого не выберет, если 1 на последнем (4)
не понял про "никого"... вроде если "3" стоит не четвёртым, а "1" последним, то выберут "1"... :upset:
URL
03.03.2020 в 11:17

asde21as1
All_ex, так поэтому только 4 варианта
URL
03.03.2020 в 11:30

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
asde21as1, обучающая = "2" :
в этом случае "никого" - 0 вариантов...
тут либо "3", либо "1"...
URL
03.03.2020 в 11:36

asde21as1
All_ex, тогда 1 (22) варианта, а 3 (2)?
URL
03.03.2020 в 11:48

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
думаю, да...
URL
03.03.2020 в 13:57

asde21as1
All_ex, Спасибо за помощь!
URL
03.03.2020 в 15:33

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
welcome...
URL