第7章 應對策略一：精確但加速#

面對 NP-hard 問題，第一條務實的路線是：不放棄「精確解」，但用聰明的技巧把指數時間的常數與剪枝做到極致，或利用問題的特殊結構（如數值範圍小）換取可行的執行時間。本章介紹三種最有代表性的技術：分支限界法（用下界估計砍掉大半搜尋樹）、動態規劃（以空間換時間，對背包這類偽多項式問題特別有效）、以及現代 SAT 求解器（DPLL 及其後裔，工業級邏輯推理的主力）。這些方法的共同精神是：最壞情況仍是指數，但實際實例往往遠小於最壞情況。