現(xiàn))
01背包問題是我接觸算法這么多年最常拿來(lái)測(cè)試新思路的“試金石”。它表面簡(jiǎn)單到一句話就能說(shuō)清楚每個(gè)物品要么裝進(jìn)背包、要么不裝在總重量不超過背包容量的前提下讓總價(jià)值盡可能大?？梢坏┪锲窋?shù)量超過幾十個(gè)暴力枚舉立刻變成天文數(shù)字貪心算法快是快卻經(jīng)常在最后一刻給出一個(gè)不是最優(yōu)的答案動(dòng)態(tài)規(guī)劃在容量很大的時(shí)候內(nèi)存和時(shí)間又會(huì)雙雙爆炸。我第一次認(rèn)真研究分支定界算法Branch and Bound就是被這樣一組數(shù)據(jù)逼的物品數(shù)量不算大但背包容量到了千萬(wàn)級(jí)別動(dòng)態(tài)規(guī)劃根本塞不下貪心又無(wú)法保證最優(yōu)。后來(lái)把分支定界吃透才明白這類問題的核心不是“遍歷所有方案”而是如何盡可能少地遍歷。這篇文章從問題建模講起逐步拆解分支定界的三件套——分支、定界、剪枝然后給出一份可以直接跑的 Python 實(shí)現(xiàn)最后聊聊我在不同規(guī)模算例上的實(shí)測(cè)體會(huì)以及它和動(dòng)態(tài)規(guī)劃、回溯法之間到底該怎么選。1. 為什么01背包看起來(lái)簡(jiǎn)單卻容易在數(shù)據(jù)量面前翻車1.1 問題本質(zhì)與數(shù)學(xué)建模先把問題形式化。給定 n 個(gè)物品第 i 個(gè)物品的重量是 w_i、價(jià)值是 v_i背包容量為 C。引入 0-1 決策變量 x_ix_i 1 表示裝入x_i 0 表示不裝那么模型就是最大化Σ v_i * x_i 約束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}注意這里“0-1”是核心它和“分?jǐn)?shù)背包”有本質(zhì)區(qū)別。分?jǐn)?shù)背包允許把一個(gè)物品切開只裝一部分所以貪心按價(jià)值密度從高到低裝就行了。而 01 背包不允許切割一個(gè)物品只有“整件裝”和“整件不裝”兩種狀態(tài)這就導(dǎo)致貪心失效你可能為了裝下一個(gè)密度很高的物品被迫放棄一堆密度稍低但總價(jià)值更大的組合。這種問題的復(fù)雜度屬于 NP 難。從組合數(shù)學(xué)的角度看n 個(gè)物品的選擇方案一共有 2^n 種。n 30 時(shí)是十億級(jí)別n 50 時(shí) 2^50 已經(jīng)超過一千萬(wàn)億普通機(jī)器上直接枚舉是絕對(duì)跑不完的。1.2 貪心失敗現(xiàn)場(chǎng)與動(dòng)態(tài)規(guī)劃的內(nèi)存困境我見過不止一個(gè)初學(xué)者寫完貪心代碼之后對(duì)著結(jié)果發(fā)呆。舉個(gè)反例背包容量 10三個(gè)物品分別為 (重量, 價(jià)值) (6, 6)、(5, 5)、(5, 5)。按價(jià)值密度排序全部一樣貪心先裝第一個(gè)剩余容量 4裝不下任何剩下的總價(jià)值 6?？蓪?shí)際上裝后兩個(gè)總價(jià)值是 10重量剛好也是 10。這就是 01 背包和分?jǐn)?shù)背包最大的區(qū)別它不是一個(gè)“按比例分配”的問題而是一個(gè)“組合取舍”的問題。動(dòng)態(tài)規(guī)劃能保證最優(yōu)時(shí)間復(fù)雜度 O(nC)空間可以滾動(dòng)到 O(C)。問題是這個(gè)復(fù)雜度里的 C 是背包容量不是物品個(gè)數(shù)。我實(shí)際遇到過 n 500、C 5000000 的輸入500 × 500 萬(wàn)就是 25 億次操作內(nèi)存哪怕用滾動(dòng)數(shù)組也要 500 萬(wàn) × 4 字節(jié)約 20MB時(shí)間卻要好幾秒甚至更久。當(dāng)容量繼續(xù)放大到億級(jí)DP 基本就廢了。分支定界算法在這個(gè)場(chǎng)景下就顯得特別有價(jià)值它不依賴容量 C 的大小核心消耗取決于搜索樹的節(jié)點(diǎn)數(shù)。只要上界函數(shù)設(shè)計(jì)得好、剪枝剪得及時(shí)很多大規(guī)模實(shí)例在極短時(shí)間就能出最優(yōu)解。這也是我決定深入實(shí)現(xiàn)它的原因。2. 分支定界的三件套分支、定界與剪枝的完整邏輯2.1 解空間樹把“選/不選”鋪成一棵二叉樹分支定界的第一步是把所有可能方案組織成一棵樹。樹的每一層對(duì)應(yīng)一個(gè)物品的決策節(jié)點(diǎn)從根節(jié)點(diǎn)出發(fā)左分支表示“裝入當(dāng)前物品”右分支表示“不裝當(dāng)前物品”。走到葉子節(jié)點(diǎn)就得到一組完整的 0-1 選擇方案。n 個(gè)物品的解空間樹一共有 2^(n1) - 1 個(gè)節(jié)點(diǎn)葉子數(shù)是 2^n。直接遍歷這棵樹就是回溯法復(fù)雜度指數(shù)級(jí)。分支定界和樸素回溯的本質(zhì)區(qū)別在于回溯法把所有葉子都走一遍才能確定最優(yōu)解而分支定界在每個(gè)內(nèi)部節(jié)點(diǎn)先估算“如果繼續(xù)往下走最高能拿到多少價(jià)值”一旦這個(gè)估算值比當(dāng)前已知最優(yōu)解還要差就果斷砍掉整個(gè)子樹根本不用進(jìn)去。2.2 定界的幾何直覺先假設(shè)“能切開”再慢慢收緊分支定界里上界函數(shù)是整個(gè)算法的靈魂。常見的做法是把 01 背包“松弛”成連續(xù)背包問題允許當(dāng)前節(jié)點(diǎn)后面的物品按任意比例裝入。因?yàn)榧s束放寬了松弛問題的最優(yōu)解一定不小于原問題任何一個(gè)可行解的價(jià)值所以它可以作為原問題的合法上界。這個(gè)上界還有一個(gè)特別好的性質(zhì)連續(xù)背包問題用貪心就能解。把剩余物品按價(jià)值密度從高到低排好能整件裝的先整件裝裝到最后一個(gè)物品時(shí)如果剩余容量不夠就按比例取一部分。算出來(lái)的總價(jià)值就是當(dāng)前節(jié)點(diǎn)繼續(xù)往下探索的價(jià)值天花板。更有意思的是整數(shù)取整。如果所有價(jià)值和重量都是正整數(shù)那么任意一個(gè)整數(shù)可行解的價(jià)值必然是整數(shù)而上界如果是 13.67那它真正的整數(shù)上界最多是 13。把上界向下取整在實(shí)際剪枝中往往能多砍掉相當(dāng)一部分節(jié)點(diǎn)。2.3 三個(gè)可以剪枝的地方別漏掉任何一個(gè)我用一個(gè)具體例子演示。假設(shè) 4 個(gè)物品(重量, 價(jià)值) (2, 3)、(3, 4)、(4, 5)、(5, 8)背包容量 9。所有方案里最優(yōu)的是裝物品 3 和物品 4總重量 9總價(jià)值 13。首先按價(jià)值密度從大到小排序排序后順序是物品 4密度 1.6、物品 1密度 1.5、物品 2密度 1.33、物品 3密度 1.25。根節(jié)點(diǎn)的上界按密度裝滿 9 容量物品 4 整裝、物品 1 整裝剩 2 容量只能裝 2/3 個(gè)物品 2上界 8 3 4×2/3 ≈ 13.67取整為 13。初始最優(yōu)解 best_value 設(shè)為 0開始深度優(yōu)先搜索。整個(gè)過程可以簡(jiǎn)化成下面這棵文本樹根節(jié)點(diǎn)上界13 ├─ 左裝物品4重量5價(jià)值8上界13 │ ├─ 左裝物品1重量7價(jià)值11上界13 │ │ └─ 右不裝物品2之后只能走到價(jià)值11best更新為11 │ └─ 右不裝物品1重量5價(jià)值8上界13 │ ├─ 左裝物品2重量8價(jià)值12best更新為12 │ └─ 右不裝物品2重量5價(jià)值8 │ └─ 左裝物品3重量9價(jià)值13best更新為13 └─ 右不裝物品4上界 345 1212 ≤ best13剪枝可以看到右分支在根節(jié)點(diǎn)就被砍掉了因?yàn)椴还芎竺嬖趺催x價(jià)值都不可能超過 12。整個(gè)搜索只訪問了 12 個(gè)節(jié)點(diǎn)而樸素回溯會(huì)訪問全部 31 個(gè)節(jié)點(diǎn)。當(dāng) n 變大這種差距會(huì)被指數(shù)級(jí)放大。3. 上界函數(shù)的底層思考連續(xù)背包松弛為什么能用、怎么用3.1 線性規(guī)劃松弛允許“半個(gè)物品”的妙處很多人第一次看到連續(xù)背包松弛都會(huì)有一個(gè)疑問明明 01 背包不允許裝半個(gè)物品為什么拿“允許裝半個(gè)”的模型來(lái)當(dāng)上界不會(huì)給出錯(cuò)誤的剪枝判斷關(guān)鍵在于“上界”的性質(zhì)。我們要保證一件事任何從當(dāng)前節(jié)點(diǎn)出發(fā)的完整方案其價(jià)值都不可能超過上界函數(shù)算出來(lái)的值。連續(xù)背包問題的可行域比 01 背包更大所有整數(shù)可行解都是松弛問題的可行解。因此松弛問題的最優(yōu)值一定是整數(shù)問題最優(yōu)值的上界這個(gè)邏輯是嚴(yán)格成立的。用一句話概括放寬約束只會(huì)讓最優(yōu)值變大絕不會(huì)變小所以它是一個(gè)“不會(huì)漏掉最優(yōu)解”的天花板。連續(xù)背包問題的貪心最優(yōu)性也可以用交換論證來(lái)理解假設(shè)有兩個(gè)物品 A 和 BA 的密度比 B 高。如果一個(gè)可行解里裝了 B 的一部分重量 d卻在 A 還沒裝滿時(shí)留有空位那么把 d 這部分重量換成等重的 A重量不變、價(jià)值更高。反復(fù)做這種交換最終的形態(tài)必然是密度從高到低裝滿所以貪心順序正確。3.2 從13.67到13取整技巧帶來(lái)的額外剪枝力取整技巧非常實(shí)用但有兩件事必須注意。第一只有所有物品的價(jià)值、重量都是整數(shù)時(shí)才能放心對(duì) bound 向下取整。整數(shù)可行解的價(jià)值累加后必然是整數(shù)而連續(xù)松弛上界哪怕算出 13.67實(shí)際上你最多能湊出的整數(shù)價(jià)值也不會(huì)超過 13?？扇绻锲穬r(jià)值本身是浮點(diǎn)數(shù)直接 int() 可能會(huì)把上界截到一個(gè)不可達(dá)的下方造成誤剪枝。我在實(shí)現(xiàn)里默認(rèn)所有輸入都是正整數(shù)所以會(huì)用int(bound(...)) best_value作剪枝條件如果碰到浮點(diǎn)價(jià)值改成bound(...) best_value 1e-9更穩(wěn)妥。第二取整時(shí)必須向下取整不能四舍五入。13.67 四舍五入成 14 之后上界被抬高了剪枝條件變得更難滿足等于削弱算法效果向下取整才是安全的緊化。3.3 上界計(jì)算的代碼實(shí)現(xiàn)要點(diǎn)上界函數(shù)的實(shí)現(xiàn)邏輯很直白def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper一個(gè)容易被忽略的性能優(yōu)化當(dāng)剩余容量還能裝下從 start 到末尾的所有物品時(shí)按密度貪心并沒有意義此時(shí)上界就是當(dāng)前價(jià)值加上剩余物品價(jià)值總和。這行判斷可以用后綴和數(shù)組提前算好雖然能省的時(shí)間不多但在節(jié)點(diǎn)數(shù)上百萬(wàn)時(shí)能減少不少浮點(diǎn)乘除和循環(huán)開銷。另外要強(qiáng)調(diào)上界函數(shù)計(jì)算越緊剪枝效果越好但計(jì)算量也會(huì)增大。連續(xù)背包松弛是目前性價(jià)比最高的選擇它只需要一次線性掃描還能配合我們已經(jīng)做好的密度排序直接使用不需要額外數(shù)據(jù)結(jié)構(gòu)的維護(hù)。4. 一份能跑的Python求解器實(shí)現(xiàn)與核心代碼逐段拆解4.1 預(yù)處理為什么必須先按價(jià)值密度排序分支定界對(duì)物品做密度降序排序有三個(gè)好處一是上界函數(shù)計(jì)算連續(xù)背包解時(shí)天然依賴密度從高到低的順序排序之后直接按順序掃描即可。二是在搜索過程中先考慮密度高的物品更容易在早期形成質(zhì)量較好的可行解。比如根節(jié)點(diǎn)左邊分支裝上密度最高的物品往往很快就逼近最優(yōu)值best_value 提升得快后續(xù)剪枝條件更容易滿足。三是排序不會(huì)改變最優(yōu)解本身因?yàn)榻饪臻g本質(zhì)上是在枚舉所有 0-1 組合順序調(diào)整并不影響組合的完整性。我在代碼中使用(weights[i], values[i], i)三元組保存原始下標(biāo)排序時(shí)只排三元組列表這樣排序后依然能回溯每個(gè)物品的原始位置最終構(gòu)造出正確的選擇掩碼。4.2 深度優(yōu)先搜索與剪枝代碼完整求解器如下def solve_01knapsack_bnb(weights, values, capacity): n len(weights) items sorted( [(weights[i], values[i], i) for i in range(n)], keylambda x: x[1] / x[0], reverseTrue ) best_value 0 best_mask [0] * n node_count 0 def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper def dfs(idx, cur_w, cur_v, chosen): nonlocal best_value, best_mask, node_count node_count 1 if cur_v best_value: best_value cur_v best_mask [0] * n for orig in chosen: best_mask[orig] 1 if idx n: return if int(bound(idx, cur_w, cur_v)) best_value: return w, v, orig_i items[idx] if cur_w w capacity: dfs(idx 1, cur_w w, cur_v v, chosen [orig_i]) dfs(idx 1, cur_w, cur_v, chosen) dfs(0, 0, 0, []) return best_value, best_mask, node_count代碼里有一個(gè)容易被忽略的順序進(jìn)入節(jié)點(diǎn)后先做“價(jià)值更新”再做“上界剪枝”。這樣設(shè)計(jì)是有意的。當(dāng)遞歸從更深層返回到當(dāng)前節(jié)點(diǎn)時(shí)全局 best_value 可能已經(jīng)被某個(gè)可行解刷新過了此時(shí)再算上界剪枝才有意義。如果先剪枝再更新部分子樹就可能被一個(gè)偏低的 best_value 錯(cuò)誤放過導(dǎo)致整體搜索量變大。4.3 記錄最優(yōu)解從chosen列表到最終掩碼很多教程只返回最優(yōu)值不返回選中的物品集合這對(duì)實(shí)際項(xiàng)目來(lái)說(shuō)不夠用。我用chosen列表保存從根到當(dāng)前節(jié)點(diǎn)“裝入”的物品的原始下標(biāo)每當(dāng)找到一個(gè)更優(yōu)價(jià)值時(shí)就重新生成一個(gè)長(zhǎng)度為 n 的全 0 掩碼把 chosen 里的下標(biāo)都置為 1。這種方式邏輯清晰代價(jià)是每次更新最優(yōu)解都要 O(n) 復(fù)制數(shù)組。當(dāng) n 達(dá)到幾萬(wàn)時(shí)頻繁更新可能拖慢速度。另一種做法是維護(hù)一個(gè)和物品數(shù)等長(zhǎng)的選擇數(shù)組在遞歸中用“選/不選”原位更新葉子節(jié)點(diǎn)時(shí)統(tǒng)一拷貝一次。我推薦先跑通當(dāng)前版本再根據(jù)性能瓶頸決定要不要優(yōu)化。4.4 標(biāo)準(zhǔn)算例演示用之前的例子驗(yàn)證weights [2, 3, 4, 5] values [3, 4, 5, 8] capacity 9 value, mask, count solve_01knapsack_bnb(weights, values, capacity) print(最優(yōu)價(jià)值:, value) print(選擇掩碼:, mask) print(物品原始下標(biāo):, [i for i, x in enumerate(mask) if x 1]) print(探索節(jié)點(diǎn)數(shù):, count)輸出應(yīng)該是最優(yōu)價(jià)值: 13 選擇掩碼: [0, 0, 1, 1] 物品原始下標(biāo): [2, 3] 探索節(jié)點(diǎn)數(shù): 12注意掩碼[0, 0, 1, 1]對(duì)應(yīng)原始物品 3 和物品 4總重量 4 5 9總價(jià)值 5 8 13。整個(gè)搜索只訪問 12 個(gè)節(jié)點(diǎn)遠(yuǎn)小于 31 個(gè)節(jié)點(diǎn)的全遍歷量。5. 大規(guī)模實(shí)測(cè)分支定界、動(dòng)態(tài)規(guī)劃與回溯法的選型邊界5.1 節(jié)點(diǎn)數(shù)與上界質(zhì)量的關(guān)聯(lián)分支定界的實(shí)際表現(xiàn)高度依賴數(shù)據(jù)特征我把它分成兩類典型場(chǎng)景。一類是“強(qiáng)相關(guān)”數(shù)據(jù)。價(jià)值與重量強(qiáng)相關(guān)比如價(jià)值 2 × 重量 隨機(jī)小擾動(dòng)。這種情況下連續(xù)背包松弛算出的上界和真正整數(shù)最優(yōu)解非常接近剪枝異常迅猛。我實(shí)測(cè)過 n 200、容量 5000 的強(qiáng)相關(guān)數(shù)據(jù)很多情況下節(jié)點(diǎn)數(shù)只有幾千毫秒級(jí)出結(jié)果。另一類是“弱相關(guān)”數(shù)據(jù)。價(jià)值和重量基本獨(dú)立隨機(jī)生成比如重量隨機(jī)取 1 到 100價(jià)值隨機(jī)取 1 到 200。此時(shí)連續(xù)背包松弛的上界會(huì)明顯虛高剪枝能力大幅下降節(jié)點(diǎn)數(shù)可能膨脹到幾十萬(wàn)甚至百萬(wàn)級(jí)。n 60、容量 1500 的弱相關(guān)數(shù)據(jù)就要做好它跑好幾秒的心理準(zhǔn)備而同樣數(shù)據(jù)用動(dòng)態(tài)規(guī)劃 O(60×1500) 只要一個(gè) O(nC) 小表就解決了。所以分支定界并不是“更快的最優(yōu)求解器”它是“在某些數(shù)據(jù)分布下特別高效的最優(yōu)求解器”。動(dòng)手之前先看一下你的數(shù)據(jù)是重相關(guān)還是弱相關(guān)才能判斷要不要選它。5.2 分支定界、動(dòng)態(tài)規(guī)劃、回溯暴力的適用邊界對(duì)照我把三種精確求解方法放在一張表里比較方法時(shí)間復(fù)雜度空間復(fù)雜度強(qiáng)項(xiàng)明顯短板回溯暴力最壞 O(2^n)O(n)實(shí)現(xiàn)最簡(jiǎn)單幾乎不剪枝n 30 就吃力分支定界平均遠(yuǎn)小于 2^n最壞 O(2^n)O(n)遞歸棧不依賴容量數(shù)據(jù)強(qiáng)相關(guān)時(shí)極快弱相關(guān)數(shù)據(jù)可能退化指數(shù)級(jí)動(dòng)態(tài)規(guī)劃O(nC)O(C) 可滾動(dòng)穩(wěn)定可預(yù)測(cè)小容量場(chǎng)景最優(yōu)容量 C 大時(shí)內(nèi)存和耗時(shí)爆掉從工程角度我一般這樣選型容量 C 和物品種類 n 都在可接受范圍直接上 DP穩(wěn)定省心。C 特別大、但物品數(shù)據(jù)有明顯密度差異上分支定界。數(shù)據(jù)是弱相關(guān)隨機(jī)且 n 很大那就別硬剛精確解考慮啟發(fā)式近似算法更現(xiàn)實(shí)。5.3 我踩過的一個(gè)遞歸大坑用 Python 寫 DFS 分支定界時(shí)有一個(gè)隱藏地雷遞歸深度。n 達(dá)到 1000 以上時(shí)默認(rèn)遞歸上限很容易爆出RecursionError。解決辦法有兩個(gè)一是在腳本開頭設(shè)置sys.setrecursionlimit(10000)二是改用顯式棧。顯式棧還有一個(gè)額外好處棧節(jié)點(diǎn)可以動(dòng)態(tài)排序方便實(shí)現(xiàn)后面要說(shuō)的最佳優(yōu)先搜索。不過代價(jià)是代碼復(fù)雜度明顯上升。如果你只是處理幾百個(gè)物品遞歸版本足夠沒必要一開始就寫顯式棧。6. 進(jìn)階玩法Best-First搜索、下界強(qiáng)化與并行注意點(diǎn)6.1 最佳優(yōu)先搜索優(yōu)先處理最有希望的節(jié)點(diǎn)深度優(yōu)先搜索的優(yōu)點(diǎn)是內(nèi)存小但它的“搜索路線”有時(shí)很盲目明明某個(gè)節(jié)點(diǎn)的上界非常高卻因?yàn)檫f歸路徑的關(guān)系被排到很晚才處理反而一些上界很低的節(jié)點(diǎn)卻因?yàn)槌霈F(xiàn)在遞歸路徑上被優(yōu)先擴(kuò)展了。Best-First 策略用一個(gè)優(yōu)先隊(duì)列替代遞歸棧每次取出上界最高的節(jié)點(diǎn)擴(kuò)展。這樣做的直接好處是算法會(huì)非常快地走到一條高質(zhì)量路徑并迅速刷新全局最優(yōu)解。全局最優(yōu)解變緊之后其他節(jié)點(diǎn)的剪枝條件也就更容易滿足。代價(jià)是優(yōu)先隊(duì)列需要保存大量節(jié)點(diǎn)最壞情況下內(nèi)存會(huì)指數(shù)增長(zhǎng)。我通常只在解空間特別大、且上界質(zhì)量參差不齊時(shí)使用 Best-First。6.2 下界強(qiáng)化起步時(shí)用一個(gè)好一點(diǎn)的初值很多實(shí)現(xiàn)把初始 best_value 設(shè)為 0這其實(shí)浪費(fèi)了第一波剪枝機(jī)會(huì)。簡(jiǎn)單的改進(jìn)是先跑一遍貪心算法把一個(gè)可行解的價(jià)值作為初始下界。貪心解雖然不一定最優(yōu)但往往不會(huì)太差尤其強(qiáng)相關(guān)數(shù)據(jù)下可能已經(jīng)非常接近最優(yōu)值。這樣搜索一開始就有了一把還算緊的尺子剪枝效率立即提升。更激進(jìn)的做法是在每個(gè)節(jié)點(diǎn)內(nèi)部再做一次局部貪心基于當(dāng)前已選物品繼續(xù)往后挑選可行解得到一個(gè)更精細(xì)的下界。但節(jié)點(diǎn)內(nèi)部貪心會(huì)增加計(jì)算成本對(duì)于節(jié)點(diǎn)數(shù)已經(jīng)很少的強(qiáng)相關(guān)數(shù)據(jù)收益不大對(duì)于弱相關(guān)數(shù)據(jù)單純加一個(gè)啟發(fā)式下界也救不了虛高的上界。所以我的建議是先用全局貪心當(dāng)初始下界跑一輪看效果再?zèng)Q定要不要加節(jié)點(diǎn)級(jí)啟發(fā)式。6.3 并行化的現(xiàn)實(shí)考量分支定界天然適合并行根節(jié)點(diǎn)的左右分支彼此獨(dú)立可以分給不同工作線程去搜索。工程上需要維護(hù)一個(gè)全局共享的 best_value任意工作線程發(fā)現(xiàn)更優(yōu)可行解就原子更新其他線程在剪枝判斷時(shí)讀取這個(gè)全局下界。但并行分支定界有一個(gè)典型的坑全局 best 更新可能有延遲某個(gè)線程在上界已經(jīng)能剪枝時(shí)因?yàn)樽x到的 best 偏小白白多搜了一整棵子樹。要緩解這個(gè)問題可以讓工作線程定期同步全局 best同時(shí)在每個(gè)子樹搜索開始時(shí)重新讀取一次。實(shí)際經(jīng)驗(yàn)是并行只能應(yīng)對(duì)“弱相關(guān)大實(shí)例”帶來(lái)的節(jié)點(diǎn)爆炸而且加速比并不線性很多時(shí)候 8 核只跑出 3 到 4 倍提升。如果節(jié)點(diǎn)數(shù)不大并行反而因?yàn)榫€程同步開銷變慢。我建議先把單核版本調(diào)到足夠好再考慮并行。最后分享兩個(gè)開發(fā)小技巧。第一實(shí)現(xiàn)分支定界時(shí)先寫一個(gè)完全不帶剪枝的回溯版配合小規(guī)模暴力枚舉或 DP 驗(yàn)證正確性然后再加 bound 和剪枝一步一確認(rèn)。第二步專注調(diào)試剪枝條件不然上界函數(shù)出錯(cuò)時(shí)很難定位是“剪錯(cuò)了最優(yōu)解”還是“搜索路徑本身有 bug”。第二調(diào)優(yōu)時(shí)把 node_count 打印出來(lái)觀察剪枝前后節(jié)點(diǎn)數(shù)的變化。如果加了剪枝之后節(jié)點(diǎn)數(shù)還和暴力幾乎一樣八成是上界太松或者排序沒生效這時(shí)候再回頭檢查上界函數(shù)比盲目加并行要有效得多。 01背包問題的高效求解：分支定界算法原理與Python實(shí)現(xiàn)
01背包問題是我接觸算法這么多年最常拿來(lái)測(cè)試新思路的“試金石”。它表面簡(jiǎn)單到一句話就能說(shuō)清楚每個(gè)物品要么裝進(jìn)背包、要么不裝在總重量不超過背包容量的前提下讓總價(jià)值盡可能大?？梢坏┪锲窋?shù)量超過幾十個(gè)暴力枚舉立刻變成天文數(shù)字貪心算法快是快卻經(jīng)常在最后一刻給出一個(gè)不是最優(yōu)的答案動(dòng)態(tài)規(guī)劃在容量很大的時(shí)候內(nèi)存和時(shí)間又會(huì)雙雙爆炸。我第一次認(rèn)真研究分支定界算法Branch and Bound就是被這樣一組數(shù)據(jù)逼的物品數(shù)量不算大但背包容量到了千萬(wàn)級(jí)別動(dòng)態(tài)規(guī)劃根本塞不下貪心又無(wú)法保證最優(yōu)。后來(lái)把分支定界吃透才明白這類問題的核心不是“遍歷所有方案”而是如何盡可能少地遍歷。這篇文章從問題建模講起逐步拆解分支定界的三件套——分支、定界、剪枝然后給出一份可以直接跑的 Python 實(shí)現(xiàn)最后聊聊我在不同規(guī)模算例上的實(shí)測(cè)體會(huì)以及它和動(dòng)態(tài)規(guī)劃、回溯法之間到底該怎么選。1. 為什么01背包看起來(lái)簡(jiǎn)單卻容易在數(shù)據(jù)量面前翻車1.1 問題本質(zhì)與數(shù)學(xué)建模先把問題形式化。給定 n 個(gè)物品第 i 個(gè)物品的重量是 w_i、價(jià)值是 v_i背包容量為 C。引入 0-1 決策變量 x_ix_i 1 表示裝入x_i 0 表示不裝那么模型就是最大化Σ v_i * x_i 約束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}注意這里“0-1”是核心它和“分?jǐn)?shù)背包”有本質(zhì)區(qū)別。分?jǐn)?shù)背包允許把一個(gè)物品切開只裝一部分所以貪心按價(jià)值密度從高到低裝就行了。而 01 背包不允許切割一個(gè)物品只有“整件裝”和“整件不裝”兩種狀態(tài)這就導(dǎo)致貪心失效你可能為了裝下一個(gè)密度很高的物品被迫放棄一堆密度稍低但總價(jià)值更大的組合。這種問題的復(fù)雜度屬于 NP 難。從組合數(shù)學(xué)的角度看n 個(gè)物品的選擇方案一共有 2^n 種。n 30 時(shí)是十億級(jí)別n 50 時(shí) 2^50 已經(jīng)超過一千萬(wàn)億普通機(jī)器上直接枚舉是絕對(duì)跑不完的。1.2 貪心失敗現(xiàn)場(chǎng)與動(dòng)態(tài)規(guī)劃的內(nèi)存困境我見過不止一個(gè)初學(xué)者寫完貪心代碼之后對(duì)著結(jié)果發(fā)呆。舉個(gè)反例背包容量 10三個(gè)物品分別為 (重量, 價(jià)值) (6, 6)、(5, 5)、(5, 5)。按價(jià)值密度排序全部一樣貪心先裝第一個(gè)剩余容量 4裝不下任何剩下的總價(jià)值 6?？蓪?shí)際上裝后兩個(gè)總價(jià)值是 10重量剛好也是 10。這就是 01 背包和分?jǐn)?shù)背包最大的區(qū)別它不是一個(gè)“按比例分配”的問題而是一個(gè)“組合取舍”的問題。動(dòng)態(tài)規(guī)劃能保證最優(yōu)時(shí)間復(fù)雜度 O(nC)空間可以滾動(dòng)到 O(C)。問題是這個(gè)復(fù)雜度里的 C 是背包容量不是物品個(gè)數(shù)。我實(shí)際遇到過 n 500、C 5000000 的輸入500 × 500 萬(wàn)就是 25 億次操作內(nèi)存哪怕用滾動(dòng)數(shù)組也要 500 萬(wàn) × 4 字節(jié)約 20MB時(shí)間卻要好幾秒甚至更久。當(dāng)容量繼續(xù)放大到億級(jí)DP 基本就廢了。分支定界算法在這個(gè)場(chǎng)景下就顯得特別有價(jià)值它不依賴容量 C 的大小核心消耗取決于搜索樹的節(jié)點(diǎn)數(shù)。只要上界函數(shù)設(shè)計(jì)得好、剪枝剪得及時(shí)很多大規(guī)模實(shí)例在極短時(shí)間就能出最優(yōu)解。這也是我決定深入實(shí)現(xiàn)它的原因。2. 分支定界的三件套分支、定界與剪枝的完整邏輯2.1 解空間樹把“選/不選”鋪成一棵二叉樹分支定界的第一步是把所有可能方案組織成一棵樹。樹的每一層對(duì)應(yīng)一個(gè)物品的決策節(jié)點(diǎn)從根節(jié)點(diǎn)出發(fā)左分支表示“裝入當(dāng)前物品”右分支表示“不裝當(dāng)前物品”。走到葉子節(jié)點(diǎn)就得到一組完整的 0-1 選擇方案。n 個(gè)物品的解空間樹一共有 2^(n1) - 1 個(gè)節(jié)點(diǎn)葉子數(shù)是 2^n。直接遍歷這棵樹就是回溯法復(fù)雜度指數(shù)級(jí)。分支定界和樸素回溯的本質(zhì)區(qū)別在于回溯法把所有葉子都走一遍才能確定最優(yōu)解而分支定界在每個(gè)內(nèi)部節(jié)點(diǎn)先估算“如果繼續(xù)往下走最高能拿到多少價(jià)值”一旦這個(gè)估算值比當(dāng)前已知最優(yōu)解還要差就果斷砍掉整個(gè)子樹根本不用進(jìn)去。2.2 定界的幾何直覺先假設(shè)“能切開”再慢慢收緊分支定界里上界函數(shù)是整個(gè)算法的靈魂。常見的做法是把 01 背包“松弛”成連續(xù)背包問題允許當(dāng)前節(jié)點(diǎn)后面的物品按任意比例裝入。因?yàn)榧s束放寬了松弛問題的最優(yōu)解一定不小于原問題任何一個(gè)可行解的價(jià)值所以它可以作為原問題的合法上界。這個(gè)上界還有一個(gè)特別好的性質(zhì)連續(xù)背包問題用貪心就能解。把剩余物品按價(jià)值密度從高到低排好能整件裝的先整件裝裝到最后一個(gè)物品時(shí)如果剩余容量不夠就按比例取一部分。算出來(lái)的總價(jià)值就是當(dāng)前節(jié)點(diǎn)繼續(xù)往下探索的價(jià)值天花板。更有意思的是整數(shù)取整。如果所有價(jià)值和重量都是正整數(shù)那么任意一個(gè)整數(shù)可行解的價(jià)值必然是整數(shù)而上界如果是 13.67那它真正的整數(shù)上界最多是 13。把上界向下取整在實(shí)際剪枝中往往能多砍掉相當(dāng)一部分節(jié)點(diǎn)。2.3 三個(gè)可以剪枝的地方別漏掉任何一個(gè)我用一個(gè)具體例子演示。假設(shè) 4 個(gè)物品(重量, 價(jià)值) (2, 3)、(3, 4)、(4, 5)、(5, 8)背包容量 9。所有方案里最優(yōu)的是裝物品 3 和物品 4總重量 9總價(jià)值 13。首先按價(jià)值密度從大到小排序排序后順序是物品 4密度 1.6、物品 1密度 1.5、物品 2密度 1.33、物品 3密度 1.25。根節(jié)點(diǎn)的上界按密度裝滿 9 容量物品 4 整裝、物品 1 整裝剩 2 容量只能裝 2/3 個(gè)物品 2上界 8 3 4×2/3 ≈ 13.67取整為 13。初始最優(yōu)解 best_value 設(shè)為 0開始深度優(yōu)先搜索。整個(gè)過程可以簡(jiǎn)化成下面這棵文本樹根節(jié)點(diǎn)上界13 ├─ 左裝物品4重量5價(jià)值8上界13 │ ├─ 左裝物品1重量7價(jià)值11上界13 │ │ └─ 右不裝物品2之后只能走到價(jià)值11best更新為11 │ └─ 右不裝物品1重量5價(jià)值8上界13 │ ├─ 左裝物品2重量8價(jià)值12best更新為12 │ └─ 右不裝物品2重量5價(jià)值8 │ └─ 左裝物品3重量9價(jià)值13best更新為13 └─ 右不裝物品4上界 345 1212 ≤ best13剪枝可以看到右分支在根節(jié)點(diǎn)就被砍掉了因?yàn)椴还芎竺嬖趺催x價(jià)值都不可能超過 12。整個(gè)搜索只訪問了 12 個(gè)節(jié)點(diǎn)而樸素回溯會(huì)訪問全部 31 個(gè)節(jié)點(diǎn)。當(dāng) n 變大這種差距會(huì)被指數(shù)級(jí)放大。3. 上界函數(shù)的底層思考連續(xù)背包松弛為什么能用、怎么用3.1 線性規(guī)劃松弛允許“半個(gè)物品”的妙處很多人第一次看到連續(xù)背包松弛都會(huì)有一個(gè)疑問明明 01 背包不允許裝半個(gè)物品為什么拿“允許裝半個(gè)”的模型來(lái)當(dāng)上界不會(huì)給出錯(cuò)誤的剪枝判斷關(guān)鍵在于“上界”的性質(zhì)。我們要保證一件事任何從當(dāng)前節(jié)點(diǎn)出發(fā)的完整方案其價(jià)值都不可能超過上界函數(shù)算出來(lái)的值。連續(xù)背包問題的可行域比 01 背包更大所有整數(shù)可行解都是松弛問題的可行解。因此松弛問題的最優(yōu)值一定是整數(shù)問題最優(yōu)值的上界這個(gè)邏輯是嚴(yán)格成立的。用一句話概括放寬約束只會(huì)讓最優(yōu)值變大絕不會(huì)變小所以它是一個(gè)“不會(huì)漏掉最優(yōu)解”的天花板。連續(xù)背包問題的貪心最優(yōu)性也可以用交換論證來(lái)理解假設(shè)有兩個(gè)物品 A 和 BA 的密度比 B 高。如果一個(gè)可行解里裝了 B 的一部分重量 d卻在 A 還沒裝滿時(shí)留有空位那么把 d 這部分重量換成等重的 A重量不變、價(jià)值更高。反復(fù)做這種交換最終的形態(tài)必然是密度從高到低裝滿所以貪心順序正確。3.2 從13.67到13取整技巧帶來(lái)的額外剪枝力取整技巧非常實(shí)用但有兩件事必須注意。第一只有所有物品的價(jià)值、重量都是整數(shù)時(shí)才能放心對(duì) bound 向下取整。整數(shù)可行解的價(jià)值累加后必然是整數(shù)而連續(xù)松弛上界哪怕算出 13.67實(shí)際上你最多能湊出的整數(shù)價(jià)值也不會(huì)超過 13?？扇绻锲穬r(jià)值本身是浮點(diǎn)數(shù)直接 int() 可能會(huì)把上界截到一個(gè)不可達(dá)的下方造成誤剪枝。我在實(shí)現(xiàn)里默認(rèn)所有輸入都是正整數(shù)所以會(huì)用int(bound(...)) best_value作剪枝條件如果碰到浮點(diǎn)價(jià)值改成bound(...) best_value 1e-9更穩(wěn)妥。第二取整時(shí)必須向下取整不能四舍五入。13.67 四舍五入成 14 之后上界被抬高了剪枝條件變得更難滿足等于削弱算法效果向下取整才是安全的緊化。3.3 上界計(jì)算的代碼實(shí)現(xiàn)要點(diǎn)上界函數(shù)的實(shí)現(xiàn)邏輯很直白def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper一個(gè)容易被忽略的性能優(yōu)化當(dāng)剩余容量還能裝下從 start 到末尾的所有物品時(shí)按密度貪心并沒有意義此時(shí)上界就是當(dāng)前價(jià)值加上剩余物品價(jià)值總和。這行判斷可以用后綴和數(shù)組提前算好雖然能省的時(shí)間不多但在節(jié)點(diǎn)數(shù)上百萬(wàn)時(shí)能減少不少浮點(diǎn)乘除和循環(huán)開銷。另外要強(qiáng)調(diào)上界函數(shù)計(jì)算越緊剪枝效果越好但計(jì)算量也會(huì)增大。連續(xù)背包松弛是目前性價(jià)比最高的選擇它只需要一次線性掃描還能配合我們已經(jīng)做好的密度排序直接使用不需要額外數(shù)據(jù)結(jié)構(gòu)的維護(hù)。4. 一份能跑的Python求解器實(shí)現(xiàn)與核心代碼逐段拆解4.1 預(yù)處理為什么必須先按價(jià)值密度排序分支定界對(duì)物品做密度降序排序有三個(gè)好處一是上界函數(shù)計(jì)算連續(xù)背包解時(shí)天然依賴密度從高到低的順序排序之后直接按順序掃描即可。二是在搜索過程中先考慮密度高的物品更容易在早期形成質(zhì)量較好的可行解。比如根節(jié)點(diǎn)左邊分支裝上密度最高的物品往往很快就逼近最優(yōu)值best_value 提升得快后續(xù)剪枝條件更容易滿足。三是排序不會(huì)改變最優(yōu)解本身因?yàn)榻饪臻g本質(zhì)上是在枚舉所有 0-1 組合順序調(diào)整并不影響組合的完整性。我在代碼中使用(weights[i], values[i], i)三元組保存原始下標(biāo)排序時(shí)只排三元組列表這樣排序后依然能回溯每個(gè)物品的原始位置最終構(gòu)造出正確的選擇掩碼。4.2 深度優(yōu)先搜索與剪枝代碼完整求解器如下def solve_01knapsack_bnb(weights, values, capacity): n len(weights) items sorted( [(weights[i], values[i], i) for i in range(n)], keylambda x: x[1] / x[0], reverseTrue ) best_value 0 best_mask [0] * n node_count 0 def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper def dfs(idx, cur_w, cur_v, chosen): nonlocal best_value, best_mask, node_count node_count 1 if cur_v best_value: best_value cur_v best_mask [0] * n for orig in chosen: best_mask[orig] 1 if idx n: return if int(bound(idx, cur_w, cur_v)) best_value: return w, v, orig_i items[idx] if cur_w w capacity: dfs(idx 1, cur_w w, cur_v v, chosen [orig_i]) dfs(idx 1, cur_w, cur_v, chosen) dfs(0, 0, 0, []) return best_value, best_mask, node_count代碼里有一個(gè)容易被忽略的順序進(jìn)入節(jié)點(diǎn)后先做“價(jià)值更新”再做“上界剪枝”。這樣設(shè)計(jì)是有意的。當(dāng)遞歸從更深層返回到當(dāng)前節(jié)點(diǎn)時(shí)全局 best_value 可能已經(jīng)被某個(gè)可行解刷新過了此時(shí)再算上界剪枝才有意義。如果先剪枝再更新部分子樹就可能被一個(gè)偏低的 best_value 錯(cuò)誤放過導(dǎo)致整體搜索量變大。4.3 記錄最優(yōu)解從chosen列表到最終掩碼很多教程只返回最優(yōu)值不返回選中的物品集合這對(duì)實(shí)際項(xiàng)目來(lái)說(shuō)不夠用。我用chosen列表保存從根到當(dāng)前節(jié)點(diǎn)“裝入”的物品的原始下標(biāo)每當(dāng)找到一個(gè)更優(yōu)價(jià)值時(shí)就重新生成一個(gè)長(zhǎng)度為 n 的全 0 掩碼把 chosen 里的下標(biāo)都置為 1。這種方式邏輯清晰代價(jià)是每次更新最優(yōu)解都要 O(n) 復(fù)制數(shù)組。當(dāng) n 達(dá)到幾萬(wàn)時(shí)頻繁更新可能拖慢速度。另一種做法是維護(hù)一個(gè)和物品數(shù)等長(zhǎng)的選擇數(shù)組在遞歸中用“選/不選”原位更新葉子節(jié)點(diǎn)時(shí)統(tǒng)一拷貝一次。我推薦先跑通當(dāng)前版本再根據(jù)性能瓶頸決定要不要優(yōu)化。4.4 標(biāo)準(zhǔn)算例演示用之前的例子驗(yàn)證weights [2, 3, 4, 5] values [3, 4, 5, 8] capacity 9 value, mask, count solve_01knapsack_bnb(weights, values, capacity) print(最優(yōu)價(jià)值:, value) print(選擇掩碼:, mask) print(物品原始下標(biāo):, [i for i, x in enumerate(mask) if x 1]) print(探索節(jié)點(diǎn)數(shù):, count)輸出應(yīng)該是最優(yōu)價(jià)值: 13 選擇掩碼: [0, 0, 1, 1] 物品原始下標(biāo): [2, 3] 探索節(jié)點(diǎn)數(shù): 12注意掩碼[0, 0, 1, 1]對(duì)應(yīng)原始物品 3 和物品 4總重量 4 5 9總價(jià)值 5 8 13。整個(gè)搜索只訪問 12 個(gè)節(jié)點(diǎn)遠(yuǎn)小于 31 個(gè)節(jié)點(diǎn)的全遍歷量。5. 大規(guī)模實(shí)測(cè)分支定界、動(dòng)態(tài)規(guī)劃與回溯法的選型邊界5.1 節(jié)點(diǎn)數(shù)與上界質(zhì)量的關(guān)聯(lián)分支定界的實(shí)際表現(xiàn)高度依賴數(shù)據(jù)特征我把它分成兩類典型場(chǎng)景。一類是“強(qiáng)相關(guān)”數(shù)據(jù)。價(jià)值與重量強(qiáng)相關(guān)比如價(jià)值 2 × 重量 隨機(jī)小擾動(dòng)。這種情況下連續(xù)背包松弛算出的上界和真正整數(shù)最優(yōu)解非常接近剪枝異常迅猛。我實(shí)測(cè)過 n 200、容量 5000 的強(qiáng)相關(guān)數(shù)據(jù)很多情況下節(jié)點(diǎn)數(shù)只有幾千毫秒級(jí)出結(jié)果。另一類是“弱相關(guān)”數(shù)據(jù)。價(jià)值和重量基本獨(dú)立隨機(jī)生成比如重量隨機(jī)取 1 到 100價(jià)值隨機(jī)取 1 到 200。此時(shí)連續(xù)背包松弛的上界會(huì)明顯虛高剪枝能力大幅下降節(jié)點(diǎn)數(shù)可能膨脹到幾十萬(wàn)甚至百萬(wàn)級(jí)。n 60、容量 1500 的弱相關(guān)數(shù)據(jù)就要做好它跑好幾秒的心理準(zhǔn)備而同樣數(shù)據(jù)用動(dòng)態(tài)規(guī)劃 O(60×1500) 只要一個(gè) O(nC) 小表就解決了。所以分支定界并不是“更快的最優(yōu)求解器”它是“在某些數(shù)據(jù)分布下特別高效的最優(yōu)求解器”。動(dòng)手之前先看一下你的數(shù)據(jù)是重相關(guān)還是弱相關(guān)才能判斷要不要選它。5.2 分支定界、動(dòng)態(tài)規(guī)劃、回溯暴力的適用邊界對(duì)照我把三種精確求解方法放在一張表里比較方法時(shí)間復(fù)雜度空間復(fù)雜度強(qiáng)項(xiàng)明顯短板回溯暴力最壞 O(2^n)O(n)實(shí)現(xiàn)最簡(jiǎn)單幾乎不剪枝n 30 就吃力分支定界平均遠(yuǎn)小于 2^n最壞 O(2^n)O(n)遞歸棧不依賴容量數(shù)據(jù)強(qiáng)相關(guān)時(shí)極快弱相關(guān)數(shù)據(jù)可能退化指數(shù)級(jí)動(dòng)態(tài)規(guī)劃O(nC)O(C) 可滾動(dòng)穩(wěn)定可預(yù)測(cè)小容量場(chǎng)景最優(yōu)容量 C 大時(shí)內(nèi)存和耗時(shí)爆掉從工程角度我一般這樣選型容量 C 和物品種類 n 都在可接受范圍直接上 DP穩(wěn)定省心。C 特別大、但物品數(shù)據(jù)有明顯密度差異上分支定界。數(shù)據(jù)是弱相關(guān)隨機(jī)且 n 很大那就別硬剛精確解考慮啟發(fā)式近似算法更現(xiàn)實(shí)。5.3 我踩過的一個(gè)遞歸大坑用 Python 寫 DFS 分支定界時(shí)有一個(gè)隱藏地雷遞歸深度。n 達(dá)到 1000 以上時(shí)默認(rèn)遞歸上限很容易爆出RecursionError。解決辦法有兩個(gè)一是在腳本開頭設(shè)置sys.setrecursionlimit(10000)二是改用顯式棧。顯式棧還有一個(gè)額外好處棧節(jié)點(diǎn)可以動(dòng)態(tài)排序方便實(shí)現(xiàn)后面要說(shuō)的最佳優(yōu)先搜索。不過代價(jià)是代碼復(fù)雜度明顯上升。如果你只是處理幾百個(gè)物品遞歸版本足夠沒必要一開始就寫顯式棧。6. 進(jìn)階玩法Best-First搜索、下界強(qiáng)化與并行注意點(diǎn)6.1 最佳優(yōu)先搜索優(yōu)先處理最有希望的節(jié)點(diǎn)深度優(yōu)先搜索的優(yōu)點(diǎn)是內(nèi)存小但它的“搜索路線”有時(shí)很盲目明明某個(gè)節(jié)點(diǎn)的上界非常高卻因?yàn)檫f歸路徑的關(guān)系被排到很晚才處理反而一些上界很低的節(jié)點(diǎn)卻因?yàn)槌霈F(xiàn)在遞歸路徑上被優(yōu)先擴(kuò)展了。Best-First 策略用一個(gè)優(yōu)先隊(duì)列替代遞歸棧每次取出上界最高的節(jié)點(diǎn)擴(kuò)展。這樣做的直接好處是算法會(huì)非常快地走到一條高質(zhì)量路徑并迅速刷新全局最優(yōu)解。全局最優(yōu)解變緊之后其他節(jié)點(diǎn)的剪枝條件也就更容易滿足。代價(jià)是優(yōu)先隊(duì)列需要保存大量節(jié)點(diǎn)最壞情況下內(nèi)存會(huì)指數(shù)增長(zhǎng)。我通常只在解空間特別大、且上界質(zhì)量參差不齊時(shí)使用 Best-First。6.2 下界強(qiáng)化起步時(shí)用一個(gè)好一點(diǎn)的初值很多實(shí)現(xiàn)把初始 best_value 設(shè)為 0這其實(shí)浪費(fèi)了第一波剪枝機(jī)會(huì)。簡(jiǎn)單的改進(jìn)是先跑一遍貪心算法把一個(gè)可行解的價(jià)值作為初始下界。貪心解雖然不一定最優(yōu)但往往不會(huì)太差尤其強(qiáng)相關(guān)數(shù)據(jù)下可能已經(jīng)非常接近最優(yōu)值。這樣搜索一開始就有了一把還算緊的尺子剪枝效率立即提升。更激進(jìn)的做法是在每個(gè)節(jié)點(diǎn)內(nèi)部再做一次局部貪心基于當(dāng)前已選物品繼續(xù)往后挑選可行解得到一個(gè)更精細(xì)的下界。但節(jié)點(diǎn)內(nèi)部貪心會(huì)增加計(jì)算成本對(duì)于節(jié)點(diǎn)數(shù)已經(jīng)很少的強(qiáng)相關(guān)數(shù)據(jù)收益不大對(duì)于弱相關(guān)數(shù)據(jù)單純加一個(gè)啟發(fā)式下界也救不了虛高的上界。所以我的建議是先用全局貪心當(dāng)初始下界跑一輪看效果再?zèng)Q定要不要加節(jié)點(diǎn)級(jí)啟發(fā)式。6.3 并行化的現(xiàn)實(shí)考量分支定界天然適合并行根節(jié)點(diǎn)的左右分支彼此獨(dú)立可以分給不同工作線程去搜索。工程上需要維護(hù)一個(gè)全局共享的 best_value任意工作線程發(fā)現(xiàn)更優(yōu)可行解就原子更新其他線程在剪枝判斷時(shí)讀取這個(gè)全局下界。但并行分支定界有一個(gè)典型的坑全局 best 更新可能有延遲某個(gè)線程在上界已經(jīng)能剪枝時(shí)因?yàn)樽x到的 best 偏小白白多搜了一整棵子樹。要緩解這個(gè)問題可以讓工作線程定期同步全局 best同時(shí)在每個(gè)子樹搜索開始時(shí)重新讀取一次。實(shí)際經(jīng)驗(yàn)是并行只能應(yīng)對(duì)“弱相關(guān)大實(shí)例”帶來(lái)的節(jié)點(diǎn)爆炸而且加速比并不線性很多時(shí)候 8 核只跑出 3 到 4 倍提升。如果節(jié)點(diǎn)數(shù)不大并行反而因?yàn)榫€程同步開銷變慢。我建議先把單核版本調(diào)到足夠好再考慮并行。最后分享兩個(gè)開發(fā)小技巧。第一實(shí)現(xiàn)分支定界時(shí)先寫一個(gè)完全不帶剪枝的回溯版配合小規(guī)模暴力枚舉或 DP 驗(yàn)證正確性然后再加 bound 和剪枝一步一確認(rèn)。第二步專注調(diào)試剪枝條件不然上界函數(shù)出錯(cuò)時(shí)很難定位是“剪錯(cuò)了最優(yōu)解”還是“搜索路徑本身有 bug”。第二調(diào)優(yōu)時(shí)把 node_count 打印出來(lái)觀察剪枝前后節(jié)點(diǎn)數(shù)的變化。如果加了剪枝之后節(jié)點(diǎn)數(shù)還和暴力幾乎一樣八成是上界太松或者排序沒生效這時(shí)候再回頭檢查上界函數(shù)比盲目加并行要有效得多。