[商管] 100政大資管 計概

看板Grad-ProbAsk作者 (方塊達人)時間7年前 (2017/01/18 22:32), 7年前編輯推噓4(4推 0噓 25→)
留言29則, 8人參與, 最新討論串1/1
大家好，想問100年政大資管 計概部分 是非題 15.The idea of the Greedy approach is to find the optimum solution by computing the local optimal at each step. 我看洪逸老師題庫班講義答案寫False，但是還是覺得怪怪的，懇請高手指點錯在哪，謝謝！ 再過一下就結束了，各位考生一起加油吧！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.117.91.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484749921.A.EF5.html ※ 編輯: cube65 (122.117.91.203), 01/18/2017 22:33:08
→
01/18 22:37, , 1F
這應該是dynamic programming?
01/18 22:37, 1F
→
01/18 22:44, , 2F
不過DP更強調的是記憶sub problems的結果
01/18 22:44, 2F
→
01/18 22:45, , 3F
Greedy不是算local optimal,是找一個solution (with
01/18 22:45, 3F
→
01/18 22:45, , 4F
Greedy choice, it is as good as optimal solution to
01/18 22:45, 4F
→
01/18 22:45, , 5F
all probelm
01/18 22:45, 5F
→
01/18 22:45, , 6F
感覺這個敘述用在greedy上也說不出錯在哪...
01/18 22:45, 6F
→
01/18 22:46, , 7F
這麼說好了，假如我對0/1KP問題每次都找optimal solutio
01/18 22:46, 7F
→
01/18 22:46, , 8F
n,但是大家都知道0/1KP在每次都找optimal情況下不一定會
01/18 22:46, 8F
→
01/18 22:47, , 9F
是最後的最佳解
01/18 22:47, 9F
→
01/18 23:01, , 10F
照上面大大說法的話，不就是正因為用greedy解0/1背包每次
01/18 23:01, 10F
→
01/18 23:01, , 11F
都找'local optimal '，所以忽略了真正的全域optimal sol
01/18 23:01, 11F
→
01/18 23:01, , 12F
ution ，才必須要改用DP的嗎？
01/18 23:01, 12F
→
01/18 23:15, , 13F
我是把題目解讀成 greedy尋找最佳解的方法是要藉由每個階
01/18 23:15, 13F
→
01/18 23:15, , 14F
段尋找出當時的最佳解，不是很懂這樣哪裡有描述不對的地
01/18 23:15, 14F
→
01/18 23:15, , 15F
方，謝謝大家！
01/18 23:15, 15F
→
01/18 23:24, , 16F
wiki是寫making不是computing
01/18 23:24, 16F
推
01/18 23:54, , 17F
這題我也寫true, 我只有想到greet choice是反覆執行再
01/18 23:54, 17F
→
01/18 23:54, , 18F
找最佳解
01/18 23:54, 18F
推
01/19 16:46, , 19F
我仔細想了一下，課本上說：Makign locally optimal
01/19 16:46, 19F
→
01/19 16:46, , 20F
choices leads to a globally optimal solution.
01/19 16:46, 20F
→
01/19 16:46, , 21F
這句話就是跟題目意思一樣吧，所以我還是選true好了
01/19 16:46, 21F
→
01/19 23:24, , 22F
謝謝分享！
01/19 23:24, 22F
推
01/20 00:17, , 23F
cube65
01/20 00:17, 23F
→
01/20 00:23, , 24F
小弟認為是find optimum solution是錯的 greedy應
01/20 00:23, 24F
→
01/20 00:23, , 25F
該是希望找到最佳解 本意不是用來找最佳解 只是洽好
01/20 00:23, 25F
→
01/20 00:23, , 26F
kruskal prim huffman是!!
01/20 00:23, 26F
→
01/22 16:55, , 27F
有去請教過老師囉，答案是True，留個紀錄給以後的人查詢
01/22 16:55, 27F
→
01/22 16:55, , 28F
，謝謝。
01/22 16:55, 28F
推
01/22 17:31, , 29F
感謝大大解惑
01/22 17:31, 29F
‣ 更多 cube65 的文章
文章代碼(AID): #1OVtnXxr (Grad-ProbAsk)