搜索方法中的剪枝優(yōu)化

《搜索方法中的剪枝優(yōu)化》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、搜索中的剪枝優(yōu)化搜索方法中的剪枝優(yōu)化南開中學(xué)齊鑫【關(guān)鍵字】搜索、優(yōu)化、剪枝【摘要】本文討論了搜索方法中最常見的一種優(yōu)化技巧——剪枝，而且主要以剪枝判斷方法的設(shè)計為核心。文章首先借助搜索樹，形象的闡明了什么是剪枝；然后分析了設(shè)計剪枝判斷方法的三個原則：正確、準(zhǔn)確、高效，本文將常見的設(shè)計剪枝判斷的思路分成可行性剪枝和最優(yōu)性剪枝兩大類，并結(jié)合上述三個原則分別以一道競賽題為例作了說明；文章最后對剪枝方法作了一些總結(jié)。IOI’99中國集訓(xùn)隊優(yōu)秀論文選-77-搜索中的剪枝優(yōu)化一、引子搜索是人工智能中的一種基本方法，也是信息學(xué)

2、競賽選手所必須熟練掌握的一種方法。我們在建立一個搜索算法的時候，首要的問題不外乎兩個：1.建立算法結(jié)構(gòu)。2.選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。然而眾所周知的是，搜索方法的時間復(fù)雜度大多是指數(shù)級的，簡單的不加優(yōu)化的搜索，其時間效率往往低的不能忍受，更是難以應(yīng)付信息學(xué)競賽嚴(yán)格的運(yùn)行時間限制。本文所討論的主要內(nèi)容就是在建立算法的結(jié)構(gòu)之后，對程序進(jìn)行優(yōu)化的一種基本方法——剪枝。圖1搜索樹首先應(yīng)當(dāng)明確的是，“剪枝”的含義是什么。我們知道，搜索的進(jìn)程可以看作是從樹根出發(fā)，遍歷一棵倒置的樹——搜索樹的過程。而所謂剪枝，顧名思義，就是通過某種

3、判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。我們在編寫搜索程序的時候，一般都要考慮到剪枝。顯而易見，應(yīng)用剪枝優(yōu)化的核心問題是設(shè)計剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪些枝條應(yīng)當(dāng)保留的方法。設(shè)計出好的剪枝判斷方法，往往能夠使程序的運(yùn)行時間大大縮短；否則，也可能適得其反。那么，我們就應(yīng)當(dāng)首先分析一下設(shè)計剪枝判斷方法的時候，需要遵循的一些原則。IOI’99中國集訓(xùn)隊優(yōu)秀論文選-77-搜索中的剪枝優(yōu)化剪枝的原則原則之一：正確性。我們知道，剪枝方法之所以能夠優(yōu)化程序的執(zhí)行效率，正

4、如前文所述，是因?yàn)樗軌颉凹羧ァ彼阉鳂渲械囊恍爸l”。然而，如果在剪枝的時候，將“長有”我們所需要的解的枝條也剪掉了，那么，一切優(yōu)化也就都失去了意義。所以，對剪枝的第一個要求就是正確性，即必須保證不丟失正確的結(jié)果，這是剪枝優(yōu)化的前提。為了滿足這個原則，我們就應(yīng)當(dāng)利用“必要條件”來進(jìn)行剪枝判斷。也就是說，通過解所必須具備的特征、必須滿足的條件等方面來考察待判斷的枝條能否被剪枝。這樣，就可以保證所剪掉的枝條一定不是正解所在的枝條。當(dāng)然，由必要條件的定義，我們知道，沒有被剪枝不意味著一定可以得到正解（否則，也就不必搜

5、索了）。原則之二：準(zhǔn)確性。在保證了正確性的基礎(chǔ)上，對剪枝判斷的第二個要求就是準(zhǔn)確性，即能夠盡可能多的剪去不能通向正解的枝條。剪枝方法只有在具有了較高的準(zhǔn)確性的時候，才能真正收到優(yōu)化的效果。因此，準(zhǔn)確性可以說是剪枝優(yōu)化的生命。當(dāng)然，為了提高剪枝判斷的準(zhǔn)確性，我們就必須對題目的特點(diǎn)進(jìn)行全面而細(xì)致的分析，力求發(fā)現(xiàn)題目的本質(zhì)，從而設(shè)計出優(yōu)秀的剪枝判斷方案。原則之三：高效性。一般說來，設(shè)計好剪枝判斷方法之后，我們對搜索樹的每個枝條都要執(zhí)行一次判斷操作。然而，由于是利用出解的“必要條件”進(jìn)行判斷，所以，必然有很多不含正解的枝

6、條沒有被剪枝。這些情況下的剪枝判斷操作，對于程序的效率的提高無疑是具有副作用的。為了盡量減少剪枝判斷的副作用，我們除了要下功夫改善判斷的準(zhǔn)確性外，經(jīng)常還需要提高判斷操作本身的時間效率。IOI’99中國集訓(xùn)隊優(yōu)秀論文選-77-搜索中的剪枝優(yōu)化然而這就帶來了一個矛盾：我們?yōu)榱思訌?qiáng)優(yōu)化的效果，就必須提高剪枝判斷的準(zhǔn)確性，因此，常常不得不提高判斷操作的復(fù)雜度，也就同時降低了剪枝判斷的時間效率；但是，如果剪枝判斷的時間消耗過多，就有可能減小、甚至完全抵消提高判斷準(zhǔn)確性所能帶來的優(yōu)化效果，這恐怕也是得不償失。很多情況下，能否

7、較好的解決這個矛盾，往往成為搜索算法優(yōu)化的關(guān)鍵。綜上所述，我們可以把剪枝優(yōu)化的主要原則歸結(jié)為六個字：正確、準(zhǔn)確、高效。當(dāng)然，我們在應(yīng)用剪枝優(yōu)化的時候，僅有上述的原則是不夠的，還需要具體研究一些設(shè)計剪枝判斷方法的思路。我們可以把常用的剪枝判斷大致分成以下兩類：1.可行性剪枝。2.最優(yōu)性剪枝（上下界剪枝）。下面，我們就結(jié)合上述的三個原則，分別對這兩種剪枝判斷方法進(jìn)行一些討論。IOI’99中國集訓(xùn)隊優(yōu)秀論文選-77-搜索中的剪枝優(yōu)化三、可行性剪枝我們已經(jīng)知道，搜索過程可以看作是對一棵樹的遍歷。在很多情況下，并不是搜索樹

8、中的所有枝條都能通向我們需要的結(jié)果，很多的枝條實(shí)際上只是一些死胡同。如果我們能夠在剛剛進(jìn)入這樣的死胡同的時候，就能夠判斷出來并立即剪枝，程序的效率往往會得到提高。而所謂可行性剪枝，正是基于這樣一種考慮。下面我們舉一個例子——Betsy的旅行(USACO)。題目簡述：一個正方形的小鎮(zhèn)被分成N2個小方格，Betsy要從左上角的方格到達(dá)左下角的方格，并且經(jīng)過每個方格恰好一次。編