[理工] 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