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

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