[理工] 106成大線代/103清大演算法 eigen555 PTT批踢踢實業坊

[理工] 106成大線代/103清大演算法

作者: eigen555 (一一一) 2019-02-04 00:11:27

打擾一下
https://i.imgur.com/a16wCUA.jpg
這題我算得辛苦數字醜醜的
因為網路上也找不到答案
請問有什麼特殊算法嗎
https://i.imgur.com/OU9swYc.jpg
這題想了好久沒有頭緒
可以請高手們指教嗎

作者: zuchang (chang) 2019-02-04 00:17:00

第一題可以對角化特徵根會有分數 n次方後變0會好算很多

作者: FRAXIS (喔喔) 2019-02-04 00:44:00

第二題 wiki 上有解釋

作者: alen0303 (艾倫零參智商負三) 2019-02-04 01:07:00

G(V,E)具HP <=> G具 degree-constrain ST of degree 2

作者: ncdonalds123 (benben) 2019-02-04 01:26:00

第一題是機率矩陣吧算lim A^n觀察一下可以看出每行是1算ker(A-I)即可得穩態向量

作者: a28238341a (小蝸) 2019-02-04 01:40:00

樓上我當年也這樣想直到我膝蓋中了一箭

作者: ncdonalds123 (benben) 2019-02-04 01:55:00

樓上如你所說，我算了一下卡住了....沉思中

作者: olen0622 (hong) 2019-02-04 02:02:00

非正則矩陣不會穩態這樣算會爆炸

作者: ncdonalds123 (benben) 2019-02-04 02:08:00

剛剛去查才看到A^n所有值都要>0才可以，還是乖乖對角化吧，抱歉耍白痴了這題這個計算量也太狠Q不過他矩陣有設計過，eigenvalue可以馬上看出來，感覺還有點人性

作者: Ricestone (麥飯石) 2019-02-04 02:53:00

這是Absorbing Markov Chain，是有特殊算法，不過很細

作者: a28238341a (小蝸) 2019-02-04 09:47:00

其實我看過有些題目不是所有的值大於零也可以算..所以我不是很清楚這種矩陣的條件是不是很緊

作者: gaowei16 (啾啾人) 2019-02-04 10:25:00

第一題硬幹印象中是 59. 0 0 53

作者: Ricestone (麥飯石) 2019-02-04 11:27:00

主要是想要知道有沒有穩態矩陣，所以是看絕對值為1的特徵值是不是只有1吧，除了1以外應該都會導致不收斂至於其他絕對值小於1的特徵值，就算不可對角化也會收斂上面指的是有沒有穩態，至於ker(A-I)算法就是看維度吧也不對，只看維度也判斷不出只有一個1，其他都單位長還是只能看會不會變正則馬可夫鏈吧或是吸收馬可夫鏈

作者: ncdonalds123 (benben) 2019-02-04 14:02:00

給樓上上上子嘉上課的定理，A^k有非零即可，不是A要非零https://i.imgur.com/wB8HJTK.jpg

作者: Ricestone (麥飯石) 2019-02-04 16:43:00

像樓上給的矩陣C，雖然不是regular，但只有一個穩態

作者: a28238341a (小蝸) 2019-02-04 17:30:00

哦哦這個我沒有注意到原來是這樣感謝

作者: GeniusPuddin (GeniusPudding) 2019-02-07 14:56:00

DCST那個可以從Hamiltonian path reduce過去(使k=2)

繼續閱讀

[理工] 交大102 計系21 23 兩問matt530 [理工] 台大106數學kaidi620 107 台大財金數學powerfulrebo [理工] 101清大計系waynetooni [理工]請教關於CPU 利用率kaidi620 [理工] 104 中興資概wei12f8158 [理工]離散黃上册圖論 6-37範例1 (95清大資工)S2067030 106 清大資應（資結計算機alily86 [理工] [工數]一題台科ode(已解決）Yic0197 [理工] 107清大資應計概( 線性代數離散alily86