作者darrenlee1 (darrenleeleelee)
看板Grad-ProbAsk
標題[理工] 108交大資演13題
時間Sat Jan 22 11:23:24 2022
https://i.imgur.com/PtNhc0R.jpg
想問一下這題題目是在說什麼呢，那個數學式有點看不懂，27就做不出來。
28、29了解fibonacci 和binary heap就做得出來。
但27真的沒想法…
Ans:
27.E
28.ACDE
29.D
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.163.67 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1642821806.A.CF7.html
1F：推 VF84: 我想不太到好的解釋，但我認為它跟 Prim 在基本的精神上有 01/22 13:44
2F：→ VF84: 些類似。你或許可以試著從這點下手 01/22 13:44
3F：推 kronze7109: 算式講的是magic order的定義 01/23 22:18
4F：→ kronze7109: 我的理解是 01/23 22:19
5F：→ kronze7109: V1是演算法選出來的第一個點 01/23 22:19
6F：→ kronze7109: V2是第二個點，依此類推 01/23 22:19
7F：→ kronze7109: 01/23 22:19
8F：→ kronze7109: 選定V1後會將各點更新key值 01/23 22:19
9F：→ kronze7109: 也就是key(v2)=w(v1,v2)其餘的點也是一樣 01/23 22:19
10F：→ kronze7109: 新的一輪挑出key值最大的點當V2 01/23 22:19
11F：→ kronze7109: 再更新其餘的點 01/23 22:19
12F：→ kronze7109: key(v3)=key(v3)+w(v2,v3)=w(v1,v3)+w(v2,v3) 01/23 22:19
13F：→ kronze7109: 依此類推 01/23 22:19
14F：→ kronze7109: 每個key值就會變成式子那樣 01/23 22:19
15F：→ kronze7109: 如此就可以求出magic order了 01/23 22:19
16F：→ kronze7109: 有點像是Dijkstra的感覺 01/23 22:19
17F：→ kronze7109: 如果還是不懂歡迎指教 01/23 22:19
18F：→ kronze7109: 有錯誤的地方也請各位大神鞭策 01/23 22:19