啟發(fā)式搜索 市賽一等獎

啟發(fā)式搜索前面所討論的搜索策略的一個共同特點是它們的搜索路徑是事先決定好的，沒有利用問題求解的過程中所產(chǎn)生的狀態(tài)的任何特性信息。因而這樣的搜索策略都具有較大的盲目性。如果能找到一種搜索方法，能充分利用待求解問題自身的特性信息以指導搜索朝著最有希望的方向前進，就可以提高搜索的效率。我們稱這種搜索策略為啟發(fā)式搜索。1啟發(fā)性信息和啟發(fā)函數(shù)

1.啟發(fā)性信息顧名思義，就是指有利于快速找到問題的解的信息。如，在搜索過程中，要對節(jié)點進行擴展，到底先擴展哪個節(jié)點更好一些？當生成一此后續(xù)節(jié)點時，同樣也面臨著選擇生成哪些后續(xù)節(jié)點的問題。如果遇到此無用節(jié)點，我們還要對刪除這些節(jié)點做出選擇。有了啟發(fā)性信息，我們就可以比較容易地做出選擇。由此可見，啟發(fā)性信息在搜索過程中起到一個引導搜索的作用。現(xiàn)在的問題是如何才能找到啟發(fā)性信息并把它用到搜索中。

2.啟發(fā)函數(shù)首先，我們應該合理定義一個問題的啟發(fā)性信息并把它用具體的表示方法表示出來。這便是我們要介紹的另一個概念——啟發(fā)函數(shù)。啟發(fā)函數(shù)，用來估計搜索樹上節(jié)點與目標節(jié)點接近程度的一種函數(shù)，通常記為h(x)。對于不同的問題，啟發(fā)函數(shù)有不同的形式。如何定義一個啟發(fā)函數(shù)呢？啟發(fā)函數(shù)并沒有固定的模式，具體問題需要具體分析。如：有些問題的啟發(fā)函數(shù)可以用一個節(jié)點到目標節(jié)點的某種距離或差異度量來表示；有些可以用一個節(jié)點在最佳路徑上的概率來表示；還有一些可以根據(jù)經(jīng)驗的主觀打分來表示等等。下面我們考慮怎樣來定義一個合適的啟發(fā)函數(shù)以幫助我們盡可能快地沿著它所確定的搜索路徑達到目標狀態(tài)。首先我們要求的啟發(fā)函數(shù)能夠幫助我們從多個狀態(tài)里找出一個看起來最有希望的狀態(tài)節(jié)點。因此，啟發(fā)函數(shù)應該為每個狀態(tài)節(jié)點產(chǎn)生一個相應的最值，這個量值能夠用來衡量該狀態(tài)與目標狀態(tài)之間的“距離”，即節(jié)點的函數(shù)值在某種意義上應能作為搜索工作量的一種度量。它能帶助我們在幾個狀態(tài)節(jié)點中確定一個選擇。從具有較小的啟發(fā)雨數(shù)值的那個狀態(tài)走向目標的搜索路徑應應該比較短，即工作代價最低。上述討論說明，一個啟發(fā)函數(shù)應具有兩個特征。首先，它們?yōu)檫_到目標狀態(tài)的工作量提供一個合理的估計，這種估計越精確，用它來作的決定也就會越好；其次，啟發(fā)函數(shù)值應該容易計算，它的使用應使搜索過程受益，而不是負擔。八數(shù)碼問題可以采用計算尚不在位的數(shù)碼塊的數(shù)目，估計它們各自離目標數(shù)碼塊的位置的“距離”，作為簡單的啟發(fā)函數(shù)。通常人們會猜想，一個尚有四個數(shù)碼塊未到位的狀態(tài)要比一個只有兩個數(shù)碼塊未到位的狀態(tài)離目標更遠（因此不會選擇它）。但是這種考慮的缺點是沒有考慮一個狀態(tài)節(jié)點中各小塊離目標位置有多遠。如果兩個數(shù)碼塊離它的目標位置很遠，那么實際上還需要有許多次移動，才能生成另外的狀態(tài)。一個比較合適的啟發(fā)函數(shù)是：測算一個狀態(tài)節(jié)點中每個數(shù)碼塊離目標的距離，并把這些值相加得到一個單一的值，作為該狀態(tài)節(jié)點的啟發(fā)函數(shù)值。具有小的啟發(fā)函數(shù)值的節(jié)點較有可能處在最佳路徑上。節(jié)點內(nèi)各數(shù)碼塊的距離的計算方法：將一個數(shù)碼塊移至其在目標節(jié)點中的位置，至少需要移動的次數(shù)作為距離值，移動一次距離值為1。這個試探值容易計算，用它來作為從當前狀態(tài)轉(zhuǎn)移到目標狀態(tài)要作的移動次數(shù)的一個粗略估計。例如，假定當前八數(shù)碼問題的初始狀態(tài)和目標狀態(tài)如下圖所示。2啟發(fā)式搜索過程啟發(fā)式搜索要用啟發(fā)函數(shù)來導航，其搜索過程是在盲目搜索的一般過程中增加了啟發(fā)兩數(shù)值的計算與傳播過程，并且OPEN表中的節(jié)點順序是根據(jù)啟發(fā)函數(shù)值來排列的。啟發(fā)式搜索過程：

（1）把初始節(jié)點S，放入OPEN表，計算h(S)并建立目前只包含S的圖G。（2）檢查OPEN表是否為空，若為空則問題無解，退出。（3）把OPEN表的第一個節(jié)點取出放入CLOSED表中，并記該節(jié)點為n。（4）考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。0（5）若節(jié)點不可擴展，則轉(zhuǎn)到步驟2。

（6）擴展節(jié)點n，生成一組子節(jié)點，計算每個子節(jié)點x的函教值，把這些節(jié)點作為節(jié)點日的子節(jié)點加入到圖G中。

（7）將第6步擴展的子節(jié)點放入到OPEN表中，再對OPEN名中所有子節(jié)點按其函數(shù)值大小以開序排序。（8）轉(zhuǎn)到第2步。流程圖表示啟發(fā)式搜索過程如圖所示。3問題與練習

1.什么是啟發(fā)函數(shù)，它在啟發(fā)式搜索中是如何起作用的？2.用啟發(fā)式搜索