4.3.1 爬山法搜索

圖4.11中顯示了爬山法（hill-climbing）搜索的算法。它是一個(gè)向值增加的方向持續(xù)移動(dòng)的簡(jiǎn)單循環(huán)過程——也就是，登高。它將會(huì)在到達(dá)一個(gè)“峰頂”時(shí)終止，相鄰狀態(tài)中沒有比它更高的值。這個(gè)算法不維護(hù)搜索樹，因此當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)只需要記錄當(dāng)前狀態(tài)和它的目標(biāo)函數(shù)值。爬山法不會(huì)前瞻與當(dāng)前狀態(tài)不直接相鄰的那些狀態(tài)的值。這就像健忘的人在大霧中試圖登頂珠穆朗瑪峰一樣。

圖4.11 爬山法搜索算法（最陡上升方式），這是最基本的局部搜索技術(shù)。在每一步中當(dāng)前的節(jié)點(diǎn)都會(huì)被最佳鄰節(jié)點(diǎn)所代替；按這種方式，最佳鄰節(jié)點(diǎn)意味著VALUE最高的鄰居節(jié)點(diǎn)，但是如果使用啟發(fā)式耗散估計(jì)h，我們要找的就是h最低的鄰居節(jié)點(diǎn)

我們將用第3.2.1節(jié)介紹的八皇后問題舉例說明爬山法算法。局部搜索算法通常使用完全狀態(tài)形式化，即每個(gè)狀態(tài)都在棋盤上放八個(gè)皇后，每列一個(gè)。后繼函數(shù)返回的是移動(dòng)一個(gè)皇后到和它同一列的另一個(gè)方格中的所有可能的狀態(tài)（因此每個(gè)狀態(tài)有8 × 7 = 56個(gè)后繼）。啟發(fā)式耗散函數(shù)h是可以彼此攻擊的皇后對(duì)的數(shù)量，不管中間是否有障礙。該函數(shù)的全局最小值是 0，僅在找到完美解時(shí)才能得到這個(gè)值。圖4.12（a）顯示了一個(gè)h = 17的狀態(tài)。圖中還顯示了它的所有后繼的值，最好的后繼的h =12。爬山法算法通常在最佳后繼的集合中隨機(jī)選擇一個(gè)進(jìn)行擴(kuò)展，如果這樣的后繼多于一個(gè)的話。

圖4.12 （a）八皇后問題的一個(gè)狀態(tài)，其中啟發(fā)式耗散估計(jì)h=17，方格中顯示的數(shù)字表示將這一列中的皇后移到該方格而得到的后繼的h值。最佳移動(dòng)在圖中標(biāo)記出來了。（b）八皇后問題狀態(tài)空間中的一個(gè)局部極小值；該狀態(tài)的h=1，但是它的每個(gè)后繼的h值都比它高

爬山法有時(shí)稱為貪婪局部搜索，因?yàn)樗皇沁x擇鄰居狀態(tài)中最好的一個(gè)，而事先不考慮之后下一步往哪個(gè)方向走。盡管貪婪是七宗罪之一，貪婪算法卻往往有很好的效果。爬山法能很快朝著解的方向進(jìn)展，因?yàn)樗ǔ：苋菀赘倪M(jìn)一個(gè)壞的狀態(tài)。例如，從圖4.12（a）中的狀態(tài)，它只需要五步就能到達(dá)圖4.12（b）中的狀態(tài)，它的h = 1基本上很接近于解了。不幸的是，爬山法經(jīng)常會(huì)遇到下面的問題：

局部極大值：局部極大值是一個(gè)比它的每個(gè)鄰居狀態(tài)都高的峰頂，但是比全局最大值要低。爬山法算法到達(dá)局部極大值附近就會(huì)被拉向峰頂，然后被卡在局部極大值處無處可走。圖4.10示意性地表現(xiàn)了這種情況。更具體地，圖4.12（b）中的狀態(tài)事實(shí)上是一個(gè)局部極大值（即耗散h的局部極小值）；不管移動(dòng)哪個(gè)皇后得到的情況都會(huì)比原來差。

山脊：圖4.13顯示了山脊的情況。山脊造成一系列的局部極大值，貪婪算法處理這種情況是很難的。

高原：高原是在狀態(tài)空間地形圖上評(píng)價(jià)函數(shù)值平坦的一塊區(qū)域。它可能是一塊平的局部極大值，不存在上山的出路，或者是一個(gè)山肩，從山肩還有可能取得進(jìn)展。（參見圖4.10。）爬山法搜索可能無法找到離開高原的道路。

在每種情況下，爬山法算法都會(huì)達(dá)到無法取得進(jìn)展的地點(diǎn)。從一個(gè)隨機(jī)生成的八皇后問題的狀態(tài)開始，最陡上升的爬山法86％的情況下會(huì)被卡住，只有14％的問題實(shí)例能求解。這個(gè)算法速度很快，成功找到最優(yōu)解的平均步數(shù)是4步，被卡住的平均步數(shù)是3步——對(duì)于包含88≈1千7百萬個(gè)狀態(tài)的狀態(tài)空間這是不錯(cuò)的結(jié)果。

