[理工] 資演 OBST

看板Grad-ProbAsk作者 (毛毛)時間8年前 (2018/01/25 12:11), 編輯推噓19(19推 0噓 32→)
留言51則, 9人參與, 8年前最新討論串1/1
想請問大家在算OBST時 Cost矩陣的對角線是放0還是外部成本呢？ 一直以來我在算的時候都放外部成本，但我昨天發現資結的算法在計算Cost的時候對角線 都是放0，這樣答案會有全部外部成本的差距。 資結跟演算法的定義是不是常常有小出入呢 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.77.180 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1516853519.A.27A.html
推
01/25 12:37, 8年前 , 1F
要注意他們的I,j從哪裡開始
01/25 12:37, 1F
→
01/25 12:37, 8年前 , 2F
你把例子貼上來 大家會比較好跟你解釋
01/25 12:37, 2F
→
01/25 14:15, 8年前 , 3F
外部成本聽起來很像社會科學那個xD 要看題目怎麼定
01/25 14:15, 3F
→
01/25 14:15, 8年前 , 4F
義
01/25 14:15, 4F
→
01/25 14:36, 8年前 , 5F
01/25 14:36, 5F
→
01/25 14:37, 8年前 , 6F
01/25 14:37, 6F
→
01/25 14:37, 8年前 , 7F
這題如果放外部成本cost是2.4
01/25 14:37, 7F
→
01/25 14:37, 8年前 , 8F
如果放0就會如答案所說是2.0
01/25 14:37, 8F
推
01/25 19:12, 8年前 , 9F
這是DS跟ALGO對外部節點定義不同的關係
01/25 19:12, 9F
→
01/25 19:13, 8年前 , 10F
考試的時候 你就把假設寫清楚應該就好了
01/25 19:13, 10F
推
01/25 19:37, 8年前 , 11F
我覺得這東西用陳立宇交的方式去算比較簡潔(就三個倒
01/25 19:37, 11F
→
01/25 19:37, 8年前 , 12F
三角形的表格
01/25 19:37, 12F
→
01/25 19:43, 8年前 , 13F
然後差別只是失敗的成本定義
01/25 19:43, 13F
→
01/25 19:45, 8年前 , 14F
dp問題只要搞懂遞迴的由來跟表格大概的長相，ds跟algo
01/25 19:45, 14F
→
01/25 19:45, 8年前 , 15F
這里的差別也只是遞迴差一點點，反正先列出遞迴在作
01/25 19:45, 15F
→
01/25 19:45, 8年前 , 16F
答比較好
01/25 19:45, 16F
→
01/25 19:45, 8年前 , 17F
是林立宇幹我打錯XD
01/25 19:45, 17F
→
01/25 19:46, 8年前 , 18F
而且表格是正三角形的XD
01/25 19:46, 18F
推
01/25 20:08, 8年前 , 19F
我好像只會洪逸的算法欸==一直覺得演算法那個很不直觀
01/25 20:08, 19F
→
01/25 20:08, 8年前 , 20F
，這樣ok嗎？
01/25 20:08, 20F
→
01/25 20:14, 8年前 , 21F
好吧 其實沒關係啦 搞清楚為什麼algo跟ds有什麼差就好
01/25 20:14, 21F
→
01/25 20:14, 8年前 , 22F
然後用你喜歡的算法就好了
01/25 20:14, 22F
推
01/25 22:38, 8年前 , 23F
我也是用林立宇的方法算xd，覺得視覺上比較好記憶
01/25 22:38, 23F
推
01/25 23:05, 8年前 , 24F
原本也是用洪逸的算法，直到遇到10個點的BST.....
01/25 23:05, 24F
推
01/26 00:39, 8年前 , 25F
那可不可以教一下怎麼林立宇算法？哈哈哈以為業配
01/26 00:39, 25F
推
01/26 00:42, 8年前 , 26F
林立宇算法好像就是楓葉本算法
01/26 00:42, 26F
→
01/26 00:43, 8年前 , 27F
去找原文書xdd
01/26 00:43, 27F
→
01/26 00:44, 8年前 , 28F
obst超煩的，有夠難算，但是又會考全套= =
01/26 00:44, 28F
→
01/26 01:02, 8年前 , 29F
其實算法沒什麼差 只是他的那個表格我覺得很乾淨
01/26 01:02, 29F
→
01/26 01:03, 8年前 , 30F
他只是把表格化成三個cost/weight/root
01/26 01:03, 30F
→
01/26 01:03, 8年前 , 31F
然後他定義的cost(i,j)那個ij我覺得比較直覺
01/26 01:03, 31F
→
01/26 01:04, 8年前 , 32F
我記得洪逸的定義cost(i,j)好像是不包含i還是j的OBST
01/26 01:04, 32F
→
01/26 01:06, 8年前 , 33F
我看過的DP的運算 算起來都有一個規律其實就算七八個
01/26 01:06, 33F
→
01/26 01:07, 8年前 , 34F
點的obst 算起來大概也是十分鐘以內就可以完成
01/26 01:07, 34F
→
01/26 01:08, 8年前 , 35F
01/26 01:08, 35F
→
01/26 01:10, 8年前 , 36F
我也是先看洪逸的那個表格看到覺得很痛苦這個舒服多XD
01/26 01:10, 36F
推
01/26 10:34, 8年前 , 37F
樓上在洗三溫暖 （別理我
01/26 10:34, 37F
推
01/26 10:37, 8年前 , 38F
是說~T大你的算法好像就是algo算法 只是擺橫的 無意
01/26 10:37, 38F
→
01/26 10:37, 8年前 , 39F
冒犯
01/26 10:37, 39F
推
01/26 10:55, 8年前 , 40F
是啊，林立宇算法就是algo算法
01/26 10:55, 40F
推
01/26 11:31, 8年前 , 41F
我覺得這一橫擺算起來的感受就有差啦XD
01/26 11:31, 41F
→
01/26 11:54, 8年前 , 42F
我覺得DS跟演算法有重疊的部分還是以演算法為主 DS
01/26 11:54, 42F
→
01/26 11:54, 8年前 , 43F
原文聖經那本本來就很…
01/26 11:54, 43F
推
01/26 12:22, 8年前 , 44F
我也不太喜歡Horowitz那本
01/26 12:22, 44F
推
01/26 14:05, 8年前 , 45F
我剛剛想說很久沒算obst算一下成大那題 11分鐘 真他
01/26 14:05, 45F
→
01/26 14:05, 8年前 , 46F
媽垃圾題目
01/26 14:05, 46F
推
01/26 14:07, 8年前 , 47F
我是看algo之後才看出這個dp算式的規律是啥的
01/26 14:07, 47F
推
01/26 14:45, 8年前 , 48F
怎麼嚕？不就用演算法寫而已嗎？
01/26 14:45, 48F
推
01/26 19:37, 8年前 , 49F
沒啊成大去年考一個七個點的真的算到很煩XD
01/26 19:37, 49F
推
01/26 20:13, 8年前 , 50F
n^3 手算很想死啊
01/26 20:13, 50F
推
01/27 00:13, 8年前 , 51F
沒事沒事 分數拿到 就一生平安！
01/27 00:13, 51F
‣ 更多 MOUOREO 的文章
文章代碼(AID): #1QQLaF9w (Grad-ProbAsk)