PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 01背包的暴搜有甚麼特別的剪枝嗎?

看板Prob_Solve (計算數學 Problem Solving)作者 (路人甲)時間4年前 (2019/12/11 19:05), 4年前編輯推噓4(4推 0噓 32→)
留言36則, 6人參與, 5年前最新討論串1/1
01背包是假多項式 背包容量超大時無法DP 只能用branch and bound 一般教科書上提到的剪枝的方法: 把物品依照CP值排序 CP值高的先放進去 用貪心法計算upper bound upper bound比較大的點優先擴展 想請問各位大大 還有甚麼特別的方法可以加速嗎? 小弟在修演算法的課 卡一筆測資1000個物品 容量又超大 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.95.72 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1576062326.A.648.html ※ 編輯: s89162504 (223.140.95.72 臺灣), 12/11/2019 19:06:38
→
12/11 19:17, 4年前 , 1F
價值也超大嗎?
12/11 19:17, 1F
→
12/11 19:22, 4年前 , 2F
對啊
12/11 19:22, 2F
→
12/11 19:23, 4年前 , 3F
有推薦類似的OJ題目嗎? 我查到的都還是一般的branch
12/11 19:23, 3F
→
12/11 19:23, 4年前 , 4F
and bound
12/11 19:23, 4F
推
12/12 06:43, 4年前 , 5F
在搜尋前, 給予一個好的初始值, 而非在搜尋過程慢慢
12/12 06:43, 5F
→
12/12 06:43, 4年前 , 6F
更新
12/12 06:43, 6F
推
12/12 06:55, 4年前 , 7F
那麼有較好的初始值後, 總是先選與不選就要看測資的
12/12 06:55, 7F
→
12/12 06:55, 4年前 , 8F
狀況有明顯差異
12/12 06:55, 8F
→
12/12 16:47, 4年前 , 9F
morris的意思是直接用upper bound很高的可行解下去暴搜
12/12 16:47, 9F
→
12/12 16:47, 4年前 , 10F
嗎？
12/12 16:47, 10F
→
12/12 16:48, 4年前 , 11F
可是如果最佳解其實在另一邊 會不會反而做白工啊？
12/12 16:48, 11F
→
12/12 18:49, 4年前 , 12F
聽起來很像是輝哥ㄉ課欸><
12/12 18:49, 12F
→
12/12 19:45, 4年前 , 13F
是喔 補考想把那筆測資過了
12/12 19:45, 13F
→
12/12 20:06, 4年前 , 14F
這一題收錄 批改娘 20005
12/12 20:06, 14F
→
12/12 20:08, 4年前 , 15F
最後的測資我沒讓 bound and branch 的方式通過, 所
12/12 20:08, 15F
→
12/12 20:08, 4年前 , 16F
以拿個 90 分不是問題
12/12 20:08, 16F
→
12/12 20:25, 4年前 , 17F
著重還是在 upper bound 能算多快, 若每次從頭跑到尾
12/12 20:25, 17F
→
12/12 20:25, 4年前 , 18F
那一種就太慢了
12/12 20:25, 18F
→
12/12 20:33, 4年前 , 19F
所以是 目前枚舉到第i項物品 剩餘空間w
12/12 20:33, 19F
→
12/12 20:34, 4年前 , 20F
要事先建一個(i,w)的表嗎?
12/12 20:34, 20F
→
12/12 20:37, 4年前 , 21F
會不會太大了XD
12/12 20:37, 21F
推
12/12 20:56, 4年前 , 22F
沒看到代碼，我不好說可能少哪一塊基礎
12/12 20:56, 22F
→
12/12 20:57, 4年前 , 23F
但是當 n 破萬，你的直接搜會不會是 n^2 估算
12/12 20:57, 23F
→
12/12 21:17, 4年前 , 24F
12/12 21:17, 24F
→
12/12 21:22, 4年前 , 25F
所以目前討論有兩個改善的方向了
12/12 21:22, 25F
→
12/12 21:23, 4年前 , 26F
1 從好一點的點開始 2 改善算上界的方法
12/12 21:23, 26F
→
12/12 21:24, 4年前 , 27F
首先，若全選為最佳解，這樣的總時間為 N^2
12/12 21:24, 27F
→
12/12 21:25, 4年前 , 28F
搜尋空間太大，不應該牽涉到 priority queue
12/12 21:25, 28F
→
12/12 21:26, 4年前 , 29F
直接使用一般的 DFS 搜尋，比較不會讓空間拖累時間
12/12 21:26, 29F
→
12/12 22:44, 4年前 , 30F
優先擴展上界較高的點不是比較好嗎？
12/12 22:44, 30F
→
12/13 07:56, 4年前 , 31F
估算總比預期來得好，意味著找到合法解後，仍有更多
12/13 07:56, 31F
→
12/13 07:56, 4年前 , 32F
的狀態有待搜索，在這種情況空間需求將不切實際
12/13 07:56, 32F
→
12/15 06:48, 4年前 , 33F
單純好奇「容量又超大」具體是多少？
12/15 06:48, 33F
→
12/23 20:10, 4年前 , 34F
感謝各位 看起來是dfs就行了
12/23 20:10, 34F
→
12/23 20:11, 4年前 , 35F
best first search 狀態太大時 每次都logn反而變瓶頸
12/23 20:11, 35F
推
02/28 21:07, 5年前 , 36F
輝哥的課嗎XD
02/28 21:07, 36F
‣ 更多 s89162504 的文章
文章代碼(AID): #1TyCrsP8 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 s89162504 的文章
文章代碼(AID): #1TyCrsP8 (Prob_Solve)