圖4.11中的算法如果到達(dá)一個(gè)高原，最佳后繼的狀態(tài)值和當(dāng)前狀態(tài)值相等時(shí)將會(huì)停止。如果高原其實(shí)是如圖4.10中所示的山肩，繼續(xù)前進(jìn)——即側(cè)向移動(dòng)是一個(gè)好主意嗎？答案通常是肯定的，但是我們要小心。如果我們?cè)跊]有上山移動(dòng)的情況下總是允許側(cè)向移動(dòng)，那么當(dāng)?shù)竭_(dá)一個(gè)平坦的局部極大值而不是山肩的時(shí)候，算法會(huì)陷入無限循環(huán)。一種常規(guī)的解決辦法是設(shè)置允許連續(xù)側(cè)向移動(dòng)的次數(shù)限制。例如，我們?cè)诎嘶屎髥栴}中允許最多連續(xù)側(cè)向移動(dòng)100次。這使問題實(shí)例的解決率從14％提高到了94％。成功的代價(jià)是：算法對(duì)于每個(gè)成功搜索實(shí)例的平均步數(shù)為大約21步，每個(gè)失敗實(shí)例的平均步數(shù)為大約64步。

人們發(fā)明了爬山法的許多變化形式。隨機(jī)爬山法在上山移動(dòng)中隨機(jī)地選擇下一步；選擇的概率隨著上山移動(dòng)的陡峭程度而變化。這種算法通常比最陡上升算法的收斂速度慢不少，但是在某些狀態(tài)空間地形圖上能找到更好的解。首選爬山法實(shí)現(xiàn)了隨機(jī)爬山法，它采用的方式是隨機(jī)地生成后繼節(jié)點(diǎn)直到生成一個(gè)優(yōu)于當(dāng)前節(jié)點(diǎn)的后繼。這個(gè)算法在有很多后繼節(jié)點(diǎn)的情況下（例如上千個(gè)）是個(gè)好策略。習(xí)題4.16要求你研究這個(gè)問題。

圖4.13 為什么山脊會(huì)給爬山法帶來困難的圖示。圖中的狀態(tài)網(wǎng)格（黑色圓點(diǎn)）疊加在從左到右上升的山脊上，創(chuàng)造了一個(gè)不直接相連的局部極大值序列。從每個(gè)局部極大點(diǎn)出發(fā)，可能的行動(dòng)都是指向下山方向的

到現(xiàn)在為止我們描述的爬山法算法還是不完備的——它們經(jīng)常會(huì)在目標(biāo)存在的情況下因?yàn)楸痪植繕O大值卡住而找不到該目標(biāo)。隨機(jī)重新開始的爬山法采納了一條著名的諺語：“如果一開始沒有成功，那么嘗試，繼續(xù)嘗試?！彼ㄟ^隨機(jī)生成的初始狀態(tài)[14]來進(jìn)行一系列的爬山法搜索，找到目標(biāo)時(shí)停止搜索。這個(gè)算法是完備的概率接近于1，原因是它最終會(huì)生成一個(gè)目標(biāo)狀態(tài)作為初始狀態(tài)。如果每次爬山法搜索成功的概率為p，那么需要重新開始搜索的期望次數(shù)為1/p。對(duì)于不允許側(cè)向移動(dòng)的八皇后問題實(shí)例，p≈0.14，因此我們大概需要7次迭代就能找到目標(biāo)（6次失敗1次成功）。所需步數(shù)的期望值為一次成功迭代的搜索步數(shù)加上失敗的搜索步數(shù)與(1 ? p) / p的乘積，大約是22步。當(dāng)我們?cè)试S側(cè)向移動(dòng)時(shí)，平均需要迭代約1 / 0.94≈1.06次，平均的步數(shù)為(1 × 21)+(0.06 / 0.94) × 64≈25步。那么對(duì)于八皇后問題，隨機(jī)重新開始的爬山法實(shí)際上是非常有效的。甚至對(duì)于三百萬個(gè)皇后，這個(gè)方法用不了一分鐘就可以找到解。[15]

爬山法算法成功與否在很大程度上取決于狀態(tài)空間地形圖的形狀：如果在圖中幾乎沒有局部極大值和高原，隨機(jī)重新開始的爬山法將會(huì)很快地找到好的解。另一方面，許多實(shí)際問題的地形圖就像平坦的地板上的一群豪豬，每個(gè)豪豬身上刺的尖端還生活著微小的豪豬，乃至無限。NP 難題通常有指數(shù)級(jí)數(shù)量的局部極大值。盡管如此，經(jīng)過少數(shù)隨機(jī)重新開始的搜索之后還是能找到一個(gè)合理的較好的局部極大值的。