算法合集之《浅析竞赛中一类数学期望问题的解决方法》.ppt
浅析竞赛中一类数学期望问题的解决方法,福建省福州第八中学 汤可因,预备知识,什么是数学期望 如果X是一个离散的随机变量，输出值为 x1, x2, .， 和输出值相应的概率为p1, p2, . （概率和为1）, 那么期望值,预备知识,全期望公式,E(Y | X = 1)=4,E(Y | X = 2)=3,P(X = 2)=0.4,P(X = 1)=0.6,E(Y)=0.4×3 + 0.6×4 = 3.6,引言,一、利用递推或动态规划解决 二、建立线性方程组解决 模型 例题：First Knight 例题：Mario,引入模型,给出一张有向图G = (V, E)。 顶点i的权值为Wi 。 给出Pu, v表示顶点u经过边(u, v)到顶点v的概率。若某点i发出边概率和为Pi ，那么在顶点i时有1Pi的概率停止行动。 定义路径权为这条路径上所有点权之和。 问从一个顶点s开始，在每次按照指定的概率走的前提下，到某一顶点停止行动时所走的路径权的期望值。,引入模型,例如这张有向图， s = 1 。 W1 = W2 = W3 = 1，W4 = 0。 可以看到有两条路径。两 条路径权分别为3和2，而 走这两条路径的概率均为0.5。 所以得到的期望为 2.5 = 0.5×3 + 0.5×2 。,1,2,3,4,1,0.5,0.5,1,引入模型,对于这种不存在环的有向图。 设Fi表示从顶点i出发的路 径权期望。 可以分成两类情况。 从顶点i出发经过相邻顶点k的路 径权期望为Fk +Wi ，概率Pi, k 。 停止行动路径权Wi 。,1,2,3,4,1,0.5,0.5,1,引入模型,可以得到如下的递推式 并按照拓扑序来递推 但若将这张有向图稍作修改,1,2,3,4,1,0.5,0.5,1,引入模型,可以得到如下的递推式 并按照拓扑序来递推 但若将这张有向图稍作修改 图存在环。,1,2,3,4,1,0.5,0.5,1,引入模型,所以对于一般的有向图，可 以设Fi,j为从顶点i出发，经 过j步所走路径的路径权 期望。 那么有： 当j 0时,1,2,3,4,1,0.5,0.5,1,引入模型,所以对于一般的情况，可 以设Fi,j为从顶点i出发，经 过j步所走路径的路径权 期望。 那么有： 当j 0时,若Fi,j当 j时收敛，设 收敛于Fi 那么答案即为Fs。,1,2,3,4,1,0.5,0.5,1,引入模型,若Fi,j当 j时收敛，设 收敛于Fi 那么答案即为Fs。 可以利用迭代求出满足精度要求的解，但是时间复杂度无法接受。,1,2,3,4,1,0.5,0.5,1,引入模型,方程形式： 对于右图可以得到如下方程组,1,2,3,4,1,0.5,0.5,1,引入模型,高斯消元,1 -1 0 0 1 0 1 -1 0 1 -0.5 0 1 -0.5 1 0 0 0 1 0,1,2,3,4,1,0.5,0.5,1,引入模型,方程组中只含有与s相关的点。 方程组没有唯一解的情况。 可以调整消元顺序让所要求的Fs放在最后，这样就可以不用回代。 若权在边上而不在点上的话，设边(u, v)的权值为Wu,v，那么同理方程即为,例题：First Knight,题目来源：SWERC 08 一个m×n的棋盘，左上至右下编号为(1, 1)至 (m, n)，并给定每个格子到周围四个格子的概率 。 一个骑士从(1, 1)开始，按照给定概率走，问到达(m, n)的期望步数。 题目保证从任一格开始到(m, n)的概率均为1 。,问题描述,例题：First Knight,列出方程直接求解？ Ei, j表示从(i, j)出发的步数期望。,m, n 40,Accept?,时间复杂度O(m3n3),Time limit exceeded ,进行优化！,分析,例题：First Knight,方程,未知量,第i行第j列的格子表示了方程：,优化,例题：First Knight,方程,未知量,第i行第j列的格子表示了未知量：,优化,例题：First Knight,同样为了避免回代，可以以逆序也就是Em, n到E1, 1的顺序进行消元。,1,2,3,方程,未知量,优化,例题：First Knight,对于方程而言，若当前要消去的未知量为Ex, y。,方程,未知量,Ex, y,y,y,x,x,优化,例题：First Knight,与开始的mn个方程相比，减少的方程数和消去的未知量数相等。,方程,未知量,y,y,x,x,优化,Ex, y,例题：First Knight,满足i x1或i = x1且j y的方程 不包含当前要消的和之前消去的未知量,方程,未知量,y,y,x,x,优化,Ex, y,例题：First Knight,所以最多与n个方程进行消元。,方程,未知量,y,y,x,x,优化,Ex, y,例题：First Knight,消元顺序最后的未知量为Ex-2, y。 所以对于增广矩阵来说，每次消元最多只需要对n行和其中的2n+1列进行操作。,方程,未知量,y,y,x,x,优化,Ex, y,例题：First Knight,时间复杂度O(n3m3) O(n3m)。 空间复杂度可优化至O(n2m)。,方程,未知量,x,x,y,y,时空复杂度,Ex, y,总结,期望模型,有限递推,无限递推,有环,无环,方程组,高斯消元,近似解，效率低,精确解，效率高,总结,期望模型,具体问题,对应,总结,具体问题,期望模型,对应,解决方法,处理优化,特点,选择,
