1、第四章 啟發式搜尋方法4.1 最佳擾先搜尋法4.2 啟發函數4.3 記憶體限制尋法4.4 疊代改進演算法4.1 最佳優先搜尋法 有許多方式，可以將知識套用在以狀態與運算元形成問題的過程上。不過，一旦有了定義明確的問題之後，我們可以選擇的機會就會變得比較有限。一般搜尋（General-Search）策略的話，唯一可以套用知識的地方，就是在佇列函數(queuing function)之中，它的作用在決定要優先擴展的節點。通常制訂這項決策所需的知識是由評量函數（evaluation function）提供的，這個函數會回傳一個數字，代表擴展該節點的有用程度。當它們以最佳的節點優先擴展的方式排序時，所
2、形成的就是最佳優先搜尋（Best-First Search）策略。它可以使用一般搜尋策略直接導入，如圖4.1所示。4.1.1 貪婪搜尋法 最簡單的最佳優先搜尋策略之一是讓到達目標的成本估計值為最小，也就是由評量函數預估由各節點狀態到達目標狀態所需的成本，並永遠優先擴展最接近目標狀態的節點。計算預估成本的函數稱為”經驗函數”，通常用字母h表示h(n)=由節點n的狀態到達目標狀態的最低路 徑成本估計值 當最佳優先搜尋策略套用經驗函數h做為選擇下個擴展節點的依據時，這種搜尋方法就稱為”貪婪搜尋法”。若已知一個經驗函數h，則貪婪搜尋法的程式可以用下列方式敘述一般而言，經驗函數h可以是任意形式的函數。我
3、們要求h(n)=0，如果n是搜尋目標。經驗函數具有問題相依(problem-specific)的特性，通常我們會針對不同問題採用不同的經驗函數求解，因此應該先選擇一個已知的問題作為討論經驗函數的範例。探討尋找從Arad到Bucharest的路徑的問題，相關的地圖也再列於圖4.2。圖4.3列出使用貪婪搜尋法由Arad到Bucharest的路徑擴展過程。hSLD(n)=從n到目標位置的直線距離 4.1.2 A*搜尋 貪婪搜尋法使到達目標的預估成本h(n)為最低，並藉以大幅度降低搜尋成本。遺憾地，貪婪搜尋法既非最佳解也缺乏完整性。另一方面，”固定成本搜尋法”能讓已經展開的路徑成本g(n)為最低，不僅
4、有最佳解而且具有完整性，然而效率可能非常差。最好能結合這兩種方法以取得兩者的優點。f(n)=g(n)+h(n)f(n)=經過節點n的最經濟的解答的估 計成本。h函數稱為可用的經驗法則可用的經驗法則。可用的經驗法則最明顯的例子是我們用在要前往Bucharest的直線距離hSLD。直線距離是可用的，因為任何兩個點之間的最短路徑是直線。圖4.4顯示用hSLD做為啟發函數的A*搜尋法解決前往Bucharest問題的前面幾個步驟。4.1.3 4.1.3 A A*搜尋法的行為搜尋法的行為 做這個觀察的目的是建構一個A*正確執行的圖像。如果f從根節點開始的任何路徑都不會減小，我們觀念上可以描繪出狀態空間的輪
5、廓。圖4.5顯示一個範例。在標示為400的輪廓內部，所有的節點的f值都小於或等於400，以此類推。定義f*為最佳解路徑的成本，則：(1)A*展開所有具有f(n)f*。現在我們想像A*從佇列選擇了G2。因為G2是一個目標狀態，這樣將會終止搜尋並得到次佳的解答（圖4.6）。我們將證明這是不可能的。考慮節點n其現在為到G的最佳路徑上的葉節點 f*f(n)。再者，如果n沒有被為了展開G2而選擇，我們必須得到 f(n)f(G2)。組合這兩個式子，我們得到 f*f(G2)。但因為G2是目標狀態，我們得到h(G2)=0；因此我們已經從我們的假設證明了：f*g(G2)。這和G2是次佳的假設矛盾，因此這樣的情形
6、一定是A*永遠不會選擇次佳的目標展開。因此，因為A*只會在解答被展開之後傳回這個解答，所以A*最佳的演算法。4.1.5 A*的完備性證明 存在無限多的節點的可能是只有：(a)有一個節點具有無限大的分支因子，或者(b)有一條路徑具有有限的路徑成本，但是在它上面有無數個節點。因此，正確的敘述是，在存在一個正常數使得每一個運算成本最少為這樣的條件之下，A*在局部性有限圖是完備的（具有有限分支因子的圖）。4.1.6 A*的複雜度 A*搜尋法，在所有這一類的演算法之中是是完備的、最佳的同時也是效率最佳的不可否認的。對於大多數的問題，在目標輪廓搜尋空間內的節點數仍是解答長度的指數倍。然而，計算時間不是A*
7、主要的缺點。因為它必須將它所產生的所有節點都保持在記憶體裡面，A*通常在它還沒有超過時間以前就已經將它的記憶體用完了。4.2 啟發函數 八陣圖是最早的啟發式搜尋的問題之一。如同我們在3,3節所提到的，這個遊戲的目的將方格水平或垂直移動至空的方格，直到它的組態滿足目標狀態（圖4.7）。如果我們想要找到最短的解，我們需要一個永遠不會過路估計到目標距離的啟發函數。這裡我們有兩種選擇：(1)h1=在錯誤位置的方格數。圖4.7沒有一個方格位在正確的位置，因此它的初始狀態將是h1=8。h1是一個可用的啟發函數，因為任何一個不在位置上的方格至少必須移動一步。(2)h2=方格和它們正確位置距離的總和。因為方格
8、不能對角線移動，因此，距離將是水平移動與垂直動的距離總和。這有時稱之為城市街區距離城市街區距離或曼哈頓距離。曼哈頓距離。其曼哈頓距離是：h2=2+3+2+1+2+2+1+2=15 4.2.1 啟發式正確性在效能上的影響啟發式正確性在效能上的影響一種評估經驗法則品質的方法是有效分支因子有效分支因子b*。如果A*對某個問題所展開的總節點數為N，且其解答的深度是d，則深度d的均勻樹的分支因子b*將必須能包含N個節點，因此N=1+b*+(b*)2+(b*)3+(b*)d。圖4.8所示為每一個策略的平均節點展開數目，以及有效分支因子。結果顯示h2比 h1好而無資訊搜尋法是最差的。4.2.2 啟發函數的設
9、計啟發函數的設計 我們已經知道h1和h2對於八陣圖都良好的啟發函數，同時h2較好。然而，我們並不知道如何設計一個啟發函數。如何做得比h2更好？讓電腦自動化設計這樣的啟發函數是可能的嗎？如果遊戲規則改變為方格可移動到任何的地方，而不是只能移到相鄰的空格，h1將給出到達最近解所需要的正確步驟數。同樣的，如果方格可以在任何方向上移動，甚至在已經佔有的方格之上，h2將給出到達最近解所需要的正確步驟數。一個條件較鬆的問題稱為寬放寬放問題問題。寬放問題的正確解答的成本通常是其原問題良好的經驗法則。例如，八陣圖問題描述為：一個磚塊可以由方格A移動至方個B，若方格A和方格B相鄰且B是空的。們可以去掉一個或多個
10、限制而產生三個寬放問題：(a)方格B相鄰，則磚塊可以由方格A移動到方格B。(b)方格B是空的，則磚塊可以由方格A移動到方格B。(c)方格A可以移動到方格B。4.2.3條件滿足問題的啟發法則條件滿足問題的啟發法則 條件滿足問題由一個變數的集合，這些變數於由給定的定義域中取值，以及一個條件的集合，這些條件指出了解答的特性，所組成。CPS的無資訊搜尋法，大部分是深度優先搜尋法的變形。為了解釋基本概念，我們將使用圖4.9的地圖著色問題（地圖著色的概念是，避免相鄰的國家使用相同的顏色）。假設最多能使用三個顏色（紅色、綠色和藍色），同時國家選擇了綠色，國家B選擇了紅色，直覺上應該接著塗國家E，應為國家E只
11、有綠色一種選擇。到了其他的國家已經選擇了顏色，我們可能會產生錯誤擇而必須回頭。事實上，一旦我們替E選擇了藍色，我們便被強迫選擇C塗紅色，F塗綠色。之後D塗綠色或是紅色便是答案。4.3 4.3 記憶體限制搜尋法記憶體限制搜尋法 儘管所有聰明的搜尋方法都被發明了，由於問題的特性，存在難解的問題仍是事實。當我們遇到了這些指數複雜的問題時，某些事情必須給定。圖3.12指出給定的第一件事情通常是可用的記憶體。在這一節裡面，我們將探討為節省記憶體而設計的兩個演算法。第一個演算法IDA*是使用啟發資訊的疊代加深搜尋法邏輯上的推廣。第二個演算法SAM*和A*相似，但它限制了佇列的大小以符合可用的記憶體。4.3
12、.1 4.3.1 疊代加深疊代加深A A*搜尋搜尋 (IDAIDA*)將A*轉換成疊代加深的A*或IDA*（見圖4.10）。在這個演算法的每一次疊代是一個深度優先搜尋，如同一般的疊代加深法一樣。這裡的深度優先搜尋將改用f-成本限制而不用深度限制。因此，每一次的疊代對現在的f-成本展開所有在前緣的節點，在輪廓線上找出下一個輪廓線（見圖4.10的DFS-CONTOUR函數）。一旦在給定的輪廓之內的搜尋已經完成，便開始使用下一個輪廓的新的f-成本的新的疊代。4.3.2 SMA*搜尋搜尋 IDA*在處理某些問題所遇到的空間上的困境，可以被發現是因為用了太少的記憶體。在疊代之間它只需要保留一個值，現在的
13、f-成本限制。因為它無法記憶它的歷史，IDA*注定是要重複計算。圖狀的狀態空間是比是樹狀的更是如此（見3.6節）。IDA*可以修改成對現在的路徑檢查重複的狀態，但它無法避免由不同路徑所產生的重複狀態。SMA*具有如下的性質：它將利用任何能用的記憶體。(1)在記憶體允許的範圍內它避免重複的狀態。(2)它是完備的，如果可用的記體體足以儲存最淺的路徑。(3)它是最佳的，如果有足夠記體體可以用來儲存最淺的 最佳解路徑。否則它將傳回藉由可用記憶體所能找到 最好的解答。(4)當記憶體足夠整棵搜尋樹使用，這個搜尋將是效率最 佳的。SMA*最好是藉由例子解釋，這個在圖4.11中說明。圖的最上面顯示的是搜尋空間
14、。每一個節點用g+h=f標示，目標節點(D，F，I，J)用方框表示。目標是找到用只夠三個節點使用的記憶空間找到成本最小的目標節點。搜尋的步驟以由左至右的順序顯示。演算法進行如下：1.在每一個步驟，後繼者被加到其具有某些後繼者不在搜尋樹上的最深的最小f成本節點。左子節點B被加到跟節點A。2.現在f(A)仍是12，因此我們加上右邊的子節點G(f=13)。現在我們已經看過了A所有的子節點，我們更新它的f-成本為其子節點的最小值，也就是13。記憶體現在已經用完。3.G現在將要被展開，但我們先要一除一個節點以空出足夠的空間。我們移除最淺的最高f成本葉節點，也就是B。當我們做了這個動作之後，我們要標示A的
15、最佳遺忘後代具有f=15，如括弧中數字。我們加上H，其f(H)=18。不幸的H不是目標節點，但到達H的路徑用盡了所有可用的記憶體。因此，我們無法找到經由H到達的解答，因此我們設定f(H)=。4.G在一次被展開。我們移除H並加上I具有f(I)=24。現在我們已經看過了G的兩個後繼者，其具有值和24，因此f(G)變成24。注意I是一個目標節點，但它可能不是最佳的解答，因為A的f成本只有15。5.A再次成為最有希望的節點，因此在下一個時間展開B。我們已經找到了經過G的路徑畢竟沒有這樣大。6.B的第一個後繼者C是一個在最大深度的非目標節點，因此f(C)=。7.為了查看另外一個後繼者D，我們移除C。我們
16、得到f(D)=20，這個值將被B和A所繼承。8.現在最深的最小f成本節點是D。因此D被選取，因為它是目標節點，所以搜尋終止。一個SMA*的概略輪廓如圖4.12所示。在實際的程式裡面，因為某些節點會因為有些在記憶體其後繼者被被遺忘而終止這樣的事實，因此仍有一些狀況是需要處理的。當我們要檢查重複的節點，事情會變得比較複雜。SMA*是我們目前看過最複雜的搜尋方法。4.4 疊代改進演算法疊代改進演算法疊代改進演算法通常提供了最實際的解決方法。例如，我們從八個皇后都在棋盤上開始，或是所有的線路都經過特定的通道繞境。之後我們要是試圖移動皇后，以減少被襲擊的數目；或者我們將一條線路從一個通道移到另一個通道，
17、以減少壅塞。其一般性的概念是從一個完整的組態開始並加以修正以增加它的品質。理解疊代改進演算法最好的方法是考慮將所有的狀態展示在高低起伏的山勢表面。在這個山勢中的任何一點個高度就代表了那個點的狀態的評估函數（圖4.13）。4.4.1登山搜尋法登山搜尋法 登山搜尋演算法如圖4.14所示。它只是一個持續往能夠讓值增加的方向移動的簡單迴圈。這個演算法不需要維持搜尋樹，因此節點的資料結構只需記錄狀態以及它的估計值，我們用VALUE表示。這個簡單的策略具有三個為人所知的缺點：區域極值區域極值：一個區域性的極大值，相對於整體的極大值，是比狀態空間中最高的高峰要低的一個高峰。一旦落入了區域性極大值，演算法將會
18、終止，即使得到的解答和符合要求的答案距離非常遙遠。高原高原：高原是狀態空間的一個區域，此處的評估函數基本上是相差不多的。搜尋將會成為隨機散步。山脈山脈：山脈具有險峻的斜邊，因此搜尋很容易到達山脈的頂端，而這個頂端到達高峰的坡度非常的緩和。除非直接沿著山脈的頂端移動，否則搜尋將從一般到一邊來回震盪而沒有進展。很明顯的，如果允許足夠的疊代次數，隨機重新起始登山法最後將會找到最佳解。登山法是否成功和狀態空間表面的形狀非常相關：如果只有少數的區域極值，隨機重新起始登山法將會非常快速的找到好的解答。4.4.2 模擬退火法模擬退火法 當落入了區域極大值的時候除了隨機的重新開始之外，我們也可以允許搜尋採取某
19、些往下的步驟，以離開局部極大值。這大略就是模擬退火法的概念（圖4.15）。模擬退火法最中間的迴圈和登山法非常類似。4.4.3 條件滿足問題的應用條件滿足問題的應用條件滿足問題（CPS）可以用疊代改進方法，藉由首先給定每個變數數值，之後再應用修正運算將組態移動至解答的方式解決。修正運算單純的只是給變數不同的值。例如，在八皇后問題，初始狀態八個皇后都在棋盤上，運算是將某個皇后從一個方格移到另一個方格。用這樣的方式幾解決CPS的演算法通常稱為啟發式糾正法，因為它們修正了現有狀態的不一致性。在為變數選擇一個新的值的時候，最常選取的值是與其他變數衝突最少的值最少衝突經驗法則。圖4.16說明八皇后問題走了兩個步驟的情形。
