算法合集之《浅析竞赛中一类数学期望问题的解决方法》.ppt
《算法合集之《浅析竞赛中一类数学期望问题的解决方法》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《浅析竞赛中一类数学期望问题的解决方法》.ppt(30页珍藏版)》请在三一文库上搜索。
1、浅析竞赛中一类数学期望问题的解决方法,福建省福州第八中学 汤可因,预备知识,什么是数学期望 如果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.43 + 0.64 = 3.6,引言,一、利用递推或动态规划解决 二、建立线性方程组解决 模型 例题:First Knight 例题:Mario,引入模型,给出一张有向图G = (V, E)。 顶点i的权值为Wi 。 给出Pu,
2、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.53 + 0.52 。,1,2,3,4,1,0.5,0.5,1,引入模型,对于这种不存在环的有向图。 设Fi表示从顶点i出发的路 径权期望。
3、 可以分成两类情况。 从顶点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,引入模型,所以对于一般的情
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅析竞赛中一类数学期望问题的解决方法 算法 浅析 竞赛 一类 数学 期望 问题 解决方法
链接地址:https://www.31doc.com/p-2158926.html