作者eigen555 (一一一)
看板Grad-ProbAsk
標題[理工] 106成大線代/103清大演算法
時間Mon Feb 4 00:11:27 2019
打擾一下
https://i.imgur.com/a16wCUA.jpg
這題我算得辛苦 數字醜醜的
因為網路上也找不到答案
請問有什麼特殊算法嗎
https://i.imgur.com/OU9swYc.jpg
這題想了好久沒有頭緒
可以請高手們指教嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.76.112.242
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549210290.A.631.html
1F：推 zuchang: 第一題可以對角化 特徵根會有分數 n次方後變0會好算很多 02/04 00:17
2F：推 FRAXIS: 第二題 wiki 上有解釋 02/04 00:44
3F：推 alen0303: G(V,E)具HP <=> G具 degree-constrain ST of degree 2 02/04 01:07
4F：推 ncdonalds123: 第一題是機率矩陣吧 02/04 01:26
5F：→ ncdonalds123: 算lim A^n觀察一下可以看出每行是1 02/04 01:30
6F：→ ncdonalds123: 算ker(A-I)即可得穩態向量 02/04 01:32
7F：→ a28238341a: 樓上 我當年也這樣想 直到我膝蓋中了一箭 02/04 01:40
8F：→ ncdonalds123: 樓上如你所說，我算了一下卡住了....沉思中 02/04 01:55
9F：推 olen0622: 非正則矩陣不會穩態 這樣算會爆炸 02/04 02:02
10F：→ ncdonalds123: 剛剛去查才看到A^n所有值都要>0才可以，還是乖乖對 02/04 02:08
11F：→ ncdonalds123: 角化吧，抱歉耍白痴了 02/04 02:08
12F：→ ncdonalds123: 這題這個計算量也太狠Q 02/04 02:11
13F：→ ncdonalds123: 不過他矩陣有設計過，eigenvalue可以馬上看出來， 02/04 02:35
14F：→ ncdonalds123: 感覺還有點人性 02/04 02:35
15F：→ Ricestone: 這是Absorbing Markov Chain，是有特殊算法，不過 02/04 02:53
16F：→ Ricestone: 很細 02/04 02:53
17F：→ a28238341a: 其實我看過有些題目不是所有的值大於零也可以算.. 02/04 09:47
18F：→ a28238341a: 所以我不是很清楚這種矩陣的條件是不是很緊 02/04 09:48
19F：→ gaowei16: 第一題硬幹 印象中是 59. 0 0 53 02/04 10:25
20F：→ Ricestone: 主要是想要知道有沒有穩態矩陣，所以是看絕對值為1的 02/04 11:27
21F：→ Ricestone: 特徵值是不是只有1吧，除了1以外應該都會導致不收斂 02/04 11:28
22F：→ Ricestone: 至於其他絕對值小於1的特徵值，就算不可對角化也會收斂 02/04 11:28
23F：→ Ricestone: 上面指的是有沒有穩態，至於ker(A-I)算法就是看維度吧 02/04 11:34
24F：→ Ricestone: 也不對，只看維度也判斷不出只有一個1，其他都單位長 02/04 11:45
25F：→ Ricestone: 還是只能看會不會變正則馬可夫鏈吧 02/04 11:45
26F：→ Ricestone: 或是吸收馬可夫鏈 02/04 11:46
27F：推 ncdonalds123: 給樓上上上子嘉上課的定理，A^k有非零即可，不是A 02/04 14:02
28F：→ ncdonalds123: 要非零 02/04 14:02
30F：→ Ricestone: 像樓上給的矩陣C，雖然不是regular，但只有一個穩態 02/04 16:43
31F：推 a28238341a: 哦哦這個我沒有注意到 原來是這樣 感謝 02/04 17:30
32F：→ GeniusPuddin: DCST那個可以從Hamiltonian path reduce過去(使k=2) 02/07 14:56