算法合集之浅析竞赛中一类数学期望问题的解决方法

1、福建省福州第八中学 汤可因什么是数学期望什么是数学期望如果x是一个离散的随机变量，输出值为 x1, x2, .， 和输出值相应的概率为p1, p2, . （概率和为1）, 那么期望值iiixpxe)(全期望公式全期望公式iiixxyexxpxyeeye)|()()|()(e(y | x = 1)=4e(y | x = 2)=3p(x = 2)=0.4p(x = 1)=0.6e(y)=0.43 + 0.64 = 3.6一、利用递推或动态规划解决二、建立线性方程组解决 模型 例题：first knight 例题：mario给出一张有向图g = (v, e)。顶点i的权值为wi 。给出pu, v表示

2、顶点u经过边(u, v)到顶点v的概率。若某点i发出边概率和为pi ，那么在顶点i时有1pi的概率停止行动。定义路径权为这条路径上所有点权之和。问从一个顶点s开始，在每次按照指定的概率走的前提下，到某一顶点停止行动时所走的路径权的期望值。例如这张有向图， s = 1 。w1 = w2 = w3 = 1，w4 = 0。可以看到有两条路径。两条路径权分别为3和2，而走这两条路径的概率均为0.5。所以得到的期望为2.5 = 0.53 + 0.52 。123410.50.51对于这种不存在环的有向图。设fi表示从顶点i出发的路径权期望。可以分成两类情况。从顶点i出发经过相邻顶点k的路径权期望为fk +

3、wi ，概率pi, k 。停止行动路径权wi 。123410.50.51可以得到如下的递推式并按照拓扑序来递推但若将这张有向图稍作修改123410.50.51ekiijkkijiwfpf),(1,可以得到如下的递推式并按照拓扑序来递推但若将这张有向图稍作修改图存在环。ekiijkkijiwfpf),(1,123410.50.51所以对于一般的有向图，可以设fi,j为从顶点i出发，经过j步所走路径的路径权期望。那么有：当j 0时iiwf0,ekiijkkijiwfpf),(1,123410.50.51所以对于一般的情况，可以设fi,j为从顶点i出发，经过j步所走路径的路径权期望。那么有：当j 0

4、时iiwf0,ekiijkkijiwfpf),(1,若fi,j当 j时收敛，设收敛于fi那么答案即为fs。123410.50.51若fi,j当 j时收敛，设收敛于fi那么答案即为fs。可以利用迭代求出满足精度要求的解，但是时间复杂度无法接受。ekiijkkijiwfpf),(1,123410.50.51方程形式：对于右图可以得到如下方程组ekiijkkijiwfpf),(1,015 . 05 . 01144133221ffffffff123410.50.51高斯消元ekiijkkijiwfpf),(1,1-100101-101-0.5 01-0.5 100010123410.50.51方程组中

5、只含有与s相关的点。方程组没有唯一解的情况。可以调整消元顺序让所要求的fs放在最后，这样就可以不用回代。若权在边上而不在点上的话，设边(u, v)的权值为wu,v，那么同理方程即为ejijijjiiwfpf),(,)(题目来源：swerc 08一个mn的棋盘，左上至右下编号为(1, 1)至 (m, n)，并给定每个格子到周围四个格子的概率。一个骑士从(1, 1)开始，按照给定概率走，问到达(m, n)的期望步数。题目保证从任一格开始到(m, n)的概率均为1 。)(,kjip问题描述问题描述列出方程直接求解？ei, j表示从(i, j)出发的步数期望。11,)4(, 1)3(,1,)2(, 1

6、)1(,jijijijijijijijijiepepepepem, n 40accept?时间复杂度o(m3n3)time limit exceeded 分析分析方程未知量 第i行第j列的格子表示了方程：11,)4(, 1)3(,1,)2(, 1)1 (,jijijijijijijijijiepepepepe优化优化方程未知量 第i行第j列的格子表示了未知量：jie,优化优化同样为了避免回代，可以以逆序也就是em, n到e1, 1的顺序进行消元。123方程未知量优化优化对于方程而言，若当前要消去的未知量为ex, y。方程未知量ex, yyyxx优化优化与开始的mn个方程相比，减少的方程数和消去

7、的未知量数相等。方程未知量yyxx优化优化ex, y满足i x1或i = x1且j y的方程不包含当前要消的和之前消去的未知量方程未知量11,)4(, 1)3(,1,)2(, 1)1 (,jijijijijijijijijiepepepepeyyxx优化优化ex, y所以最多与n个方程进行消元。方程未知量yyxx优化优化ex, y消元顺序最后的未知量为ex-2, y。所以对于增广矩阵来说，每次消元最多只需要对n行和其中的2n+1列进行操作。方程未知量yyxx优化优化ex, y时间复杂度o(n3m3) o(n3m)。空间复杂度可优化至o(n2m)。方程未知量xxyy时空复杂度时空复杂度ex, y期望模型期望模型有限递推有限递推无限递推无限递推有环有