→ jurian0101:好吧，不是整數。429、430和431都不對 (沮喪) 03/01 01:34
推 LPH66:就算3x3這樣拆還是可能有問題... 03/01 06:56
→ LPH66:例如已經把一個種子由 g 搬到 a 好了 03/01 06:56
→ LPH66:那下一次要搬時得走到 h 和 i 才行 03/01 06:57
→ LPH66:這時a->h的期望步數和g,h,i都有種子時a->h的期望步數不一樣 03/01 06:58
→ jurian0101:沒錯，我有考慮到這個。現在我連種子都還不敢討論XD 03/01 08:53
→ jurian0101:只是想找出快速方法求出某到某狀態的機率(表列?) 03/01 08:55
Naively, 把所有可能狀態都列出來是動態規劃的精髓(worst-time 就確定了)
引用utomaya大的原文
０００００ 到 １１１１１ 我想這樣表示狀態: (3,3) Ant 位置
０００００ ０００００ 0 0或1 有無搬運種子
００╳００ ００╳００ 11111 上排
０００００ ０００００ 11111 下排
１１１１１ ０００００
乍看似乎有 5 x 5 x 2 x 32 x 32 = 51200種 電腦有這麼大記憶空間做51200階方陣的
馬可夫過程嗎? 不行XD 但先說其實種子的位置只有
Ant狀態為"沒有搬" : 1+ 5^2 +10^2 +10^2 +5^2 +1 = 252
Ant狀態為"搬運中" : 5x1 + 10x5 + 10x10 + 5x10 + 1x5 = 210 一共462種
ａｂｃ
ｄｅｆ
ｇｈｉ
回到九宮格，我用http://www.uni-bonn.de/~manfear/matrixcalc.php 這個線上
Matrix calculator "手動"算過了 從b到h的期望值不折不扣是12整，當我要呆呆繼續算
其他的期望值時......要上課了= =
A=
0 1/3 0 1/3 0 0 0 0 0 a
1/2 0 1/2 0 1/4 0 0 0 0 b
0 1/3 0 0 0 1/3 0 0 0 c
1/2 0 0 0 1/4 0 1/2 0 0 d
0 1/3 0 1/3 0 1/3 0 1/3 0 e
0 0 1/2 0 1/4 0 0 0 1/2 f
0 0 0 1/3 0 0 0 1/3 0 g
0 0 0 0 1/4 0 1/2 0 1/2 h
0 0 0 0 0 1/3 0 1/3 0 i
A^2=
1/3 0 1/6 0 1/6 0 1/6 0 0 a
0 5/12 0 1/4 0 1/4 0 1/12 0 b
1/6 0 1/3 0 1/6 0 0 0 1/6 c
0 1/4 0 5/12 0 1/12 0 1/4 0 d
1/3 0 1/3 0 1/3 0 1/3 0 1/3 e
0 1/4 0 1/12 0 5/12 0 1/4 0 f
1/6 0 0 0 1/6 0 1/3 0 1/6 g
0 1/12 0 1/4 0 1/4 0 5/12 0 h
0 0 1/6 0 1/6 0 1/6 0 1/3 i
WOW....
[手動計算途中]
[出現的趣題例]
請找出:<a_n>
1, 23, 241, 2375, 23233, 227063, 2218897, 21683111, 211887457, 2070564695
這個數列的
a. 遞迴關係 開燈:a_n+2 - 11*a_n+1 + 12*a_n = 0
b. 根據a求數列表達式 開燈:a_n= Ａα^n + Ｂβ^n
Ａ= 1/2 + 35/2√73 Ｂ= 1/2 - 35/2√73 α= (11+√73)/2 β=(11-√73)/2
(一般噁心而已)
c. 待求的期望值Exp(b→h)=
(0~∞)Σ (2n+2) * a_n / 12^(n+1)
※ 編輯: jurian0101 來自: 140.112.243.60 (03/01 10:02)