剪枝技術（Pruning）#

剪枝是提升搜尋效率的關鍵策略，通過提前捨棄無效或劣質分支，大幅減少搜尋空間。

為什麼需要剪枝？#

現實問題的狀態空間往往呈指數級增長。純粹的 BFS/DFS 會走訪所有節點，計算成本無法負荷。剪枝的本質是優勝劣汰：提前捨棄那些明顯較差或無效的分支。

狀態空間樹與 $O(b^d)$#

把回溯過程裡所有可能的選擇攤開來看，會得到一棵狀態空間樹（state space tree）：

• 每個節點代表一個「部分解」——已經做完前幾步決定後的中間狀態；
• 每條分支代表「下一步可以怎麼選」；
• 從根走到葉，就是一條完整的決策路徑（一個候選解）。

設每個節點平均有 $b$ 個分支（分支因子，branching factor），樹的深度為 $d$（要做 $d$ 個決定），那麼整棵樹的節點數量大約是：

$$ 1 + b + b^2 + \dots + b^d = O(b^d) $$

這就是回溯的本質困境：搜尋成本隨深度指數成長。

既然總量是 $O(b^d)$，要讓搜尋變快，只有兩條路：降低有效分支因子 $b$（每一步少試幾個分支）或縮短有效深度 $d$（更早碰到死路就回頭）。剪枝做的正是這件事——砍掉整棵子樹，等於一次抹掉 $b^k$ 量級的節點。這也是為什麼「剪得準」往往比「算得快」更能決定成敗。

剪枝的運作邏輯#

當搜尋進行到某個節點時（例如面臨 50 個分支）：

1. 確定性剪枝：若能確定最優解只存在於某分支，直接捨棄其他
2. 優先順序剪枝：優先搜尋「區域最優」的分支，較差的延後或捨棄

常見剪枝策略#

案例：井字棋的剪枝思維#

人類下棋時自然會進行剪枝：

當對手落子於某位置後，你不會再考慮「對手下在其他位置」的分支。這就是最自然的剪枝——根據已知事實，剪掉不可能的未來。

從深藍到 AlphaGo#

國際象棋（深藍，1996）#

• 方法：強大計算力 + 精細剪枝規則
• 搜尋深度：30-40 步
• 複雜度：約 10^123

圍棋（AlphaGo，2016）#

• 方法：深度學習 + 蒙特卡洛樹搜尋
• 創新：神經網路充當「智慧剪枝函式」
• 複雜度：約 10^360

從西洋棋到圍棋，本質上是對抗「狀態空間爆炸」。當無法窮盡所有變化時，演算法重心從「算得快」轉向「剪得準」。

棋類遊戲複雜度排行#

置信度剪枝與聚光搜索（Beam Search）#

前面的剪枝都有個共同前提：被砍掉的分支是「不可能更好」的，所以剪掉不影響最優性。但當狀態空間實在太大、連剪枝後也算不完時，這種保證就成了奢侈品——這時可以退一步，從「保證找到最優」改成「以高置信度找到夠好的解」。

聚光搜索（Beam Search） 是最具代表性的做法。它逐層展開狀態空間樹，但在每一層只保留評分最高的 $m$ 個候選（$m$ 稱為 beam width，束寬），其餘全部直接砍掉：

• 樸素搜尋每層節點數會以 $b$ 倍膨脹，第 $d$ 層達到 $b^d$；
• Beam Search 強制每層至多 $m$ 個節點，總工作量壓到約 $O(m \cdot b \cdot d)$——與深度線性相關。

代價是：被砍掉的分支裡，可能藏著真正的最優解，但我們再也找不回它了。

兩種剪枝的分界線，全在那句評語：

• 一般剪枝：剪掉「不可能更好」的分支——邏輯上已被排除，不損最優性。
• 置信度剪枝：剪掉「大概不會更好」的分支——憑評分函式的猜測下手，可能誤砍最優解，但換來能在合理時間內跑完。

這背後其實是同一種思維：用一點正確性，換取大量時間。它和近似演算法放棄精確最優、只求「離最優不太遠」的取捨如出一轍。Beam Search 因此廣泛用於機器翻譯、語音辨識這類輸出空間爆炸、又無法等待窮舉的場景。

回頭看前面提到的圍棋：當狀態空間大到 $10^{360}$，棋類 AI 同樣靠「限制搜尋深度 + 寬度剪枝」來馴服它——限制深度是縮短 $d$，寬度剪枝就是束搜尋式地壓低每層保留的分支數。指數級的怪獸，最終靠著一層層的取捨被關進可計算的籠子裡。

剪枝的難點#

剪枝的難點在於評估函式的設計：

• 剪得太狠：可能漏掉全域最優解
• 剪得太少：起不到最佳化效果

這需要對具體業務邏輯有深刻理解。

實戰啟發式規則#

以象棋為例：