Re: [中譯] Projecteuler (280) Ant and seeds
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (小維)時間16年前 (2010/03/01 20:25)推噓8(8推 0噓 11→)留言19則, 5人參與討論串4/5 (看更多)
剛剛想到所有期望值形式上的算法。還是以三乘三為例 ａｂｃ
ｄｅｆ
ｇｈｉ
馬可夫矩陣 起始狀態矩陣 (以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大有沒有進展~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.60
推
03/01 22:22, , 1F
03/01 22:22, 1F
→
03/01 22:23, , 2F
03/01 22:23, 2F
→
03/01 22:23, , 3F
03/01 22:23, 3F
→
03/01 22:28, , 4F
03/01 22:28, 4F
→
03/01 22:28, , 5F
03/01 22:28, 5F
推
03/01 22:29, , 6F
03/01 22:29, 6F
→
03/01 22:34, , 7F
03/01 22:34, 7F
推
03/01 22:36, , 8F
03/01 22:36, 8F
→
03/01 22:42, , 9F
03/01 22:42, 9F
推
03/01 22:49, , 10F
03/01 22:49, 10F
推
03/01 22:51, , 11F
03/01 22:51, 11F
→
03/01 22:58, , 12F
03/01 22:58, 12F
→
03/02 00:48, , 13F
03/02 00:48, 13F
另外 原來Knuth就是高德納XD 我還以為是某個研究Computer Science簡稱咧
http://zh.wikipedia.org/wiki/%E9%AB%98%E5%BE%B7%E7%BA%B3
要用時才真的覺得自己的力量、知識不足－－心之谷裡，阿雯是這樣說的。
^_^
推
03/02 00:54, , 14F
03/02 00:54, 14F
推
03/02 01:15, , 15F
03/02 01:15, 15F
→
03/02 01:16, , 16F
03/02 01:16, 16F
推
03/02 01:48, , 17F
03/02 01:48, 17F
※ 編輯: jurian0101 來自: 140.112.243.60 (03/02 01:55)
→
03/04 19:23, , 18F
03/04 19:23, 18F
→
03/04 19:25, , 19F
03/04 19:25, 19F
討論串 (同標題文章)
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
14
32