分支定界法（branch and bound）

當你只需要任一個滿足規則的解時，回溯很好用。但許多問題要的是最佳解——最便宜的路線、最有價值的背包、最短的排程。分支定界是為最佳化升級過的回溯：探索時你保留「到目前為止找到的最佳完整解」，並在每個部分解處算出一個樂觀估計，即它的任一完成方式所能達到的最好結果。若連那個樂觀估計都打不過你手上已有的最佳解，你就剪掉整棵子樹——進去看也沒意義。

兩半都在名字裡。分支與回溯相同：把一個部分解依下一個決定的各選項拆開，建出狀態空間樹。定界是新點子：在每個節點你對「該節點所有完成方式」的目標值算一個界——對最小化問題是下界（任一完成方式所能有的最好、即最小成本），對最大化是上界。你也追蹤現任最佳值（incumbent），即至今所見最佳完整解的值。剪枝規則：若某節點的樂觀界不優於現任最佳值（最小化時，若節點下界 >= 現任最佳值），則該節點的任何完成方式都不能改進你手上的，於是丟棄該節點。好的界通常是一種鬆弛——解一個忽略某些約束的較易版本（例如背包允許分數物品）來快速取得樂觀值。

正確性完全繫於界的有效性：它絕不能比真相更樂觀（最小化的下界必須真的 <= 每個完成方式的成本），否則你可能剪掉真正的最佳解。給定有效的界，分支定界回傳一個可證明的最佳答案，而往往造訪的節點遠少於完整列舉。問題在於最壞情況仍是指數——弱的界剪不掉多少——而這方法的快慢，取決於界有多緊、以及探索順序有多好（先探有希望的節點能快速抬高現任最佳值，使後續剪枝更兇狠）。