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

Re: [問題] Interview street: zombie march

看板Prob_Solve (計算數學 Problem Solving)作者 (Achilles)時間11年前 (2012/10/31 23:58), 編輯推噓19(19推 0噓 91→)
留言110則, 7人參與, 最新討論串5/6 (看更多)
※ 引述《DJWS (...)》之銘言： : Leon提供了一個證明， : 證明題目給定的矩陣存在stationary probability distribution，而且很容易證明。 : 但是Leon完全沒有提到， : 這矩陣究竟是幾步之後才會收斂，只說它難解。 因為我知道這個一講下去沒人知道我再說甚麼啊, 我想這個版學過 Random process 的人應該不多. : 至於原問題是問：k步之後，究竟state會變成如何？ : Leon提到的這兩個命題，都無法完全解決原問題。 我想這是重點. 因為時間關係, 我寫文章的時候並沒有把所有條件列出來. 我所提供的方法, 是在考慮困難的情況下 (簡單的我根本不想看) 也就是在 M, N, K 很大的時候, 我怎麼去提供一個近似解. : 所以Leon並沒有解決原本的問題，只是提供了原問題的其中一些性質。 : 各位就算跟Leon繼續辯論下去，也得不到原問題的答案的。 : 至於Leon回文的第一句：「其實是.. 有的, 而且快到你難以想像.」 : 想必這句話是說錯了，其實他並沒有解決原問題。 在研究的路程上, 通常你只能得到 heurisitic solution, 並且你只能解一步狀況下的問題.. 我想, 公平的說, 我不用解 eignvalue, eign-vector 就能得到 stationary probability. 在這點的進展, 並且引起討論這是我樂於見到的. 我倒是很期待有人能放上更好的解法. 你要不要試試看? : 照Leon的文章內容來看， : 我想原問題應該是滿難解的， : 原因是牽扯到 Markov Chain mixing time， : 如果要繼續討論的話，從這關鍵字下手，大家應該會比較有交集。 : 另外我想請教的是， : Leon推文說到這是圖論問題， : 那麼目前市面上有沒有哪一本圖論書籍，有涵蓋到這個主題的？ 這個問題夯的很呢, 去 google Markov Chain mixing time, random walk, gossip algorithm 連 S. Boyd 都在這個領域發過文章. 這個人寫的論文比較淺顯, 也有例子, 你也可以在 page 15 以後找到他推論 mixing time 的公式 http://keithbriggs.info/documents/Min_Chen_MSc.pdf 教科書, 通常都是要晚個好幾年.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 76.170.76.59
推
11/01 00:11, , 1F
我想推文的人都應該有看懂你在說什麼 只是你可能中文不好
11/01 00:11, 1F
→
11/01 00:11, , 2F
一直沒辦法理解大家想討論一個確切解　而非近似解
11/01 00:11, 2F
→
11/01 00:13, , 3F
至於你提供近似解也是一個方向　不過也應該一開始就講明了
11/01 00:13, 3F
→
11/01 00:13, , 4F
免得大家搞不清楚你究竟想不想解決原問題
11/01 00:13, 4F
→
11/01 00:58, , 5F
我會寫那些東西, 是因為有人說可以觀察 eignvalue..
11/01 00:58, 5F
→
11/01 00:59, , 6F
Based on what you said on ``eignvalue'', I suppose you
11/01 00:59, 6F
→
11/01 00:59, , 7F
already accept the assumption on Markov Chain
11/01 00:59, 7F
→
11/01 01:00, , 8F
anyway, I don't think it's good to discuss this topic
11/01 01:00, 8F
→
11/01 01:00, , 9F
since not many people know about the concept
11/01 01:00, 9F
推
11/01 07:53, , 10F
是我提出來的 我當然知道呀...求eigenvalue是NP-hard
11/01 07:53, 10F
→
11/01 07:53, , 11F
所以我才說這個方法參考看看就好
11/01 07:53, 11F
→
11/01 07:54, , 12F
還有你eigenvalue打錯字了 XD
11/01 07:54, 12F
→
11/01 08:22, , 13F
你.. 是112的嗎? eigenvalue 是 NP-hard ????
11/01 08:22, 13F
→
11/01 08:23, , 14F
我.. 竟然浪費了時間和這群人討論....
11/01 08:23, 14F
→
11/01 08:27, , 15F
我除了這篇留給你看之外, 其他的我全砍了..
11/01 08:27, 15F
推
11/01 09:25, , 16F
DJ大口誤吧XDD
11/01 09:25, 16F
→
11/01 10:57, , 17F
"提到eigenvalue"是指我嗎? 我聽過(在你給的這份文件Ch4
11/01 10:57, 17F
→
11/01 10:58, , 18F
也有提到, 不過我還沒時間細看這份)那個second large
11/01 10:58, 18F
→
11/01 10:58, , 19F
eigenvalue與mixing rate的方法 才提起來的
11/01 10:58, 19F
→
11/01 11:01, , 20F
eigen decompose我只知道O(n^3), 所以我想請教mixing
11/01 11:01, 20F
→
11/01 11:02, , 21F
time有什麼好進展. 畢竟自己不是做隨機這方面領域的,
11/01 11:02, 21F
→
11/01 11:03, , 22F
自然希望有更多關鍵字指引, 不然MC,mixing time的文章
11/01 11:03, 22F
→
11/01 11:04, , 23F
對不是鑽這領域的人來說, 可太多了...
11/01 11:04, 23F
推
11/01 15:44, , 24F
就因式分解是NP-hard級別的 然後求eigenvalue可以化作多項式
11/01 15:44, 24F
→
11/01 15:44, , 25F
因式分解 所以求出所有eigenvalue是NP-hard
11/01 15:44, 25F
→
11/01 15:45, , 26F
因為很難算 所以可以用內插法、牛頓法等等的近似演算法求根
11/01 15:45, 26F
→
11/01 15:46, , 27F
所以我們可以用P-time求得一個根 目前所有的eigen-decomposi
11/01 15:46, 27F
→
11/01 15:47, , 28F
tion的演算法，都是基於近似演算法的
11/01 15:47, 28F
→
11/01 15:48, , 29F
這段是之前從別人blog看到的 如果我的理解有誤請告訴我
11/01 15:48, 29F
推
11/01 15:59, , 30F
另外就是 我並不覺得跟你討論是浪費時間 還是能學到新觀念
11/01 15:59, 30F
推
11/01 16:04, , 31F
只是你講的內容實在偏離原問題太多 使得大家沒共識而已...
11/01 16:04, 31F
→
11/01 16:07, , 32F
抱歉...第一句話開頭請改成「多項式因式分解是NP-hard級別」
11/01 16:07, 32F
→
11/01 19:24, , 33F
可不可以題外話問一下XD 像這種求解出來可能是什麼根號
11/01 19:24, 33F
→
11/01 19:25, , 34F
什麼奇怪的實數的問題 我們說計算時間一般是指什麼的的時
11/01 19:25, 34F
→
11/01 19:25, , 35F
間? 比如 (-b+-sqrt(b^2-4ac))/(2a), 是忽略那sqrt時間嗎?
11/01 19:25, 35F
推
11/01 22:03, , 36F
如果是說big-O notation的話 只留下成長最快的那一項就可以
11/01 22:03, 36F
→
11/01 22:05, , 37F
噢, 我說得不太清楚, 這樣問好了
11/01 22:05, 37F
→
11/01 22:05, , 38F
我們說計算這個的時間複雜度 是指計算近似值到某特定精度
11/01 22:05, 38F
→
11/01 22:06, , 39F
的演算法的複雜度嗎?ZY
11/01 22:06, 39F
還有 31 則推文
還有 1 段內文
→
11/03 15:35, , 71F
我覺得 DJWS 說的應該是求 exact value ，而不是數值解
11/03 15:35, 71F
→
11/03 15:37, , 72F
也就是答案如果是 sqrt(2) ，就不能輸出 1.414...
11/03 15:37, 72F
→
11/03 15:51, , 73F
那可能是個滿弔詭的地方. sqrt(2)可以看成一個演算法, 輸
11/03 15:51, 73F
→
11/03 15:52, , 74F
出 x^2 - 2 = 0 的正根到任意精度位
11/03 15:52, 74F
→
11/03 15:52, , 75F
而一般任意五次或以上方程式, 其解沒有通用的方法用係數
11/03 15:52, 75F
→
11/03 15:53, , 76F
的加減乘除及某些次方根來表示
11/03 15:53, 76F
→
11/03 15:53, , 77F
所以是必要用其他的表示法 就看接不接受
11/03 15:53, 77F
→
11/03 15:58, , 78F
我認為DJWS寫的東西, 與Matrix computation談的complexity
11/03 15:58, 78F
→
11/03 15:59, , 79F
定義完全不同, 所以我建議他去修課, 看看別人怎麼定義問題
11/03 15:59, 79F
→
11/03 16:00, , 80F
不然就把自己的定義寫成文章投稿 解釋`eigenvalue is NP-hard
11/03 16:00, 80F
→
11/03 16:06, , 81F
順便給樓上兩位: finite state machine 怎麼表示 irrational
11/03 16:06, 81F
→
11/03 16:07, , 82F
number? 有辦法 exactly 表示 [0,1] 間的 irrational number?
11/03 16:07, 82F
推
11/03 16:09, , 83F
我對電腦中的exact value的理解是要像mathematica那樣，
11/03 16:09, 83F
→
11/03 16:10, , 84F
1/3 他就寫 1/3 ，sqrt(2) 他就寫 sqrt(2)，pi 就是 pi
11/03 16:10, 84F
推
11/03 18:46, , 85F
所以你也沒修過complexity囉？ 那麼等我問到，我再教你。
11/03 18:46, 85F
→
11/03 18:51, , 86F
如果你有管道可以問的話　也請你幫忙問一下 謝謝!
11/03 18:51, 86F
推
11/03 19:41, , 87F
話說, Mathematica 能對於任意正整數 n, 都給出
11/03 19:41, 87F
→
11/03 19:42, , 88F
x^5 + x - n = 0 的解的 exact value 嗎?
11/03 19:42, 88F
→
11/03 19:42, , 89F
我手邊只有 Maple, 可是不知道怎麼下指令..|||
11/03 19:42, 89F
推
11/03 20:30, , 90F
我覺得現在好像是在討論eigenvalue是不是computable number
11/03 20:30, 90F
→
11/03 20:30, , 91F
11/03 20:30, 91F
→
11/03 20:34, , 92F
是好像有這種味道XDDD
11/03 20:34, 92F
→
11/04 01:12, , 93F
我認為 DJWS 寫的東西還是不要看比較好, 對知識長進有害
11/04 01:12, 93F
→
11/04 01:13, , 94F
你先去念 CLRS 的 algorithm, 再去看 Golomb 的 matrix
11/04 01:13, 94F
→
11/04 01:14, , 95F
Computation, 另外, 敢上來嗆人就得先學會 google, 不是嘛?
11/04 01:14, 95F
推
11/04 10:35, , 96F
那我大概有個底了 我想你應該是做訊號方面的!
11/04 10:35, 96F
→
11/04 10:37, , 97F
CLRS我整本都讀過了 至於矩陣運算我真的不熟
11/04 10:37, 97F
→
11/04 10:37, , 98F
還有就是關於eigenvalue的問題 我昨天努力google了很久
11/04 10:37, 98F
→
11/04 10:39, , 99F
多項式因式分解是P 包括有理數/代數擴展 http://ppt.cc/vnOA
11/04 10:39, 99F
→
11/04 10:40, , 100F
特徵多項式是GapL http://ppt.cc/xBLC
11/04 10:40, 100F
→
11/04 10:42, , 101F
特徵多項式事實上也有P演算法 http://ppt.cc/T_E3
11/04 10:42, 101F
→
11/04 10:43, , 102F
求eigenvalue其實就是對特徵多項式作因式分解 故推論為P
11/04 10:43, 102F
→
11/04 10:44, , 103F
至於求eigenvector、求eigenbasis的部分我還沒找到資料
11/04 10:44, 103F
→
11/04 10:45, , 104F
所以我的推文確實推錯了 求eigenvalue是P才對! 不好意思...
11/04 10:45, 104F
推
11/04 10:58, , 105F
另外想問 Golomb 的 matrix 是哪一本書？ 因為找不到書名裡
11/04 10:58, 105F
→
11/04 10:58, , 106F
有 martix 的...
11/04 10:58, 106F
推
11/04 20:46, , 107F
Eigenvalue的複雜度可以參考這篇論文
11/04 20:46, 107F
→
11/04 20:46, , 108F
The complexity of the matrix eigenproblem, STOC 1999
11/04 20:46, 108F
推
11/04 20:49, , 109F
至於書的話 我猜他是在說Matrix Computations, by Golub
11/04 20:49, 109F
推
11/04 22:39, , 110F
謝謝樓上! 有空來去圖書館翻一翻
11/04 22:39, 110F
‣ 更多 Leon 的文章
文章代碼(AID): #1GaKgW6g (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Leon 的文章
文章代碼(AID): #1GaKgW6g (Prob_Solve)