搜尋空間（search space）

在你能去搜尋答案之前，你得先知道你要在「什麼」裡面搜尋。搜尋空間是問題允許的所有候選解構成的集合——真正的答案可能藏身的每一個地方。對密碼鎖來說它是那 1000 組碼；對 n 位賓客排座位來說它是 n! 種順序；對從 n 件物品中挑一些來說它是 2^n 個子集合。想像一座巨大的倉庫，正確的箱子就在某個架子上；搜尋空間就是你可能得打開的全部箱子清單。

關於搜尋空間，有兩件事主導一切：它的結構與大小。結構是候選彼此如何相連——子集合靠加上或拿掉一個元素而不同、排列靠交換兩個位置、部分解靠多延伸一步。好的結構讓你能有系統地走過這個空間，而且關鍵在於能一次跳過一整排架子。大小單純就是候選有幾個，而它通常隨輸入殘酷地成長：對 n 件物品各選要或不要，給出 2^n 個候選（冪集合）；把 n 件物品排序給出 n!；把 n 件物品各貼上 k 種標籤之一給出 k^n。這些數字不是偶然——它們正是暴力法呈指數的原因。

演算法設計幾乎每一種技巧，骨子裡都是對搜尋空間的一句話：分治法切割它、貪婪法在它之中認定一條路、動態規劃重用它重疊的區域、回溯則剪掉它之中不可能含有解的分支。誠實地估算搜尋空間的大小——它是 2^n、n!、還是多項式？——是判斷「窮舉搜尋到底可不可行、還是非得更聰明不可」的第一個清醒步驟。