打扰一下
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)