推 zuchang: 第一題可以對角化 特徵根會有分數 n次方後變0會好算很多 02/04 00:17
推 FRAXIS: 第二題 wiki 上有解釋 02/04 00:44
推 alen0303: G(V,E)具HP <=> G具 degree-constrain ST of degree 2 02/04 01:07
推 ncdonalds123: 第一題是機率矩陣吧 02/04 01:26
→ ncdonalds123: 算lim A^n觀察一下可以看出每行是1 02/04 01:30
→ ncdonalds123: 算ker(A-I)即可得穩態向量 02/04 01:32
→ a28238341a: 樓上 我當年也這樣想 直到我膝蓋中了一箭 02/04 01:40
→ ncdonalds123: 樓上如你所說，我算了一下卡住了....沉思中 02/04 01:55
推 olen0622: 非正則矩陣不會穩態 這樣算會爆炸 02/04 02:02
→ ncdonalds123: 剛剛去查才看到A^n所有值都要>0才可以，還是乖乖對 02/04 02:08
→ ncdonalds123: 角化吧，抱歉耍白痴了 02/04 02:08
→ ncdonalds123: 這題這個計算量也太狠Q 02/04 02:11
→ ncdonalds123: 不過他矩陣有設計過，eigenvalue可以馬上看出來， 02/04 02:35
→ ncdonalds123: 感覺還有點人性 02/04 02:35
→ Ricestone: 這是Absorbing Markov Chain，是有特殊算法，不過 02/04 02:53
→ Ricestone: 很細 02/04 02:53
→ a28238341a: 其實我看過有些題目不是所有的值大於零也可以算.. 02/04 09:47
→ a28238341a: 所以我不是很清楚這種矩陣的條件是不是很緊 02/04 09:48
→ gaowei16: 第一題硬幹 印象中是 59. 0 0 53 02/04 10:25
→ Ricestone: 主要是想要知道有沒有穩態矩陣，所以是看絕對值為1的 02/04 11:27
→ Ricestone: 特徵值是不是只有1吧，除了1以外應該都會導致不收斂 02/04 11:28
→ Ricestone: 至於其他絕對值小於1的特徵值，就算不可對角化也會收斂 02/04 11:28
→ Ricestone: 上面指的是有沒有穩態，至於ker(A-I)算法就是看維度吧 02/04 11:34
→ Ricestone: 也不對，只看維度也判斷不出只有一個1，其他都單位長 02/04 11:45
→ Ricestone: 還是只能看會不會變正則馬可夫鏈吧 02/04 11:45
→ Ricestone: 或是吸收馬可夫鏈 02/04 11:46
推 ncdonalds123: 給樓上上上子嘉上課的定理，A^k有非零即可，不是A 02/04 14:02
→ ncdonalds123: 要非零 02/04 14:02
→ Ricestone: 像樓上給的矩陣C，雖然不是regular，但只有一個穩態 02/04 16:43
推 a28238341a: 哦哦這個我沒有注意到 原來是這樣 感謝 02/04 17:30
→ GeniusPuddin: DCST那個可以從Hamiltonian path reduce過去(使k=2) 02/07 14:56