PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Interview street: zombie march

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/10/31 21:58)推噓1(1推 0噓 5→)

留言6則, 3人參與討論串4/6 (看更多)

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