最佳化問題（optimization problem）

最佳化問題要的不只是一個有效解，而是最好的那個。很多有效路線都能帶你橫越市區；最佳化問題要的是最短的。很多方式都能把物品塞進袋子；最佳化問題要的是塞得進又最值錢的。這裡有一個目標——一個我們設法盡量變小或變大的數——而在所有被允許的（可行的）解之中，我們要一個讓該目標達到極值的解。

精確地說，最佳化問題有三個部分：可行解（哪些候選根本被允許）、目標函數（我們用來給每個候選打分的數），以及方向（極小化或極大化）。答案是一個目標值最佳的可行解——沒有可行解能做得更好。對最短路徑問題而言，可行解是從 A 到 B 的所有路線，目標是總距離，方向是極小化，而答案是長度最小的一條路線。把最佳值（最好的分數，比方 42 公里）與最佳解（一條達成 42 公里的路線）分開來談很有用；有時你要前者，有時要後者，有時兩者都要。

每個最佳化問題都附帶一個自然的判定版本——「存在目標值至多為 k 的可行解嗎？」——這座橋在理論與實務上都被大量使用。如果你能對任何 k 快速回答那個是非問題，對 k 做一段短短的搜尋就能釘出最佳值，再多花點工夫通常能還原一個最佳解。坦白提醒一句：最佳化往往是真的難。有些問題我們有快速的精確方法（最短路徑、最小生成樹）；有些，例如把背包裝到最佳，目前並無已知的快速精確方法，於是我們退而求近似——接受一個可證明地接近最好的解，而不堅持要那個絕對最好的。