作者jurian0101 (小維)
看板puzzle
標題Re: [中譯] Projecteuler (280) Ant and seeds
時間Mon Mar 1 20:25:39 2010
剛剛想到所有期望值形式上的算法。還是以三乘三為例 ａｂｃ
ｄｅｆ
ｇｈｉ
馬可夫矩陣 起始狀態矩陣 (以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
推 utomaya:沒耶 沒學過馬可夫鏈 這題太難了 我已經放棄了 03/01 22:22
→ utomaya:不過我看到有人在題目po出後兩小時內就解出來了 03/01 22:23
→ utomaya:他應該用的不是這方法 03/01 22:23
→ utomaya:剛看了一下 好像最快的人是45分鐘內解出來 03/01 22:28
→ utomaya:是個英國佬 PE裡真的是一堆怪物級的人 03/01 22:28
推 weijr:isnoneval po的解法就是正解了，這篇方向也對 03/01 22:29
→ weijr:wrongbook也是用scipy 解的，方法同 isnoneval 03/01 22:34
推 utomaya:你進到論壇了嗎? 03/01 22:36
→ utomaya:所以你已經解出來了? 真厲害 03/01 22:42
推 weijr:因為這題對 python 來說，比較容易一點 03/01 22:49
推 utomaya:嗯 沒錯 scipy好像是python的東西 C++沒有這東西 03/01 22:51
→ utomaya:嗯 原來你也有在玩PE 03/01 22:58
→ jurian0101:暑假來研究python好了 又強大又是OpenSource。 03/02 00:48
另外 原來Knuth就是高德納XD 我還以為是某個研究Computer Science簡稱咧
http://zh.wikipedia.org/wiki/%E9%AB%98%E5%BE%B7%E7%BA%B3
要用時才真的覺得自己的力量、知識不足－－心之谷裡，阿雯是這樣說的。
^_^
推 FACE90006:鴨皇拜托教我python>///< 03/02 00:54
推 utomaya:你現在才知道他是人名喔 他在計算機科學領域中很有名 03/02 01:15
→ utomaya:我記得PE的論壇也有談到他 03/02 01:16
推 LPH66:他的 TAOCP 可是資工人的聖經呢 XD 03/02 01:48
※ 編輯: jurian0101 來自: 140.112.243.60 (03/02 01:55)
→ jurian0101:後記:所謂無窮級數的"巧妙方法"其實是行不通的，Why? 03/04 19:23
→ jurian0101:因為Ｐ一定是singular方陣 Orz 祝賀utomaya解出> < 03/04 19:25