= ( 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.5 × 3 + 0.5 × 2 。 1234 1 0.5 0.5 1引入模型引入模型?对于这种不存在环的有向图。?设F i表示从顶点 i出发的路?径权期望。?可以分成两类情况。?从顶点 i出发经过相邻顶点 k的路?径权期望为 F k +W i,概率 P i , k。?停止行动路径权 W i。 1234 1 0.5 0.5 1引入模型引入模型?可以得到如下的递推式?并按照拓扑序来递推?但若将这张有向图稍作修改 1234 1 0.5 0.5 1 ????? Eki ijkkijiW FPF ),( 1,,,引入模型引入模型?可以得到如下的递推式?并按照拓扑序来递推?但若将这张有向图稍作修改?图存在环。????? Eki ijkkijiW FPF ),( 1,,, 1234 1 0.5 0.5 1引入模型引入模型?所以对于一般的有向图,可 以设 F i,j为从顶点 i出发,经 过j步所走路径的路径权 期望。?那么有: 当j > 0 时 iiW F? 0,????? Eki ijkkijiW FPF ),( 1,,, 1234 1 0.5 0.5 1
全文预览
