搜尋方法中的剪枝優化
南開中學齊鑫
【關鍵字】搜尋、優化、剪枝
【摘要】本文討論了搜尋方法中最常見的一種優化技巧——剪枝，而且主要以剪枝判斷方法的設計為核心。文章首先借助搜尋樹，形象的闡明了什麼是剪枝；然後分析了設計剪枝判斷方法的三個原則：正確、準確、高效，本文將常見的設計剪枝判斷的思路分成可行性剪枝和最優性剪枝兩大類，並結合上述三個原則分別以一道競賽題為例作了說明；文章最後對剪枝方法作了一些總結
一、 引子
搜尋是人工智慧中的一種基本方法，也是資訊學競賽選手所必須熟練掌握的一種方法。我們在建立乙個搜尋演算法的時候，首要的問題不外乎兩個：
1. 建立演算法結構。
2. 選擇適當的資料結構。
然而眾所周知的是，搜尋方法的時間複雜度大多是指數級的，簡單的不加優化的搜尋，其時間效率往往低的不能忍受，更是難以應付資訊學競賽嚴格的執行時間限制。
本文所討論的主要內容就是在建立演算法的結構之後，對程式進行優化的一種基本方法——剪枝。
圖1 搜尋樹
首先應當明確的是，「剪枝」的含義是什麼。我們知道，搜尋的程序可以看作是從樹根出發，遍歷一棵倒置的樹——搜尋樹的過程。而所謂剪枝，顧名思義，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜尋樹中的某些「枝條」，故稱剪枝。
我們在編寫搜尋程式的時候，一般都要考慮到剪枝。顯而易見，應用剪枝優化的核心問題是設計剪枝判斷方法，即確定哪些枝條應當捨棄，哪些枝條應當保留的方法。設計出好的剪枝判斷方法，往往能夠使程式的執行時間大大縮短；否則，也可能適得其反。
那麼，我們就應當首先分析一下設計剪枝判斷方法的時候，需要遵循的一些原則。
二、 剪枝的原則
我們知道，剪枝方法之所以能夠優化程式的執行效率，正如前文所述，是因為它能夠「剪去」搜尋樹中的一些「枝條」。然而，如果在剪枝的時候，將「長有」我們所需要的解的枝條也剪掉了，那麼，一切優化也就都失去了意義。所以，對剪枝的第乙個要求就是正確性，即必須保證不丟失正確的結果，這是剪枝優化的前提。
為了滿足這個原則，我們就應當利用「必要條件」來進行剪枝判斷。也就是說，通過解所必須具備的特徵、必須滿足的條件等方面來考察待判斷的枝條能否被剪枝。這樣，就可以保證所剪掉的枝條一定不是正解所在的枝條。
當然，由必要條件的定義，我們知道，沒有被剪枝不意味著一定可以得到正解（否則，也就不必搜尋了）。
在保證了正確性的基礎上，對剪枝判斷的第二個要求就是準確性，即能夠盡可能多的剪去不能通向正解的枝條。剪枝方法只有在具有了較高的準確性的時候，才能真正收到優化的效果。因此，準確性可以說是剪枝優化的生命。
當然，為了提高剪枝判斷的準確性，我們就必須對題目的特點進行全面而細緻的分析，力求發現題目的本質，從而設計出優秀的剪枝判斷方案。
一般說來，設計好剪枝判斷方法之後，我們對搜尋樹的每個枝條都要執行一次判斷操作。然而，由於是利用出解的「必要條件」進行判斷，所以，必然有很多不含正解的枝條沒有被剪枝。這些情況下的剪枝判斷操作，對於程式的效率的提高無疑是具有***的。
為了儘量減少剪枝判斷的***，我們除了要下功夫改善判斷的準確性外，經常還需要提高判斷操作本身的時間效率。
然而這就帶來了乙個矛盾：我們為了加強優化的效果，就必須提高剪枝判斷的準確性，因此，常常不得不提高判斷操作的複雜度，也就同時降低了剪枝判斷的時間效率；但是，如果剪枝判斷的時間消耗過多，就有可能減小、甚至完全抵消提高判斷準確性所能帶來的優化效果，這恐怕也是得不償失。很多情況下，能否較好的解決這個矛盾，往往成為搜尋演算法優化的關鍵。
綜上所述，我們可以把剪枝優化的主要原則歸結為六個字：正確、準確、高效。
當然，我們在應用剪枝優化的時候，僅有上述的原則是不夠的，還需要具體研究一些設計剪枝判斷方法的思路。我們可以把常用的剪枝判斷大致分成以下兩類：
1. 可行性剪枝。
2. 最優性剪枝（上下界剪枝）。
下面，我們就結合上述的三個原則，分別對這兩種剪枝判斷方法進行一些討論。
三、可行性剪枝
我們已經知道，搜尋過程可以看作是對一棵樹的遍歷。在很多情況下，並不是搜尋樹中的所有枝條都能通向我們需要的結果，很多的枝條實際上只是一些死胡同。如果我們能夠在剛剛進入這樣的死胡同的時候，就能夠判斷出來並立即剪枝，程式的效率往往會得到提高。
而所謂可行性剪枝，正是基於這樣一種考慮。
下面我們舉乙個例子——betsy的旅行(usaco)。
題目簡述：乙個正方形的小鎮被分成n2個小方格，betsy要從左上角的方格到達左下角的方格，並且經過每個方格恰好一次。程式設計對於給定的n，計算出betsy能採用的所有的旅行路線的數目。
我們用深度優先的回溯方法來解決這個問題：betsy從左上角出發，每一步可以從乙個格仔移動到相鄰的沒有到過的格仔中，遇到死胡同則回溯，當移動了n2-1步並達到左下角時，即得到了一條新的路徑，繼續回溯搜尋，直至遍歷完所有道路。
但是，僅僅依照上述演算法框架程式設計，時間效率極低，對n=6的情況無法很好的解決，所以，優化勢在必行。對本題優化的關鍵就在於當搜尋到某乙個步驟時，能夠提前判斷出在後面的搜尋過程中是否一定會遇到死胡同，而可行性剪枝正可以在這裡派上用場。
我們首先從「必要條件」，即合法的解所應當具備的特徵的角度分析剪枝的方法，主要有兩個方向：
1. 對於一條合法的路徑，除出發點和目標格仔外，每乙個中間格仔都必然有「一進一出」的過程。所以在搜尋過程中，必須保證每個尚未經過的格仔都與至少兩個尚未經過的格仔相鄰（除非當時betsy就在它旁邊）。
這裡，我們是從微觀的角度分析問題。
2. 在第乙個條件的基礎上，我們還可以從巨集觀的角度分析，進一步提高剪枝判斷的準確性。顯然，在乙個合法的移動方案的任何時刻，都不可能有孤立的區域存在。
雖然孤立區域中的每乙個格仔也可能都有至少兩個相鄰的空的格仔，但它們作為乙個整體，betsy已經不能達到。我們也應當及時判斷出這種情況，並避免之。
以上兩個剪枝判斷條件都是正確的，其準確度也比較高。但是，僅僅滿足這兩點還不夠，剪枝判斷的操作過程還必須力求高效。假如我們在每次剪枝判斷時，都簡單的對n2個格仔進行一遍掃瞄，其效率的低下可想而知。
因此，我們必須盡可能的簡化判斷的過程。
實際上，由於betsy的每一次移動，只會影響到附近的格仔，所以每次執行剪枝判斷時，應當只對她附近的格仔進行檢查：
對於第乙個剪枝條件，我們可以設乙個整型標誌陣列，分別儲存與每個格仔相鄰的沒被經過的格仔的數目，betsy每次移動到乙個新位置，都只會使與之相鄰的至多4個格仔的標誌值發生變化，只要檢查它們的標誌值即可。
已經到過的格仔尚未到過的格仔
betsy的移動方向betsy的位置
圖2 剪枝原理示意圖
而對於第二個剪枝條件，處理就稍稍麻煩一些。但我們仍然可以使用區域性分析的方法，即只通過對betsy附近的格仔進行判斷，就確定是否應當剪枝，下圖簡要說明了剪枝的原理：
上圖給出了可以剪枝的三種情況。由於betsy到過的所有格仔都一定是四連通的，所以每種情況下的兩個白色的格仔之間必定是不連通的，它們當中必然至少有乙個是屬於某個孤立區域的，都一定可以剪枝。
經過上述的優化，程式的時間效率有了很大的提高（參見附錄）。
一般說來，可行性剪枝多用於路徑搜尋類的問題。除本例外，如prime circle (acm asian regional 96)等問題，也都可以使用這種剪枝方法。
在應用可行性剪枝的時候，首先要多角度全面分析問題的特點（本題就是從微觀和巨集觀兩個角度設計剪枝方法），找到盡可能多的可以剪枝的情況；同時，還必須注意提高剪枝的時間效率，所以我們使用了「區域性判斷」的方法，特別是在處理第二個剪枝條件時，更是通過區域性判斷來體現整體性質（是否有孤立區域），這一技巧不僅在設計剪枝方法的時候能夠發揮作用，在其他方面也有著極為廣泛的應用。
三、 最優性剪枝
在我們平時遇到的問題中，有一大類是所謂最優化問題，即所要求的結果是最優解。如果我們使用搜尋方法來解決這類問題，那麼，最優性剪枝是一定要考慮到的。
為了表述的統一，首先要作一些說明：我們知道，解的優劣一般是通過乙個評價函式來評判的。這裡定義乙個抽象的評價函式——「優度」，它的值越大，對應的解也就越優（對於具體的問題，我們可以認為「優度」代表正的收益或負的代價等）。
然後，我們再來回顧一下搜尋最優解的過程：一般情況下，我們需要儲存乙個「當前最優解」，實際上就是儲存解的優度的乙個下界。在遍歷到搜尋樹的葉子節點的時候，我們就能得到乙個新的解，當然也就得到了它的評價函式值，與儲存的優度的下界作比較，如果新解的優度值更大，則這個優度值就成為新的下界。
搜尋結束後，所儲存的解就是最優解。
那麼，最優性剪枝又是如何進行的呢？當我們處在搜尋樹的枝條上時，可以通過某種方法估算出該枝條上的所有解的評價函式的上界，即所謂估價函式。顯然，大於當前儲存的優度的下界，是該枝條上存在最優解的必要條件，否則就一定可以剪枝。
所以，最優性剪枝也可以稱為「上下界剪枝」。同時，我們也可以看到，最優性剪枝的核心問題就是估價函式的建立。
下面舉乙個應用最優性剪枝的典型例題——最少乘法次數。
題目簡述：由開始，通過最少的乘法次數得出，其中為輸入資料。（參見參考書目1）
因為兩式相乘等於方冪相加，所以本題可以等效的表示為：構造乙個數列，滿足
要求，並且使最小。
我們選擇回溯法作為本程式的主體結構：當搜尋到第層時，的取值範圍在到之間，為了盡快接近目標，應當從開始從大到小為取值，當然，選取的數都不能大於。當搜尋到出現時，就得到了乙個解，與當前儲存的解比較取優。
最終搜尋結束之後，即得到最終的最優解。
如果按上述結構直接進行搜尋，效率顯然很低。因此，我們可以考慮使用最優性剪枝進行優化：
優化之一：當然首先要建立估價函式。由於使數列中的最大數加倍無疑是最快的增長方式，所以一種最簡單的估價函式為（設數列中當前的最大者是，即當前搜尋深度為）：
然而，這個估價函式的準確性太差，特別是當大於時，只能等於1，根本不能發揮剪枝的作用。因此，無論是深度優先的回溯法還是寬度優先的a*搜尋方法，只要還使用這個估價函式，其優化效果都比較有限。
下面，我們再討論一些進一步的優化手段——
優化之二：著眼於估價函式的「生命」——準確性。我們可以利用加法在奇偶性上的特點的推廣，使估價函式在某些情況下的準確性得到一定的提高（具體改進請參見附錄）。
演算法合集之《資訊學競賽中的思維方法》
廣東省韶關一中陳彧 關鍵字 資訊學思維方法 摘要 本文將借鑑一些數學思維理論，思維方法在資訊學競賽中的地位和作用，並介紹資訊學競賽中的幾種思維方法，包括 試驗猜想及歸納 模型化 分類及分治 模擬。其中將引用大量的例題進行思維過程的分析，大部分的例題是1999年noi ioi試題，具有廣泛的代表性。最...
演算法合集之《圖論的基本思想及方法》
湖南省長沙市長郡中學任愷 文章著眼於圖論基本思想及方法的討論，不涉及高深的圖論演算法。文章主要從兩方面闡述圖論的基本思想 一是合理選擇圖論模型 二是如何深入挖掘問題本質，充分利用模型的特性。同時還歸納了一些解決問題的普適性方法。基本思想 圖論模型 問題本質 定義法 分析法 綜合法 圖是用點和邊來描述...
谷歌演算法調整下的搜尋引擎優化
對於seo很多表示沒上個幾年學，沒有多少的優化經驗都可以很好的從頭學起，有時候甚至比那些做了很多年的seoer還要好。這是怎麼回事，難道搜尋引擎也屬於 喜新厭舊 之類？得出此結論要從最新的谷歌演算法中可以看出，針對大量的外鏈匯入到內頁，這次谷歌演算法調整之後很多 受到了懲罰，這是很多業內人士所出乎意...