作者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/cn.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