※ 引述《Leon (Achilles)》之铭言： : ※ 引述《shaopin (problem maker)》之铭言： : : 题目是要问: 最後 有最多zombie的五个node上的zombie数量 : : 在此请教不知道更快的做法是否是跟那只选五个最多的zombie node : : 有关? 但我还是不知道怎麽做?? : 其实是.. 有的, 而且快到你难以想像. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ : 接下来我们探讨几个问题: : 1. 给定一个 Markov Chain, Stationary probability distribution : 是否存在? : Ans: 这问题很大, 在 Random Process 有个章节专门探讨这个问题, : 但在这个题目 ( actually it's a special graph), : stationary probability distribution 是存在的, 我们之後会证明. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ : 2. 请问几步之後他会收敛到 stationary probability? : Ans: 这问题也是很大, 因为这牵扯到 Markov Chain mixing time, : 这是 Markov Chain Monte Carlo 的核心问题, 也.. 难解. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ : 但是, 求解 stationary probability distribution 的过程, : 漂亮的令你难以想像. Leon提供了一个证明， 证明题目给定的矩阵存在stationary probability distribution，而且很容易证明。 但是Leon完全没有提到， 这矩阵究竟是几步之後才会收敛，只说它难解。 至於原问题是问：k步之後，究竟state会变成如何？ Leon提到的这两个命题，都无法完全解决原问题。 所以Leon并没有解决原本的问题，只是提供了原问题的其中一些性质。 各位就算跟Leon继续辩论下去，也得不到原问题的答案的。 至於Leon回文的第一句：「其实是.. 有的, 而且快到你难以想像.」 想必这句话是说错了，其实他并没有解决原问题。 照Leon的文章内容来看， 我想原问题应该是满难解的， 原因是牵扯到 Markov Chain mixing time， 如果要继续讨论的话，从这关键字下手，大家应该会比较有交集。 另外我想请教的是， Leon推文说到这是图论问题， 那麽目前市面上有没有哪一本图论书籍，有涵盖到这个主题的？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 36.225.136.162 ※ 编辑: DJWS 来自: 36.225.136.162 (10/31 22:19)