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