作者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
1F：推 utomaya:没耶 没学过马可夫链 这题太难了 我已经放弃了 03/01 22:22
2F：→ utomaya:不过我看到有人在题目po出後两小时内就解出来了 03/01 22:23
3F：→ utomaya:他应该用的不是这方法 03/01 22:23
4F：→ utomaya:刚看了一下 好像最快的人是45分钟内解出来 03/01 22:28
5F：→ utomaya:是个英国佬 PE里真的是一堆怪物级的人 03/01 22:28
6F：推 weijr:isnoneval po的解法就是正解了，这篇方向也对 03/01 22:29
7F：→ weijr:wrongbook也是用scipy 解的，方法同 isnoneval 03/01 22:34
8F：推 utomaya:你进到论坛了吗? 03/01 22:36
9F：→ utomaya:所以你已经解出来了? 真厉害 03/01 22:42
10F：推 weijr:因为这题对 python 来说，比较容易一点 03/01 22:49
11F：推 utomaya:嗯 没错 scipy好像是python的东西 C++没有这东西 03/01 22:51
12F：→ utomaya:嗯 原来你也有在玩PE 03/01 22:58
13F：→ 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
要用时才真的觉得自己的力量、知识不足－－心之谷里，阿雯是这样说的。
^_^
14F：推 FACE90006:鸭皇拜托教我python>///< 03/02 00:54
15F：推 utomaya:你现在才知道他是人名喔 他在计算机科学领域中很有名 03/02 01:15
16F：→ utomaya:我记得PE的论坛也有谈到他 03/02 01:16
17F：推 LPH66:他的 TAOCP 可是资工人的圣经呢 XD 03/02 01:48
※ 编辑: jurian0101 来自: 140.112.243.60 (03/02 01:55)
18F：→ jurian0101:後记:所谓无穷级数的"巧妙方法"其实是行不通的，Why? 03/04 19:23
19F：→ jurian0101:因为Ｐ一定是singular方阵 Orz 祝贺utomaya解出> < 03/04 19:25