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

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