Ken*_*nny 6 algorithm statistics optimization probability dynamic-programming
假设我正在玩10种不同的游戏.对于每个游戏,我都知道获胜的概率,搭售的概率和失败的概率(每个游戏都有不同的概率).
从这些值,我可以计算赢得X游戏的概率,丢失X游戏的概率,以及绑定X游戏的概率(X = 0到10).
我只想弄清楚赢得W游戏,打T游戏以及在玩了所有10场比赛后失去L游戏的概率......并且希望比O(3 ^ n)更好.例如,获胜7,失去2和搭售1的概率是多少？
有任何想法吗？谢谢!
编辑 - 这里是一些示例数据,如果只有2个游戏:
第1场比赛:
第2场比赛:
基于此,我们可以计算出2场比赛后的概率:
根据这些数字,是否有一个通用的公式来找出W胜利,T领带和L损失的概率？可能的结果(WLT)将是:
这可以通过动态编程来完成，我不确定是否有更好的方法，因为游戏是独立的。
\n\n有一个 4 维数组，包含胜利、失败、平局和比赛。您可以将胜利/失败/平局限制为您想要的数量（令它们为W，L，T，W+L+T=G），时间复杂度将为O(W*L*T*G)，这是有界的通过 O(G\xe2\x81\xb4)。
\n\n该算法基本上是：
\n\nA[][][][] = new double[G+1][W][T][L]\n// A[g][w][t][l] is the probability of have w wins, t ties, l losses\n// after g games. This can be computed from A[g-1].\n// Let P[g][o] be the probability of outcome o for game g\n//everything else is initially 0.\nA[0][0][0][0] = 1\nfor g=1..G\n for w=0..W\n for t=0..T\n for l=0..L\n A[g][w][t][l] = A[g-1][w-1][t][l]*P[g][win] // assume out of bounds\n +A[g-1][w][t-1][l]*P[g][tie] // reference returns 0\n +A[g-1][w][t][l-1]*P[g][lose]\nreturn A[G][W][T][L]\n编辑）
\n\n我们可以在 O(W*L*T*G/max(W,L,T)) 中完成此操作，即 O(G\xc2\xb3)。请注意，如果在 G 场比赛后我们有 W 场胜利和 T 场平局，那么我们必须有 L 场损失。
\n\n// we should pick the conditions we loop to be the smallest two.\n// here we just use wins and ties.\nA[][][][] = new double[G+1][W][T]\nA[0][0][0] = 1\nfor g=1..G\n for w=0..W\n for t=0..T\n A[g][w][t] = A[g-1][w-1][t]*P[g][win] // assume out of bounds\n +A[g-1][w][t-1]*P[g][tie] // reference returns 0\n +A[g-1][w][t]*P[g][lose]\nreturn A[G][W][T]\n也许可以通过分别计算 x 胜/平/负的概率 (O(G))，然后智能地添加/减去它们来更快地完成此操作，但我还没有找到一种方法来做到这一点。
\n