Projecteuler (280) Ant and seeds - 拼圖

剛剛想到所有期望值形式上的算法。還是以三乘三為例 ａｂｃ
ｄｅｆ
　ｇｈｉ

馬可夫矩陣 起始狀態矩陣 (以b為例)
Ａ= Ｓ=
0 1/3 0 1/3 0 0 0 0 0 a 0
1/2 0 1/2 0 1/4 0 0 0 0 b 1
0 1/3 0 0 0 1/3 0 0 0 c 0
1/2 0 0 0 1/4 0 1/2 0 0 d 0
0 1/3 0 1/3 0 1/3 0 1/3 0 e 0
0 0 1/2 0 1/4 0 0 0 1/2 f 0
0 0 0 1/3 0 0 0 1/3 0 g 0
0 0 0 0 1/4 0 1/2 0 1/2 h 0
0 0 0 0 0 1/3 0 1/3 0 i 0

在程式的例子中，每到終點(這裡以h為例)的機率不為零時，便

1.乘上目前步數 2.加到期望值 3.然後再將i 歸零。

事實上在3x3或5x5的例子中，零與非零輪流出現，因此這些操作每兩次就得進行一次。

例如第一次是取 (Ａ^2)Ｓ 結果中的 h = 1/12

[POINT] 只把h歸零而其他機率不變的方法是乘上矩陣Ｅ (E for Elimination)

Ｅ=
0 1/3 0 1/3 0 0 0 0 0 a
1/2 0 1/2 0 1/4 0 0 0 0
0 1/3 0 0 0 1/3 0 0 0 .
1/2 0 0 0 1/4 0 1/2 0 0 .
0 1/3 0 1/3 0 1/3 0 1/3 0 .
0 0 1/2 0 1/4 0 0 0 1/2
0 0 0 1/3 0 0 0 1/3 0
0 0 0 0 0 0 0 0 0 h
0 0 0 0 0 1/3 0 1/3 0 i


跳結論，b→i的期望值
= 2 (Ａ^2)Ｓ + 4 (ＡＥ)(Ａ^2)Ｓ + 6 (ＡＥ)^2 (Ａ^2)Ｓ + ... 即

＿＿∞
╲
／ (2n+2) (ＡＥ)^n (Ａ^2)Ｓ 的i那一項
￣￣n=0

然後這是個無窮級數 令原式=EXP, ＡＥ= Ｐ, (Ａ^2)Ｓ = Ｓ'


EXP /2 = (Σ n P^n + Σ P^n) (Ａ^2)Ｓ

_1 2 _1
=[ ((I-P) ) P + (I-P) P ] (Ａ^2)Ｓ 媽呀，我竟然瘋到在PTT打數學式。

我們要的答案還是i那一項
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

這樣應該就可以直接算每種狀態的期望值(精確，還一定是有理數)，然後isoneval大

的125X ......管他多少種，只要能有效列舉就一定能算出來。

不過我手邊沒有矩陣運算的工具XD WOW 25階方陣耶，我連四階以上反矩陣怎麼算都忘了

先在這裡掉隊啦。不知道utomaya大有沒有進展~~~




--