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

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

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

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

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

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

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

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