算法合集之淺析競賽中一類數(shù)學(xué)期望問題的解決方法-ppt課件

1、福建省福州第八中學(xué) 湯可因什么是數(shù)學(xué)期望什么是數(shù)學(xué)期望如果如果X是一個離散的隨機(jī)變量，輸出值是一個離散的隨機(jī)變量，輸出值為為 x1, x2, .， 和輸出值相應(yīng)的概率為和輸出值相應(yīng)的概率為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一、利用遞推或動態(tài)規(guī)劃解決二、建立線性方程組解決模型例題：First Knight例題：Mario給出一張

2、有向圖G = (V, E)。頂點i的權(quán)值為Wi 。給出Pu, v表示頂點u經(jīng)過邊(u, v)到頂點v的概率。若某點i發(fā)出邊概率和為Pi ，那么在頂點i時有1Pi的概率停止行動。定義路徑權(quán)為這條路徑上所有點權(quán)之和。問從一個頂點s開始，在每次按照指定的概率走的前提下，到某一頂點停止行動時所走的路徑權(quán)的期望值。例如這張有向圖， s = 1 。W1 = W2 = W3 = 1，W4 = 0?？梢钥吹接袃蓷l路徑。兩條路徑權(quán)分別為3和2，而走這兩條路徑的概率均為0.5。所以得到的期望為2.5 = 0.53 + 0.52 。123410.50.51對于這種不存在環(huán)的有向圖。設(shè)Fi表示從頂點i出發(fā)的路徑權(quán)期望

3、?？梢苑殖蓛深惽闆r。從頂點i出發(fā)經(jīng)過相鄰頂點k的路徑權(quán)期望為Fk +Wi ，概率Pi, k 。停止行動路徑權(quán)Wi 。123410.50.51可以得到如下的遞推式并按照拓?fù)湫騺磉f推但若將這張有向圖稍作修改123410.50.51EkiijkkijiWFPF),(1,可以得到如下的遞推式并按照拓?fù)湫騺磉f推但若將這張有向圖稍作修改圖存在環(huán)。EkiijkkijiWFPF),(1,123410.50.51所以對于一般的有向圖，可以設(shè)Fi,j為從頂點i出發(fā)，經(jīng)過j步所走路徑的路徑權(quán)期望。那么有：當(dāng)j 0時iiWF0,EkiijkkijiWFPF),(1,123410.50.51所以對于一般的情況，可以設(shè)F

4、i,j為從頂點i出發(fā)，經(jīng)過j步所走路徑的路徑權(quán)期望。那么有：當(dāng)j 0時iiWF0,EkiijkkijiWFPF),(1,若Fi,j當(dāng) j時收斂，設(shè)收斂于Fi那么答案即為Fs。123410.50.51若Fi,j當(dāng) j時收斂，設(shè)收斂于Fi那么答案即為Fs?？梢岳玫蟪鰸M足精度要求的解，但是時間復(fù)雜度無法接受。EkiijkkijiWFPF),(1,123410.50.51方程形式：對于右圖可以得到如下方程組EkiijkkijiWFPF),(1,015 . 05 . 01144133221FFFFFFFF123410.50.51高斯消元EkiijkkijiWFPF),(1,1-100101-101

5、-0.5 01-0.5 100010123410.50.51方程組中只含有與s相關(guān)的點。方程組沒有唯一解的情況?？梢哉{(diào)整消元順序讓所要求的Fs放在最后，這樣就可以不用回代。若權(quán)在邊上而不在點上的話，設(shè)邊(u, v)的權(quán)值為Wu,v，那么同理方程即為EjijijjiiWFPF),(,)(題目來源：SWERC 08一個mn的棋盤，左上至右下編號為(1, 1)至 (m, n)，并給定每個格子到周圍四個格子的概率。一個騎士從(1, 1)開場，按照給定概率走，問到達(dá)(m, n)的期望步數(shù)。題目保證從任一格開始到(m, n)的概率均為1 。)(,kjiP問題描述問題描述列出方程直接求解？Ei, j表示從(

6、i, j)出發(fā)的步數(shù)期望。11,)4(, 1)3(,1,)2(, 1)1(,jijijijijijijijijiEPEPEPEPEm, n 40Accept?時間復(fù)雜度O(m3n3)Time limit exceeded 分析分析方程未知量 第i行第j列的格子表示了方程：11,)4(, 1)3(,1,)2(, 1)1 (,jijijijijijijijijiEPEPEPEPE優(yōu)化優(yōu)化方程未知量 第i行第j列的格子表示了未知量：jiE,優(yōu)化優(yōu)化同樣為了避免回代，可以以逆序也就是Em, n到E1, 1的順序進(jìn)行消元。123方程未知量優(yōu)化優(yōu)化對于方程而言，若當(dāng)前要消去的未知量為Ex, y。方程未知量

7、Ex, yyyxx優(yōu)化優(yōu)化與開始的mn個方程相比，減少的方程數(shù)和消去的未知量數(shù)相等。方程未知量yyxx優(yōu)化優(yōu)化Ex, y滿足i x1或i = x1且j y的方程不包含當(dāng)前要消的和之前消去的未知量方程未知量11,)4(, 1)3(,1,)2(, 1)1 (,jijijijijijijijijiEPEPEPEPEyyxx優(yōu)化優(yōu)化Ex, y所以最多與n個方程進(jìn)行消元。方程未知量yyxx優(yōu)化優(yōu)化Ex, y消元順序最后的未知量為Ex-2, y。所以對于增廣矩陣來說，每次消元最多只需要對n行和其中的2n+1列進(jìn)行操作。方程未知量yyxx優(yōu)化優(yōu)化Ex, y時間復(fù)雜度O(n3m3) O(n3m)。空間復(fù)雜度可優(yōu)化至O(n2m)。方程未知量xxyy時空復(fù)雜度時空復(fù)雜度Ex, y期望模型期望模型有限遞推有限遞推無限遞推無限遞推有