[理工] [資工] greedy vs dp

看板Grad-ProbAsk作者 (Eric)時間14年前 (2012/02/07 09:54), 編輯推噓3(3推 0噓 12→)
留言15則, 6人參與, 6年前最新討論串1/1
請問greedy算不算dynamic programming? 多次聽過說算 但剛才寫題目答案給不算 自己的想法是 一樣要由先前的結果堆出來 opt structure大概為 min{所有} 之類的 不過跟divide and conquer沒甚麼關係 請高手說明orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.41.177
推
02/07 10:40, , 1F
同樣疑問+1，求易懂解說，感謝!
02/07 10:40, 1F
→
02/07 10:42, , 2F
自己想法是G只用簡單的模組去找當下最佳，接著往下一階段
02/07 10:42, 2F
→
02/07 10:42, , 3F
DP則驗正了目前該答案為區域最佳，長用表格輔助計算
02/07 10:42, 3F
→
02/07 10:43, , 4F
求高手指點
02/07 10:43, 4F
推
02/07 10:57, , 5F
我記得cormen好像有寫過greedy is a specail case of DP
02/07 10:57, 5F
→
02/07 14:51, , 6F
感謝樓上 goo下去有些相關文句 不過課本還是翻不到orz
02/07 14:51, 6F
→
02/07 19:16, , 7F
我覺得差異是DP有把所有的解考慮進來　然後利用bottom up
02/07 19:16, 7F
→
02/07 19:16, , 8F
方式依序找出每個子問題的最佳解
02/07 19:16, 8F
→
02/07 19:17, , 9F
而greedy並沒有把所有的可能解討論出來
02/07 19:17, 9F
→
02/07 19:20, , 10F
而是相信最佳解就一定包含在所用的演算法中
02/07 19:20, 10F
→
02/07 19:21, , 11F
這是我的想法　也不知道是不是正確
02/07 19:21, 11F
推
02/07 20:08, , 12F
樓上沒錯
02/07 20:08, 12F
→
09/11 14:53, , 13F
而是相信最佳解就一定包 https://daxiv.com
09/11 14:53, 13F
→
02/02 14:36, 6年前 , 14F
02/02 14:36, 14F
→
02/02 14:36, 6年前 , 15F
02/02 14:36, 15F
‣ 更多 onlyeric23 的文章
文章代碼(AID): #1FC8HosE (Grad-ProbAsk)