algorithm - 如何使用动态规划找到最大概率？

Question

为了更好地理解这个问题，您可以查看:-

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

约翰正在和一个魔术师玩游戏。在这个游戏中，最初有'N'个相同的盒子摆在他面前，其中一个盒子里装着一颗魔法药丸——吃了这颗药丸后，他就长生不老了。

他必须确定哪个盒子里装有药丸。他被允许执行最多“M”个 Action 。在每一步中，他可能会执行以下操作之一:

1)

从他面前均匀分布的箱子中随机选择一个，猜猜这个箱子里装的是药丸。如果猜对了，游戏结束，他得到药丸。否则，在这个猜测之后，魔术师在他面前添加了 K 个空盒子，约翰无法确定添加了哪些盒子；他猜到的那个方 block 也留在了他的面前，他在后续的走法中也分不清这个方 block 和其他的方 block 。

2) 选择一个数字 X，使 X 是 K 的正倍数，但严格小于 John 前面的当前框数。然后魔术师取出 X 个空盒子。当然，如果当前的箱子数量≤K，John 一定不能执行这一步。

如果约翰表现最佳，他得到药丸的最大概率是多少？ “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”是我们问题的答案。

基本上，我们必须确定哪个 Action 序列会产生最大概率？还有，

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) 是 John 最佳发挥的概率。我们有以下递推关系:

• p(N, K, 0) = 0
  • 如果没有剩余的步数，那么他就输了。
• 如果 M> 0 且 N <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 的数组。