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