打擾一下
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:00G(V,E)具HP <=> G具 degree-constrain ST of degree 2
第一題是機率矩陣吧算lim A^n觀察一下可以看出每行是1算ker(A-I)即可得穩態向量
作者: a28238341a (小蝸) 2019-02-04 01:40:00
樓上 我當年也這樣想 直到我膝蓋中了一箭
剛剛去查才看到A^n所有值都要>0才可以，還是乖乖對角化吧，抱歉耍白痴了這題這個計算量也太狠Q不過他矩陣有設計過，eigenvalue可以馬上看出來，感覺還有點人性
這是Absorbing Markov Chain，是有特殊算法，不過很細
作者: a28238341a (小蝸) 2019-02-04 09:47:00
其實我看過有些題目不是所有的值大於零也可以算..所以我不是很清楚這種矩陣的條件是不是很緊
主要是想要知道有沒有穩態矩陣，所以是看絕對值為1的特徵值是不是只有1吧，除了1以外應該都會導致不收斂至於其他絕對值小於1的特徵值，就算不可對角化也會收斂上面指的是有沒有穩態，至於ker(A-I)算法就是看維度吧也不對，只看維度也判斷不出只有一個1，其他都單位長還是只能看會不會變正則馬可夫鏈吧或是吸收馬可夫鏈
像樓上給的矩陣C，雖然不是regular，但只有一個穩態
作者: a28238341a (小蝸) 2019-02-04 17:30:00
哦哦這個我沒有注意到 原來是這樣 感謝
DCST那個可以從Hamiltonian path reduce過去(使k=2)