※ 引述《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)