[理工] 108交大資演13題

看板Grad-ProbAsk作者 (darrenleeleelee)時間2年前 (2022/01/22 11:23), 編輯推噓2(2推 0噓 16→)
留言18則, 2人參與, 2年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1642821806.A.CF7.html
推
01/22 13:44, 2年前 , 1F
我想不太到好的解釋，但我認為它跟 Prim 在基本的精神上有
01/22 13:44, 1F
→
01/22 13:44, 2年前 , 2F
些類似。你或許可以試著從這點下手
01/22 13:44, 2F
推
01/23 22:18, 2年前 , 3F
算式講的是magic order的定義
01/23 22:18, 3F
→
01/23 22:19, 2年前 , 4F
我的理解是
01/23 22:19, 4F
→
01/23 22:19, 2年前 , 5F
V1是演算法選出來的第一個點
01/23 22:19, 5F
→
01/23 22:19, 2年前 , 6F
V2是第二個點，依此類推
01/23 22:19, 6F
→
01/23 22:19, 2年前 , 7F
01/23 22:19, 7F
→
01/23 22:19, 2年前 , 8F
選定V1後會將各點更新key值
01/23 22:19, 8F
→
01/23 22:19, 2年前 , 9F
也就是key(v2)=w(v1,v2)其餘的點也是一樣
01/23 22:19, 9F
→
01/23 22:19, 2年前 , 10F
新的一輪挑出key值最大的點當V2
01/23 22:19, 10F
→
01/23 22:19, 2年前 , 11F
再更新其餘的點
01/23 22:19, 11F
→
01/23 22:19, 2年前 , 12F
key(v3)=key(v3)+w(v2,v3)=w(v1,v3)+w(v2,v3)
01/23 22:19, 12F
→
01/23 22:19, 2年前 , 13F
依此類推
01/23 22:19, 13F
→
01/23 22:19, 2年前 , 14F
每個key值就會變成式子那樣
01/23 22:19, 14F
→
01/23 22:19, 2年前 , 15F
如此就可以求出magic order了
01/23 22:19, 15F
→
01/23 22:19, 2年前 , 16F
有點像是Dijkstra的感覺
01/23 22:19, 16F
→
01/23 22:19, 2年前 , 17F
如果還是不懂歡迎指教
01/23 22:19, 17F
→
01/23 22:19, 2年前 , 18F
有錯誤的地方也請各位大神鞭策
01/23 22:19, 18F
‣ 更多 darrenlee1 的文章
文章代碼(AID): #1XwtYkpt (Grad-ProbAsk)