Как найти максимальную вероятность при использовании динамического программирования?

Question

Для лучшего понимания этого вопроса вы можете проверить: -

1) https://math.stackexchange.com/questions/3100336/how-to-calculate-the-probability-in-this-case

Джон играет в игру против мага. В этой игре изначально естьN 'идентичных коробок перед ним, и одна из них содержит волшебную таблетку - после употребления этой таблетки он становится бессмертным.

Он должен определить, в какой коробке находится таблетка.Ему разрешено выполнять не более «М» ходов.На каждом ходу он может выполнить одно из следующих действий:

1)

Выберите один из прямоугольников, которые перед ним равномерно случайным образом, и предположите, что в этом блоке находится таблетка.Если предположение верно, игра заканчивается, и он получает таблетку.В противном случае, после этого предположения, маг добавляет K пустых коробок перед собой таким образом, что Джон не может определить, какие коробки были добавлены;коробка, которую он угадал, также остается перед ним, и он также не может отличить эту коробку от других коробок в последующих ходах.

2) Выберите число X, такое, что X является положительным кратным K, но строго меньшечем текущее количество ящиков перед Джоном.Затем маг удаляет X пустых коробок.Конечно, Джон не должен выполнять этот ход, если текущее количество боксов ≤K.

Если Джон играет оптимально, какова будет максимальная вероятность того, что он получит таблетку?«N» всегда меньше, чем «K».

Пример: - Пусть M = 3, поэтому разрешено 3 хода.K = 20, N = 3.

В своем первом движении Джон выбирает ящик с вероятностью, x = 1/3, (было добавлено 20 коробок (20 + 3 == 23), затем во второмдвигаться, он снова выбирает коробку снова, с вероятностью на этот раз, y = 1/23 * (2/3). Здесь, 2/3 обозначает вероятность неудачи в первом движении.

В третьемдвигаться, он делает то же самое с вероятностью, z = 1/43 * (22/23) * (2/3).

Таким образом, общая вероятность = x + y + z = l1

Допустим, в приведенном выше случае во втором ходу он решает убрать 20 ящиков и больше ничего не делать, тогда новая окончательная вероятность равна = 1/3 + 0 (ничего не делается во втором ходу!) + 2/ 3 * (1/3) = l2. Теперь, когда l2> l1, поэтому 'l2' является ответом на наш вопрос.

По сути, мы должны определить, какая последовательность ходов даст максимальную вероятностьКроме того,

P (победа) = P (игра заканчивается на 1-м ходу) + P (игра заканчивается на 2-м ходу) + P (игра заканчивается на 3-м ходу) = (1/3) +0+ (2/3) * (1/3) = 5/9

Учитывая, N, K, M, как мы можем узнать максимальную вероятность?Нужно ли применять динамическое программирование?

Answer 1

Пусть p ( N , K , M ) будет вероятностью Джона, если он будет играть оптимально.У нас есть следующие рекуррентные отношения:

• p ( N , K , 0) = 0
  • Если оставшихся ходов нет, он проигрывает.
• , если M > 0 и N <<em> X ,затем p ( N , K , M ) = ¹ / _N + ^{( N -1)} / _N · p ( N + K , K , M −1)
  • Если есть хотя бы один оставшийся ход, а опция # 2 неЕсли его разрешить, то вероятность его выигрыша равна вероятности того, что он правильно угадал в этом раунде, плюс вероятность того, что он угадал неправильно в этом раунде , но он выиграет в следующем ходу.
• если M > 0 и N ≥ X , то p ( N , K , M ) является наибольшим из этих двух:
  • ¹ / _N + ^{( N -1)} / _N · p ( N + K , K , M -1)
    • Если он выберет вариант № 1, то это то же самое, что и случай, когда онбыл вынужден принять опцию №1.
  • p ( N % K , K , M -1), где «%» - оператор «остатка» или «модуля»
    • Если он выберет вариант № 2, то он, безусловно, не выиграет на этом этапетаким образом, его вероятность выигрыша равна вероятности того, что он выиграет в более позднем ходу.
    • Обратите внимание, что нам нужно учитывать только N % K , потому что онбезусловно, следует выбрать наибольшее значение X , которое ему разрешено.Никогда нет смысла позволять пулу блоков оставаться излишне большим.

Динамическое программирование, или рекурсия плюс запоминание, хорошо подходит для этого;Вы можете применить вышеупомянутые рекуррентные отношения напрямую.

Обратите внимание, что K никогда не изменяется, поэтому вам не нужно измерение массива для него;и N изменяется только путем сложения или вычитания целых кратных K , поэтому лучше использовать индексы массива n , такие как N = ( N ₀ % K ) + nK .

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