一、何謂啟發(fā)式搜索

啟發(fā)式搜索算法有點(diǎn)像廣度優(yōu)先搜索，不同的是，它會(huì)優(yōu)先順著有啟發(fā)性和具有特定信息的節(jié)點(diǎn)搜索下去，這些節(jié)點(diǎn)可能是到達(dá)目標(biāo)的最好路徑。

我們稱這個(gè)過程為最優(yōu)（best-first）或啟發(fā)式搜索。

下面是其基本思想：

假定有一個(gè)啟發(fā)式(評(píng)估)函數(shù)?f ，可以幫助確定下一個(gè)要擴(kuò)展的最優(yōu)節(jié)點(diǎn)，我們采用一個(gè)約定，即?f的值小表示找到了好的節(jié)點(diǎn)。這個(gè)函數(shù)基于指定問題域的信息，它是狀態(tài)描述的一個(gè)實(shí)數(shù)值函數(shù)。

下一個(gè)要擴(kuò)展的節(jié)點(diǎn)n是?f(n)值最小的節(jié)點(diǎn)(假定節(jié)點(diǎn)擴(kuò)展產(chǎn)生一個(gè)節(jié)點(diǎn)的所有后繼)。

當(dāng)下一個(gè)要擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)過程終止。

假定有一個(gè)啟發(fā)式(評(píng)估)函數(shù)?f ，可以幫助確定下一個(gè)要擴(kuò)展的最優(yōu)節(jié)點(diǎn)，我們采用一個(gè)約定，即?f的值小表示找到了好的節(jié)點(diǎn)。這個(gè)函數(shù)基于指定問題域的信息，它是狀態(tài)描述的一個(gè)實(shí)數(shù)值函數(shù)。

下一個(gè)要擴(kuò)展的節(jié)點(diǎn)n是?f(n)值最小的節(jié)點(diǎn)(假定節(jié)點(diǎn)擴(kuò)展產(chǎn)生一個(gè)節(jié)點(diǎn)的所有后繼)。

當(dāng)下一個(gè)要擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)過程終止。

我們常?？梢詾樽顑?yōu)搜索指定好的評(píng)估函數(shù)。

如在8數(shù)碼問題中，可以用不正確位置的數(shù)字個(gè)數(shù)作為狀態(tài)描述好壞的一個(gè)度量：

f(n) = 位置不正確的數(shù)字個(gè)數(shù)(和目標(biāo)相比)

在搜索過程中采用這個(gè)啟發(fā)式函數(shù)將產(chǎn)生圖9 - 1所示的圖，每個(gè)節(jié)點(diǎn)的數(shù)值是該節(jié)點(diǎn)的值。

上述例子表明，在搜索過程中我們需要偏向有利于回溯到早期路徑的搜索(為了避免由于過分的優(yōu)化試探而陷入“花園小徑”)。

因此我們加了一個(gè)“深度因子”給?f: ?f(n)= g?(n)+ h?(n) ，g?(n)是對(duì)圖中節(jié)點(diǎn)n的“深度”估計(jì)(即從開始節(jié)點(diǎn)到n的最短路徑長(zhǎng)度)，h?(n)是對(duì)節(jié)點(diǎn)n的啟發(fā)或評(píng)估。

像前面一樣，如果g?(n)= 搜索圖中節(jié)點(diǎn)n的深度，h?(n)=不正確位置的數(shù)字個(gè)數(shù)(和目標(biāo)相比)， 我們可以得到圖9-2。

在這個(gè)圖中，把g?(n)和h?(n)的值寫在每個(gè)節(jié)點(diǎn)的旁邊，在這種情況下，可以看到搜索相當(dāng)直接地朝著目標(biāo)進(jìn)行(除了用圓圈標(biāo)注的節(jié)點(diǎn)外)。

這些例子提出了兩個(gè)重要的問題。

我們?nèi)绾螢樽顑?yōu)搜索決定評(píng)估函數(shù)？

最優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？

我們?nèi)绾螢樽顑?yōu)搜索決定評(píng)估函數(shù)？

最優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？

二、一個(gè)通用的圖搜索算法

為了更準(zhǔn)確地解釋啟發(fā)式搜索過程，這里提出一個(gè)通用的圖搜索算法，它允許各種用戶—偏愛啟發(fā)式的或盲目的，進(jìn)行定制。我把這個(gè)算法叫做圖搜索（GRAPHSEARCH）。

下面是（第一個(gè)版本）它的定義。

GRAPHSEACH：

生成一個(gè)僅包含開始節(jié)點(diǎn)n0的搜索樹Tr。把n0放在一個(gè)稱為OPEN的有序列表中。

生成一個(gè)初始值為空的列表CLOSED。

如果OPEN為空，則失敗并退出。

選出OPEN中的第一個(gè)節(jié)點(diǎn)，并將它從OPEN中移出，放入CLOSED中。稱該節(jié)點(diǎn)為n。

