從「有可能嗎？」到「值得嗎？」
在上一篇指南中，回溯法以深度優先的方式走過狀態空間樹，並砍掉任何違反規則的分支——一個有兩個皇后互相攻擊的 N 皇后部分棋盤永遠無法完成，所以我們停止探索它。這就是可行性剪枝：我們殺掉一條分支，是因為它根本通不到任何有效解。但許多問題並不是在問「解存在嗎？」——它們問的是「哪個有效解最好？」那是一個最佳化問題，而對這類問題，一條分支可以完全可行，卻仍然毫無希望，因為它所能產生的最好結果，也比我們已經找到的某個答案更差。
分支定界法就是第二種剪枝的名稱。「分支」和先前是同一個動作：把剩下的選擇切成子情形再遞迴。新加入的成分是「定界」：在每個節點，我們計算從那裡出發所能達到的最佳分數的一個樂觀估計。如果連這個樂觀的估計都無法勝過我們已經存下的最佳完整解——稱它為現任最佳解（incumbent）——我們就連進都不進，直接剪掉整棵子樹。我們問的不再是「這條分支有可能嗎？」而是「這條分支有可能值得嗎？」
界絕不能在樂觀方向上撒謊
一切都繫於一條規則，而它值得謹慎陳述。節點上的界必須是樂觀的：對最大化問題，它必須是一個上界——一個不小於該節點之下真正可達最佳分數的數字。（對最小化問題則相反：界必須是一個下界，不大於真正的最佳值。）為什麼一定是這個方向？因為我們只在一條最大化分支的上界已不優於現任最佳解時才剪掉它。若上界曾經太低——比那個節點之下實際可達的某值還小——我們就可能丟掉那條藏著真正最優解的分支。一個誠實、永不過度樂觀的界，正是讓搜尋保持正確的關鍵：它只能在某棵子樹裡沒有任何東西能勝出時，才剪掉那棵子樹。
這樣的界從哪來？經典手法是把問題鬆弛：丟掉一個約束，讓較簡單的版本能快速求解，而它的答案就成為一個有效的樂觀估計。鬆弛後的答案總是至少和真正的答案一樣好——你移除了一個限制，所以只會更好或相等——這正是你需要的樂觀保證。著名的例子是 0/1 背包：在某些物品已決定的節點上，用解分數背包來為其餘物品定界，分數背包允許把物品切成碎片。依「每單位重量價值」貪婪地裝填，一趟就得到分數最優解；而既然切分物品只會有幫助，那個價值就是此節點之下整數型0/1 背包還能賺到的金額的一個真正上界。
一個小小的追蹤：用界剪枝的背包問題
用三個物品和容量 10 的背包把它具體化。物品 A：重 4、值 40。物品 B：重 6、值 42。物品 C：重 5、值 25。依每單位重量價值排序：A 是 10／單位、B 是 7／單位、C 是 5／單位。狀態空間樹依序對每個物品分支——左子節點拿它、右子節點略過它。我們一路帶著已用的重量、已收集的價值，以及一個界＝目前價值加上尚未決定物品的分數背包價值。
先往左潛（拿 A，再拿 B）：重 4 + 6 = 10，值 40 + 42 = 82，且 C 再也裝不下。那是一個完整、可行的解，所以現任最佳解變成 82。現在退回去，試「拿 A 但略過 B」這條分支。它的界是目前價值 40，加上剩餘容量 6 從 {C} 中能分數性裝下的最好值：那只有 25，於是界為 65。既然 65 已經不優於現任最佳解 82，我們就剪掉整棵子樹——根本不費心在裡面決定 C。這個界讓我們丟掉一整片可行區域，連裡面一片葉子都不必探索，而答案 82 仍可被證明是最優的。
explore(node):
if node is a complete solution:
if value(node) > incumbent: incumbent = value(node)
return
if bound(node) <= incumbent: # optimistic estimate can't win
return # PRUNE the whole subtree
for child in branch(node):
explore(child)順序很重要：下一步該展開哪個節點
單純的回溯法是死板的深度優先：它沿一條分支潛到底，才試下一條。分支定界法更自由——因為它真正需要的只是「早早得到一個強的現任最佳解」，這樣界才能狠狠剪枝。兩種常見策略各有取捨。深度優先分支定界保有遞迴的小記憶體足跡，並迅速衝向一個完整（即使尚不完美）的解，立刻給你一個可供剪枝對照的現任最佳解。最佳優先（best-first）搜尋則維護一個存放活節點的優先佇列，總是展開界最有希望的那一個——它往往較快抵達真正的最優解，但佇列可能膨脹到容納指數量級的節點，代價是大量記憶體。
無論哪一種，第二個槓桿都有幫助：先探索最有希望的子節點。在背包樹裡，先試「拿這個物品」的分支、再試「略過它」的分支，往往能快速建立一個高價值的現任最佳解，接著就能更狠地剪掉較弱的兄弟分支。這和賽局搜尋裡良好的「走步排序」是同一個智慧——早早找到一個好答案不只令人滿意，它還主動縮減了其餘的工作量。這一切都不改變哪片葉子是最優的；它只改變界開始發揮作用的快慢。
它買得到什麼，又買不到什麼
對它的保證要誠實。分支定界法骨子裡仍然是完全列舉，只是把枯枝修掉了。當它回傳一個答案時，那是可被證明為最優的——剪枝只丟掉了不可能勝出的分支。但在最壞情況下，界什麼都剪不掉，搜尋仍會走訪指數量級的節點：分支定界法並不改變一個問題的最壞情況複雜度，它改變的是你撞上那個最壞情況的頻率。對 0/1 背包、旅行推銷員以及其他困難的最佳化問題，沒有人知道在最壞情況下是多項式的方法——它們落在 NP 困難 的領域，那裡多項式演算法不僅是「未知」，更被普遍相信並不存在。
那為何要用它？因為在典型輸入上，一個好的界會兇猛地剪枝，於是一個最壞情況下指數的搜尋，實務上可能幾秒就跑完。它還有一個動態規劃常缺少的性質：它能回報一個良好的可行答案，外加一個「該答案距最優可能有多遠」的界，於是你可以帶著品質保證提早停下——當你無法等待被證明的最優性時，這很有用。在結構合適之處，像 Held-Karp 這類精確 DP 方法或許更勝一籌；而當界很緊、完整 DP 表所需記憶體太大、或你想要一個「隨時可取」的答案時，分支定界法便大放異彩。
分支定界法是我們剪枝構想中、最後一個仍由上而下搜尋單一棵樹的方法。下一篇指南換一個完全不同的角度：當搜尋空間是兩半的乘積時，你有時可以分別解每一半，再折半相遇（meet in the middle），用指數時間換取它的平方根。把這裡的核心洞見揣在口袋裡——一個誠實的樂觀界，讓你連看都不看就丟掉一片可行搜尋空間的整個區域，而正是這個單一構想，把暴力法變成你真正跑得動的東西。