[理工] 101,102交大DS 三題

看板Grad-ProbAsk作者 (Transfat)時間7年前 (2017/01/03 20:08), 7年前編輯推噓3(3推 0噓 26→)
留言29則, 7人參與, 最新討論串1/1
http://imgur.com/a/H5Y4G 101年交大16. (46)(47) (46) 我在想(a)和(c), 這個如果是每個步驟去找最佳解的話，就算是Greedy, 但是如果 (c)對的話,(a)不也會是對的嗎？答案給(c). 還有(47)的(e)有點不懂他的意思 http://imgur.com/a/BQboq 102 交大第12題，他的第2個空格我沒什麼頭緒 以上，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483445307.A.AB4.html
→
01/03 20:10, , 1F
(46) 不是喔 greedy algorithm 是必須具
01/03 20:10, 1F
→
01/03 20:10, , 2F
optimal structure & greedy choice property
01/03 20:10, 2F
→
01/03 20:10, , 3F
*substructure
01/03 20:10, 3F
→
01/03 20:12, , 4F
102-12: 我猜是叫你使用 counting sort 之類的演算法
01/03 20:12, 4F
→
01/03 20:12, , 5F
畢竟 nlogn 是bound在排序 他又有給鍵值範圍
01/03 20:12, 5F
→
01/03 20:13, , 6F
(47) 就是他有給網路 要你去算題目定義的optimal path
01/03 20:13, 6F
→
01/03 20:14, , 7F
與 shortest path 是否為同一條
01/03 20:14, 7F
→
01/03 20:26, , 8F
(46)如果沒有optimal substructute怎麼會是greedy呢
01/03 20:26, 8F
→
01/03 20:28, , 9F
102第12題，如k大所說，排序須O(|E|)，每次選邊要測試
01/03 20:28, 9F
→
01/03 20:29, , 10F
有沒有形成cycle需要a(V)，有|E|個邊，需要O(|E|a(V))
01/03 20:29, 10F
→
01/03 20:30, , 11F
O(|E|)+O(|E|a(V))=O(|E|a(V))
01/03 20:30, 11F
→
01/03 20:31, , 12F
喔喔 我看反了 orz
01/03 20:31, 12F
→
01/03 20:31, , 13F
a(V)是ackermann的反函數，成長無敵慢
01/03 20:31, 13F
→
01/04 00:58, , 14F
46a optimal path就是解了,不是substructure
01/04 00:58, 14F
他的optimal path不是應該要把每個s到v的path的w(p)算出來，然後再找最小的嗎？我是 想說他的substructure就是每條path算是一個substructure,然後在再這些substruture 中找到一個最小的（optimal)的，這樣想法是錯的嗎？
推
01/04 11:20, , 15F
46 其實 shortest path 也可以用 DP 解啊 我選 ACD
01/04 11:20, 15F
我沒有選D是因為DP應該要建構在之前的解上面，不過這個每個解（w(P))都是獨立的,並 沒有哪條w(p)是去用到其他條w(p)的值才算出來的，所以我沒選DP
→
01/04 11:32, , 16F
47 e shortest path 的定義是什麼？
01/04 11:32, 16F
我好像想通了，從v2到v4的optimal path就是去算max(vi,vi+1)的weight, 這個一定是2, 所以v2到v4的w(p)=2, shortest path是指距離最短，就是從v2直接到v4,所以帶式子＝ [(2-4)*(2-4) mod5]+1=4, 所以這兩條path不是相同的 ※ 編輯: Transfat (140.112.25.105), 01/04/2017 12:19:55 ※ 編輯: Transfat (140.112.25.105), 01/04/2017 12:32:57
→
01/04 13:02, , 17F
我是覺得應該要改成optimal solution才對啦
01/04 13:02, 17F
推
01/04 13:19, , 18F
46 Floyd algorithm 是 DP 而且可以解 shortest path
01/04 13:19, 18F
→
01/04 13:19, , 19F
為什麼不選 D ？
01/04 13:19, 19F
因為他是問optimal path不是shortest path哦
→
01/04 14:52, , 20F
46不是在解shortest path
01/04 14:52, 20F
※ 編輯: Transfat (140.112.25.105), 01/04/2017 16:17:25
→
01/04 19:18, , 21F
雖然之前寫過，但感覺有點詭異
01/04 19:18, 21F
→
01/04 19:19, , 22F
這題跟我們說要 w(p) = max{w(v_i,v_j)}
01/04 19:19, 22F
→
01/04 19:20, , 23F
又同時說，當w(P)是所有路徑中最小的path 才稱為
01/04 19:20, 23F
→
01/04 19:21, , 24F
optimal path
01/04 19:21, 24F
→
01/04 19:22, , 25F
目前想到一種可能，就是有幾乎所有 w(v_i,v_j)是相同
01/04 19:22, 25F
→
01/04 19:26, , 26F
這樣就只剩下C為解了
01/04 19:26, 26F
推
01/04 21:16, , 27F
我認真的看了一下 這問題叫做 minimax path problem
01/04 21:16, 27F
→
01/04 21:16, , 28F
01/04 21:16, 28F
→
01/04 21:16, , 29F
但是我覺得用 DP 也可以解就是了 只是不是最有效率的方法.
01/04 21:16, 29F
‣ 更多 Transfat 的文章
文章代碼(AID): #1OQvGxgq (Grad-ProbAsk)