如果n是目標(biāo)節(jié)點(diǎn)，順著Tr中的弧從n回溯到n0找到一條路徑，獲得解決方案，則成功退出（弧在第6步產(chǎn)生）。

擴(kuò)展節(jié)點(diǎn)n，生成n的后繼節(jié)點(diǎn)集M。通過在Tr中建立從n到M中每個(gè)成員的弧生成n的后繼。

按照任意的模式或啟發(fā)式方式對(duì)列表OPEN重新排序。

返回步驟3 。

生成一個(gè)僅包含開始節(jié)點(diǎn)n0的搜索樹Tr。把n0放在一個(gè)稱為OPEN的有序列表中。

生成一個(gè)初始值為空的列表CLOSED。

如果OPEN為空，則失敗并退出。

選出OPEN中的第一個(gè)節(jié)點(diǎn)，并將它從OPEN中移出，放入CLOSED中。稱該節(jié)點(diǎn)為n。

如果n是目標(biāo)節(jié)點(diǎn)，順著Tr中的弧從n回溯到n0找到一條路徑，獲得解決方案，則成功退出（弧在第6步產(chǎn)生）。

擴(kuò)展節(jié)點(diǎn)n，生成n的后繼節(jié)點(diǎn)集M。通過在Tr中建立從n到M中每個(gè)成員的弧生成n的后繼。

按照任意的模式或啟發(fā)式方式對(duì)列表OPEN重新排序。

返回步驟3 。

這個(gè)算法可用來執(zhí)行最優(yōu)搜索、廣度優(yōu)先搜索或深度優(yōu)先搜索。在廣度優(yōu)先搜索中，新節(jié)點(diǎn)只要放在OPEN的尾部即可（先進(jìn)先出， FIFO），節(jié)點(diǎn)不用重排。在深度優(yōu)先搜索中，新節(jié)點(diǎn)放在OPEN的開始（后進(jìn)先出,LIFO）。

在最優(yōu)（也叫啟發(fā)式）搜索中，按照節(jié)點(diǎn)的啟發(fā)式方式來重排OPEN。

三、略談A*搜索算法

用最優(yōu)搜索算法詳細(xì)說明GRAPHSEARCH。最優(yōu)搜索算法根據(jù)函數(shù)的增加值，(在上述第7步)重排OPEN中的節(jié)點(diǎn)，如8數(shù)碼問題。把GRAPHSEACH的這種算法稱為算法A*。

下面將會(huì)看到，定義使A*執(zhí)行廣度搜索或相同代價(jià)搜索的函數(shù)是可行的。為了確定要用的函數(shù)族，必須先介紹一些其他符號(hào)。

設(shè)g(n) = 從開始節(jié)點(diǎn)n0到節(jié)點(diǎn)n的一個(gè)最小代價(jià)路徑的代價(jià)。

設(shè)h(n) =節(jié)點(diǎn)n和目標(biāo)節(jié)點(diǎn)（遍及所有可能的目標(biāo)節(jié)點(diǎn)以及從n到它們的所有可能路徑）之間的最小代價(jià)路徑的實(shí)際代價(jià)。

那么f(n) = g(n) + h(n)就是從n0到目標(biāo)節(jié)點(diǎn)并且經(jīng)過節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)。

注意f(n0)= h(n0)是從n0到目標(biāo)節(jié)點(diǎn)的一個(gè)（不受限的）最小代價(jià)路徑的代價(jià)。

對(duì)每個(gè)節(jié)點(diǎn)n，設(shè)g?(n)（深度因子）是由A*發(fā)現(xiàn)的到節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)，h?(n)（啟發(fā)因子）是h(n)的某個(gè)估計(jì)。

在算法A*中，我們用?f(n)= g?(n)+ h?(n)。

注意，如果算法A*中的恒等于0，就成為相同代價(jià)搜索。這些定義示例在圖3中。

算法A*：

生成一個(gè)只包含開始節(jié)點(diǎn)n0的搜索圖G，把n0放在一個(gè)叫OPEN的列表上。

生成一個(gè)列表CLOSED，它的初始值為空。

如果OPEN為空，則失敗退出。

選擇OPEN上的第一個(gè)節(jié)點(diǎn)，把它從OPEN中移入CLOSED，稱該節(jié)點(diǎn)為n。

如果n是目標(biāo)節(jié)點(diǎn)，順著G中，從n到n0的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹，在第7步建立）。

擴(kuò)展節(jié)點(diǎn)n，生成其后繼節(jié)點(diǎn)集M，在G中，n的祖先不能在M中。在G中安置M的成員，使它們成為n的后繼。

從M的每一個(gè)不在G中的成員建立一個(gè)指向n的指針（例如，既不在OPEN中，也不在CLOSED中）。把M的這些成員加到OPEN中。對(duì)的每一個(gè)已在OPEN 中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n，就把它的指針指向n。對(duì)已在CLOSE中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。

