深搜的剪枝技巧

剪枝

• • 概念
  • 原則
  • 優化技巧
  • 例題

概念

搜尋算法的時間複雜度大多是指數級的，很難滿足對程式運作時間的限制要求，為使降低時間複雜度，對深度優先搜尋可以進行一種優化的基本方法——剪枝。

搜尋的程序可以看做周遊一棵倒置的樹。剪枝，就是就是通過某些判斷，避免一些不必要的周遊過程，形象地說，就是減去搜尋樹中的某些“枝條”。

原則

在分析設計剪枝方法時，我們應遵循以下原則：

1. 正确性
2. 準确性
3. 高效性

優化技巧

1.優化搜尋順序

在不同的問題中，搜尋樹的各個層次、各個分支之間的順序不是固定的，不同的搜尋順序會産生不同的搜尋樹形态，其規模大小也相差甚遠。

2.排除等效備援

在搜尋過程中，若能判斷從搜尋樹目前節點上沿某幾條不同分支到達的子樹是相同的，那麼隻需對其中一條分支執行搜尋。

3.可行性剪枝

在搜尋過程中，及時對目前狀态進行檢查，若發現分支已無法到達遞歸邊界，就執行回溯。某些題目條件範圍限制是一個區間，這時可行性剪枝也被成為“上下界剪枝”。

4.最優性剪枝

在最優化問題的搜尋過程中，若目前花費的代價已超過目前搜尋到的最優解，那麼無論采取多麼優秀的政策到達遞歸邊界，都不可能更新答案，此時可以停止對目前分支的搜尋，執行回溯。

5.記憶化

可以記錄每個狀态的搜尋結果，在重複周遊一個狀态時直接檢索并傳回。

例題

P1025 數的劃分 (可行性剪枝，上下界剪枝)

P1120 小木棍 （最優性剪枝，可行性剪枝）

POJ2248 Addition Chains (優化搜尋順序)

P1118 數字三角形 (最優性剪枝+楊輝三角)

NOIP2009 靶形數獨 （最優性剪枝）