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

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

2、有向圖G = (V, E)。頂點(diǎn)i的權(quán)值為Wi 。給出Pu, v表示頂點(diǎn)u經(jīng)過(guò)邊(u, v)到頂點(diǎn)v的概率。若某點(diǎn)i發(fā)出邊概率和為Pi ，那么在頂點(diǎn)i時(shí)有1Pi的概率停止行動(dòng)。定義路徑權(quán)為這條路徑上所有點(diǎn)權(quán)之和。問(wèn)從一個(gè)頂點(diǎn)s開(kāi)始，在每次按照指定的概率走的前提下，到某一頂點(diǎn)停止行動(dòng)時(shí)所走的路徑權(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對(duì)于這種不存在環(huán)的有向圖。設(shè)Fi表示從頂點(diǎn)i出發(fā)的路徑權(quán)期望

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

4、i,j為從頂點(diǎn)i出發(fā)，經(jīng)過(guò)j步所走路徑的路徑權(quán)期望。那么有：當(dāng)j 0時(shí)iiWF0,EkiijkkijiWFPF),(1,若Fi,j當(dāng) j時(shí)收斂，設(shè)收斂于Fi那么答案即為Fs。123410.50.51若Fi,j當(dāng) j時(shí)收斂，設(shè)收斂于Fi那么答案即為Fs?？梢岳玫蟪鰸M足精度要求的解，但是時(shí)間復(fù)雜度無(wú)法接受。EkiijkkijiWFPF),(1,123410.50.51方程形式：對(duì)于右圖可以得到如下方程組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ǎn)。方程組沒(méi)有唯一解的情況。可以調(diào)整消元順序讓所要求的Fs放在最后，這樣就可以不用回代。若權(quán)在邊上而不在點(diǎn)上的話，設(shè)邊(u, v)的權(quán)值為Wu,v，那么同理方程即為EjijijjiiWFPF),(,)(題目來(lái)源：SWERC 08一個(gè)mn的棋盤，左上至右下編號(hào)為(1, 1)至 (m, n)，并給定每個(gè)格子到周圍四個(gè)格子的概率。一個(gè)騎士從(1, 1)開(kāi)場(chǎng)，按照給定概率走，問(wèn)到達(dá)(m, n)的期望步數(shù)。題目保證從任一格開(kāi)始到(m, n)的概率均為1 。)(,kjiP問(wèn)題描述問(wèn)題描述列出方程直接求解？Ei, j表示從(

6、i, j)出發(fā)的步數(shù)期望。11,)4(, 1)3(,1,)2(, 1)1(,jijijijijijijijijiEPEPEPEPEm, n 40Accept?時(shí)間復(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方程未知量?jī)?yōu)化優(yōu)化對(duì)于方程而言，若當(dāng)前要消去的未知量為Ex, y。方程未知量

7、Ex, yyyxx優(yōu)化優(yōu)化與開(kāi)始的mn個(gè)方程相比，減少的方程數(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個(gè)方程進(jìn)行消元。方程未知量yyxx優(yōu)化優(yōu)化Ex, y消元順序最后的未知量為Ex-2, y。所以對(duì)于增廣矩陣來(lái)說(shuō)，每次消元最多只需要對(duì)n行和其中的2n+1列進(jìn)行操作。方程未知量yyxx優(yōu)化優(yōu)化Ex, y時(shí)間復(fù)雜度O(n3m3) O(n3m)?？臻g復(fù)雜度可優(yōu)化至O(n2m)。方程未知量xxyy時(shí)空復(fù)雜度時(shí)空復(fù)雜度Ex, y期望模型期望模型有限遞推有限遞推無(wú)限遞推無(wú)限遞推有