按遞增值，重排OPEN（相同最小值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決）。

返回第3步。

生成一個(gè)只包含開始節(jié)點(diǎn)n0的搜索圖G，把n0放在一個(gè)叫OPEN的列表上。

生成一個(gè)列表CLOSED，它的初始值為空。

如果OPEN為空，則失敗退出。

選擇OPEN上的第一個(gè)節(jié)點(diǎn)，把它從OPEN中移入CLOSED，稱該節(jié)點(diǎn)為n。

如果n是目標(biāo)節(jié)點(diǎn)，順著G中，從n到n0的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹，在第7步建立）。

擴(kuò)展節(jié)點(diǎn)n，生成其后繼節(jié)點(diǎn)集M，在G中，n的祖先不能在M中。在G中安置M的成員，使它們成為n的后繼。

從M的每一個(gè)不在G中的成員建立一個(gè)指向n的指針（例如，既不在OPEN中，也不在CLOSED中）。把M的這些成員加到OPEN中。對(duì)的每一個(gè)已在OPEN 中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n，就把它的指針指向n。對(duì)已在CLOSE中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。

按遞增值，重排OPEN（相同最小值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決）。

返回第3步。

在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達(dá)一個(gè)節(jié)點(diǎn)的代價(jià)比現(xiàn)存的路徑代價(jià)低，我們就要重定向指向該節(jié)點(diǎn)的指針。已經(jīng)在CLOSED中的節(jié)點(diǎn)子孫的重定向保存了后面的搜索結(jié)果，但是可能需要指數(shù)級(jí)的計(jì)算代價(jià)。

因此，第7步常常不會(huì)實(shí)現(xiàn)。隨著搜索的向前推進(jìn)，其中有些指針最終將會(huì)被重定向。

四、啟發(fā)式算法相關(guān)問題

4.1、啟發(fā)式算法與最短路徑問題

啟發(fā)式通常用于資訊充份的搜尋算法，例如最好優(yōu)先貪婪算

法與A*。

最好優(yōu)先貪婪算法會(huì)為啟發(fā)式函數(shù)選擇最低代價(jià)的節(jié)點(diǎn)；

A*則會(huì)為g(n) + h(n)選擇最低代價(jià)的節(jié)點(diǎn)，此g(n)是從起始節(jié)點(diǎn)到目前節(jié)點(diǎn)的路徑的確實(shí)代價(jià)。

如果h(n)是可接受的（admissible）意即h(n)未曾付出超過達(dá)到目標(biāo)的代價(jià)，則A*一定會(huì)找出最佳解。

最能感受到啟發(fā)式算法好處的經(jīng)典問題是n-puzzle。此問題在計(jì)算錯(cuò)誤的拼圖圖形，與計(jì)算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠(yuǎn)時(shí)，使用了本算法。注意，上述兩條件都必須在可接受的范圍內(nèi)。

曼哈頓距離是一個(gè)簡(jiǎn)單版本的n-puzzle問題，因?yàn)槲覀兗僭O(shè)可以獨(dú)立移動(dòng)一個(gè)方塊到我們想要的位置，而暫不考慮會(huì)移到其他方塊的問題。

給我們一群合理的啟發(fā)式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}則是個(gè)可預(yù)測(cè)這些函式的啟發(fā)式函式。

一個(gè)在1993年由A.E. Prieditis寫出的程式ABSOLVER就運(yùn)用了這些技術(shù)，這程式可以自動(dòng)為問題產(chǎn)生啟發(fā)式算法。ABSOLVER為8-puzzle產(chǎn)生的啟發(fā)式算法優(yōu)于任何先前存在的！而且它也發(fā)現(xiàn)了第一個(gè)有用的解魔術(shù)方塊的啟發(fā)式程式。

4.2、啟發(fā)式算法對(duì)運(yùn)算效能的影響

任何的搜尋問題中，每個(gè)節(jié)點(diǎn)都有b個(gè)選擇以及到達(dá)目標(biāo)的深度d，一個(gè)毫無技巧的算法通常都要搜尋bd個(gè)節(jié)點(diǎn)才能找到答案。

啟發(fā)式算法借由使用某種切割機(jī)制降低了分叉率(branching factor)以改進(jìn)搜尋效率，由b降到較低的b'。分叉率可以用來定義啟發(fā)式算法的偏序關(guān)系，例如：若在一個(gè)n節(jié)點(diǎn)的搜尋樹上，h1(n)的分叉率較h2(n)低，則 h1(n) < h2(n)。

啟發(fā)式為每個(gè)要解決特定問題的搜尋樹的每個(gè)節(jié)點(diǎn)提供了較低的分叉率，因此它們擁有較佳效率的計(jì)算能力。