задача о невесте. Семинары_Решение_задачи_о_невесте. Семинаров Решение задачи о невесте Рассмотрим задачу выбора одного из двух лучших женихов из 4 претендентов
 Скачать 102.52 Kb.
|
|
Задачи для семинаров Решение задачи о невесте Рассмотрим задачу выбора одного из двух лучших женихов из 4 претендентов. Пусть g t (k) — это вероятность выиграть, если невеста на шаге t берем претендента с рангом k (среди первых t претендентов), а h t — это вероятность выиграть, если невеста пропускает претендента под номером t. Заметим, что вероятность h t по определению не зависит от ранга k претендента, которого мы пропускаем. Воспользуемся формулами для определения вероятностей g t (k) и h t : g t (k) = k t + 1 g t+1 (k + 1) + t + 1 − k t + 1 g t+1 (k); (1) h t = 1 t + 1 m X k=1 max(g t+1 (k), h t+1 ) + t + 1 − m t + 1 h t+1 (2) В нашем случае число претендентов n = 4, наибольший ранг «устраивающего» неве- сту претендента m = 2. Заметим, что g t (t) = 0 при всех t, если k > m. Это означает, что у невесты нет шансов выиграть, если она берет претендента, который уже сейчас ее не устраивает (приход новых претендентов не увеличивает ранг выбранного). Поэтому в таблице будем рассчитывать вероятности g t (k) только при k 6 m. Начнем расчет вероятностей с конца. 1) Для t=4 имеем: g 4 (1) = g 4 (2) = 1, g 4 (3) = g 4 (4) = 0, h 4 = 0. Занесем результаты в таблицу. t 4 3 2 1 g t (1) 1 g t (2) 1 h t 0 2) Перейдем к шагу t = 3. Имеем: g 3 (1) = 1 (каким бы ни был четвертый претендент, пре- тендент, бывший на третьем шаге лучших останется выигрышным). Рассчитаем g 3 (2). По определению это вероятность выиграть, взяв на третьем шаге второго претенден- та. Он останется выигрышным после четвертого шага, если четвертый претендент будет третьим или четвертым из четырех. Напротив, выбранный претендент будет проигрышным, если четвертый претендент будет первым или вторым из четырех. Поэтому g 3 (2) = 1 2 . Получим тот же результат по формуле (1): g 3 (2) = 2 4 g 4 (3) + 2 4 g 4 (2) = 2 4 ∗ 0 + 2 4 ∗ 1 = 1 2 Занесем результаты в таблицу. t 4 3 2 1 g t (1) 1 1 g t (2) 1 1 2 h t 0 3) Аналогично, при t = 2 имеем: g 2 (1) = 1 3 g 3 (2) + 2 3 g 3 (1) = 1 3 ∗ 1 2 + 2 3 ∗ 1 = 5 6 g 2 (2) = 2 3 g 3 (3) + 1 3 g 3 (2) = 2 3 ∗ 0 + 1 3 ∗ 1 2 = 1 6 При t = 1 имеем g 1 (1) = 1 2 g 2 (2) + 1 2 g 2 (1) = 1 2 ∗ 5 6 + 1 2 ∗ 1 6 = 1 2 Заметим, что g 1 (2) = 0 (это невозможное событие). Заметим, что, например, g 1 (1) можно было найти и из простых соображений: взяв первого претендента мы выигра- ем, если он первый или второй, и проиграем, если он третий или четвертый. Поэтому вероятность выигрыша g 1 (1) = 2 4 = 1 2 Занесем результаты в таблицу. t 4 3 2 1 g t (1) 1 1 5 6 1 2 g t (2) 1 1 2 1 6 0 h t 0 4) Перейдем к расчету h t h 3 = 1 4 2 X k=1 max(g 4 (k), h 4 ) + 2 4 h 4 = 1 4 {max(g 4 (1), h 4 ) + max(g 4 (2), h 4 )} + 1 2 h 4 = = 1 4 {max(1, 0) + max(1, 0)} + 1 2 ∗ 0 = 1 2 Аналогично для h 2 и h 1 имеем: h 2 = 1 3 {max(g 3 (1), h 3 ) + max(g 3 (2), h 3 )}+ 1 3 h 3 = 1 3 max(1, 1 2 ) + max( 1 2 , 1 2 ) + 1 3 ∗ 1 2 = 2 3 ; h 1 = 1 2 max( 5 6 , 2 3 ) + max( 1 6 , 2 3 ) + 0 = 3 4 Занесем результаты в таблицу: t 4 3 2 1 g t (1) 1 1 5 6 1 2 g t (2) 1 1 2 1 6 0 h t 0 1 2 2 3 3 4 Теперь мы можем перейти к нахождению стратегии действия невесты. Для этого будем сравнивать в каждый момент времени g t (k) и h t Получаем, что начиная с шага t = 2 невесте следует выбирать лучшего претендента, а начиная с шага t = 3 — соглашаться и на второго по качеству. Заметим также, что в этой задаче есть еще одна оптимальная стратегия: т.к. g 3 (2) = h 3 невеста может выбирать второго претендента, начиная только с четвертого шага. |