→ kyuudonut: (46) 不是喔 greedy algorithm 是必須具 01/03 20:10
→ kyuudonut: optimal structure & greedy choice property 01/03 20:10
→ kyuudonut: *substructure 01/03 20:10
→ kyuudonut: 102-12: 我猜是叫你使用 counting sort 之類的演算法 01/03 20:12
→ kyuudonut: 畢竟 nlogn 是bound在排序 他又有給鍵值範圍 01/03 20:12
→ kyuudonut: (47) 就是他有給網路 要你去算題目定義的optimal path 01/03 20:13
→ kyuudonut: 與 shortest path 是否為同一條 01/03 20:14
→ Transfat: (46)如果沒有optimal substructute怎麼會是greedy呢 01/03 20:26
→ yupog2003: 102第12題，如k大所說，排序須O(|E|)，每次選邊要測試 01/03 20:28
→ yupog2003: 有沒有形成cycle需要a(V)，有|E|個邊，需要O(|E|a(V)) 01/03 20:29
→ yupog2003: O(|E|)+O(|E|a(V))=O(|E|a(V)) 01/03 20:30
→ kyuudonut: 喔喔 我看反了 orz 01/03 20:31
→ yupog2003: a(V)是ackermann的反函數，成長無敵慢 01/03 20:31
→ k2shouai: 46a optimal path就是解了,不是substructure 01/04 00:58
他的optimal path不是應該要把每個s到v的path的w(p)算出來，然後再找最小的嗎？我是
想說他的substructure就是每條path算是一個substructure,然後在再這些substruture
中找到一個最小的（optimal)的，這樣想法是錯的嗎？
推 FRAXIS: 46 其實 shortest path 也可以用 DP 解啊 我選 ACD 01/04 11:20
我沒有選D是因為DP應該要建構在之前的解上面，不過這個每個解（w(P))都是獨立的,並
沒有哪條w(p)是去用到其他條w(p)的值才算出來的，所以我沒選DP
→ FRAXIS: 47 e shortest path 的定義是什麼？ 01/04 11:32
我好像想通了，從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
→ k2shouai: 我是覺得應該要改成optimal solution才對啦 01/04 13:02
推 FRAXIS: 46 Floyd algorithm 是 DP 而且可以解 shortest path 01/04 13:19
→ FRAXIS: 為什麼不選 D ？ 01/04 13:19
因為他是問optimal path不是shortest path哦
→ aa06697: 46不是在解shortest path 01/04 14:52
※ 編輯: Transfat (140.112.25.105), 01/04/2017 16:17:25
→ ken52011219: 雖然之前寫過，但感覺有點詭異 01/04 19:18
→ ken52011219: 這題跟我們說要 w(p) = max{w(v_i,v_j)} 01/04 19:19
→ ken52011219: 又同時說，當w(P)是所有路徑中最小的path 才稱為 01/04 19:20
→ ken52011219: optimal path 01/04 19:21
→ ken52011219: 目前想到一種可能，就是有幾乎所有 w(v_i,v_j)是相同 01/04 19:22
→ ken52011219: 這樣就只剩下C為解了 01/04 19:26
推 FRAXIS: 我認真的看了一下 這問題叫做 minimax path problem 01/04 21:16
→ FRAXIS: 但是我覺得用 DP 也可以解就是了 只是不是最有效率的方法. 01/04 21:16