1、第第9章章 啟發(fā)式搜索啟發(fā)式搜索使用評估函數(shù)使用評估函數(shù)一個(gè)通用的圖搜索算法一個(gè)通用的圖搜索算法啟發(fā)式函數(shù)和搜索效率啟發(fā)式函數(shù)和搜索效率補(bǔ)充讀物和討論補(bǔ)充讀物和討論9.1 使用評估函數(shù)使用評估函數(shù)除了搜索過程不是從開始節(jié)點(diǎn)統(tǒng)一向外擴(kuò)展外，本章描述的搜索過程有點(diǎn)像廣度優(yōu)先搜索。不同的是，它會(huì)優(yōu)先順著有啟發(fā)性和它會(huì)優(yōu)先順著有啟發(fā)性和具有特定信息的節(jié)點(diǎn)搜索下去具有特定信息的節(jié)點(diǎn)搜索下去，這些節(jié)點(diǎn)可能是到達(dá)目標(biāo)的最好路徑。我們稱這個(gè)過程為最優(yōu)（最優(yōu)（best-first）或啟發(fā)式搜索）或啟發(fā)式搜索。其基本思想如下：1）假定有一個(gè)啟發(fā)式（評估）函數(shù)假定有一個(gè)啟發(fā)式（評估）函數(shù) ，可以幫助確定下一個(gè)要擴(kuò)，

2、可以幫助確定下一個(gè)要擴(kuò)展的最優(yōu)節(jié)點(diǎn)展的最優(yōu)節(jié)點(diǎn)。采用一個(gè)約定，即 的值小表示找到了好的節(jié)點(diǎn)。的值小表示找到了好的節(jié)點(diǎn)。這個(gè)函數(shù)基于指定問題域的信息，它是狀態(tài)描述的一個(gè)實(shí)數(shù)值函這個(gè)函數(shù)基于指定問題域的信息，它是狀態(tài)描述的一個(gè)實(shí)數(shù)值函數(shù)。數(shù)。2）下一個(gè)要擴(kuò)展的節(jié)點(diǎn)n是 (n)值最小的節(jié)點(diǎn)（假定節(jié)點(diǎn)擴(kuò)展產(chǎn)假定節(jié)點(diǎn)擴(kuò)展產(chǎn)生一個(gè)節(jié)點(diǎn)的所有后繼生一個(gè)節(jié)點(diǎn)的所有后繼）。3）當(dāng)下一個(gè)要擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)過程終止。fff9.1 使用評估函數(shù)使用評估函數(shù)常?？梢詾樽顑?yōu)搜索指定好的評估函數(shù)常常可以為最優(yōu)搜索指定好的評估函數(shù)。如在如在8數(shù)碼問題中，可數(shù)碼問題中，可以用不正確位置的數(shù)字個(gè)數(shù)作為狀態(tài)描述好壞的一個(gè)度量

3、以用不正確位置的數(shù)字個(gè)數(shù)作為狀態(tài)描述好壞的一個(gè)度量： (n)=位置不正確的數(shù)字個(gè)數(shù)（和目標(biāo)相比）在搜索過程中采用這個(gè)啟發(fā)式函數(shù)將產(chǎn)生下圖。每個(gè)節(jié)點(diǎn)的數(shù)值是該節(jié)點(diǎn)的 值。ff一個(gè)啟發(fā)式搜索過程的可能結(jié)果42831647528316452831475283164776283147553283145231475283147662314756785到目標(biāo)831452374566234571831452831456731452到無結(jié)果的漫游314531458553343439.1 使用評估函數(shù)使用評估函數(shù)在搜索過程中需要偏向有利于回溯到早期路徑的搜索（為了避免為了避免由于過分的優(yōu)化試探而陷入由于過分的優(yōu)

4、化試探而陷入“花園小徑花園小徑”）。因此我們加了一個(gè)“深度因子” 給 : , 是對圖中節(jié)點(diǎn)n的“深度”估計(jì)（即從開始節(jié)點(diǎn)到n的最短路徑長度）， 是對節(jié)點(diǎn)n的啟發(fā)或評估。如果 =不正確位置的數(shù)字個(gè)數(shù)（和目標(biāo)相比）， =搜索圖中節(jié)點(diǎn)n的深度。在這種情況下，搜索相當(dāng)直接地朝著目標(biāo)前進(jìn)。兩個(gè)重要問題：第一，如何為最優(yōu)搜索決定評估函數(shù)？第二，最第一，如何為最優(yōu)搜索決定評估函數(shù)？第二，最優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？f)()()(nhngnf)(nh)(ng)(nh)(ng9.2 一個(gè)通用的圖圖搜索算法一個(gè)通用的圖圖搜索算法為了更準(zhǔn)

5、確地解釋啟發(fā)式搜索過程，提出一個(gè)通用的圖搜索算法，它允許各種用戶偏愛啟發(fā)式的或盲目的，進(jìn)行定制。我們把這個(gè)算法叫做圖搜索圖搜索（GRAPHSEARCH）。1）生成一個(gè)僅包含開始節(jié)點(diǎn)n0的搜索樹Tr。把n0放在一個(gè)稱為OPEN的有序列表中。2）生成一個(gè)初始值為空的列表CLOSED。3）如果OPEN為空，則失敗并退出4）選出OPEN中的第一個(gè)節(jié)點(diǎn)，并將它從OPEN中移出，放入CLOSED中，稱該節(jié)點(diǎn)為n。5）如果n是目標(biāo)節(jié)點(diǎn)，順著Tr中的弧從n回溯到n0找到一條路徑，獲得解決方案，則成功退出6）擴(kuò)展節(jié)點(diǎn)n，生成n的后繼節(jié)點(diǎn)集M。通過在Tr中建立從n到M中每個(gè)成員的弧生成n的后繼7）按照任意的模式或

6、啟發(fā)式方式對列表OPEN重新排序。8）返回步驟39.2 一個(gè)通用的圖圖搜索算法一個(gè)通用的圖圖搜索算法該算法可用來執(zhí)行最優(yōu)搜索、廣度優(yōu)先搜索或深度優(yōu)先搜索最優(yōu)搜索、廣度優(yōu)先搜索或深度優(yōu)先搜索。在廣度優(yōu)先搜索中，新節(jié)點(diǎn)只要放在OPEN的尾部即可（先進(jìn)先出，F(xiàn)IFO），節(jié)點(diǎn)不用重排。在深度優(yōu)先搜索中，新節(jié)點(diǎn)放在OPEN的開始（后進(jìn)先出，LIFO） 。在最優(yōu)（啟發(fā)式）搜索中，按照在最優(yōu)（啟發(fā)式）搜索中，按照節(jié)點(diǎn)的啟發(fā)式方式來重排節(jié)點(diǎn)的啟發(fā)式方式來重排OPEN。 開始節(jié)點(diǎn)n f(n )=到達(dá)一個(gè)目標(biāo)的最低代價(jià)(最優(yōu))路徑的代價(jià)0 0 一條弧的代價(jià) 5 34 76 2nf(n)=g(n) + h(n)=到

7、達(dá)一個(gè)目標(biāo)的最低代價(jià)路徑的代價(jià)-僅通過節(jié)點(diǎn)ng(n)=從n 到n的最佳路徑的代價(jià)(本例中為8)h(n)=從節(jié)點(diǎn)n到一個(gè)目標(biāo)的優(yōu)化路徑的代價(jià)0f ,g , h 分別是對f ,g ,k的估計(jì)f= g + h啟發(fā)式搜索符號(hào)9.2.1 算法算法A*用最優(yōu)搜索算法最優(yōu)搜索算法詳細(xì)說明GRAPHSEARCH。最優(yōu)搜索算法根據(jù)函數(shù) 的增加值重排OPEN中的節(jié)點(diǎn)。稱為A*算法。定義使A*執(zhí)行廣度搜索或相同代價(jià)搜索的函數(shù) 是可行的。設(shè)h(n)=節(jié)點(diǎn)n和目標(biāo)節(jié)點(diǎn)（遍及所有可能的目標(biāo)節(jié)點(diǎn)以及從n到它們的所有可能路徑）之間的最小代價(jià)路徑的實(shí)際代價(jià)。設(shè)g(n)=從開始節(jié)點(diǎn)n0到節(jié)點(diǎn)n的一個(gè)最小代價(jià)路徑的代價(jià)那么f(n)

8、=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à)。對每個(gè)節(jié)點(diǎn)n，設(shè) （啟發(fā)因子）是h(n)的某個(gè)估計(jì)， （深度因子）是由A*發(fā)現(xiàn)的到節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)。在算法A*中，用 。注意，如果算法A*中的 恒等于0，就成為相同代價(jià)搜索。ff)(nh)(ngghfh9.2.1 算法算法A*8數(shù)碼搜索過程是A*應(yīng)用的一個(gè)例子。假定了單位弧代價(jià)，因此g(n)就是圖中節(jié)點(diǎn)n的深度。如果要搜索的隱式圖不是一棵樹會(huì)怎樣呢？假如有超過一個(gè)動(dòng)作序列能從開始狀態(tài)到達(dá)相同的環(huán)境狀態(tài)。例如8數(shù)碼隱式圖顯然就不是

9、一棵樹，因?yàn)閯?dòng)作是可逆的即任何節(jié)點(diǎn)n的每一個(gè)后繼都可以使n作為它的一個(gè)后繼。在那種情況下，它們?nèi)菀妆缓雎?，只要在?jié)點(diǎn)的后繼中不包括它的雙親就行了。把GRAPHSEARCH中的第6步改為：6）擴(kuò)展節(jié)點(diǎn)n，生成后繼集合M，n的雙親不能在M中。通過在Tr中建立從n到M中每個(gè)成員的弧生成n的后繼?？紤]到更長的循環(huán)，把6改為：6）擴(kuò)展節(jié)點(diǎn)n，生成后繼集合M，n的祖先不能在M中。通過在Tr中建立從n到M中每個(gè)成員的弧生成n的后繼。9.2.1 算法算法A*為了檢查這些更長的循環(huán)，要檢查標(biāo)識(shí)節(jié)點(diǎn)n祖先的數(shù)據(jù)結(jié)構(gòu)。對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這進(jìn)一步增加了算法的復(fù)雜度。修改第6步的算法在搜索目標(biāo)路徑時(shí)避免了再循環(huán)，但是仍

10、有可能通過不同的路徑到達(dá)相同的環(huán)境狀態(tài)。一個(gè)方法就是簡單地忽略它。算法不檢查M中的一個(gè)節(jié)點(diǎn)是否已在OPEN或CLOSED中。因此算法對那種可能性就健忘了，以致它可能通過不同的路徑到達(dá)相同的節(jié)點(diǎn)。這個(gè)相同節(jié)點(diǎn)在Tr中重復(fù)多次，重復(fù)的次數(shù)是算法發(fā)現(xiàn)到達(dá)該節(jié)點(diǎn)的不同路徑數(shù)目。如果Tr中的兩個(gè)節(jié)點(diǎn)被同樣的數(shù)據(jù)結(jié)構(gòu)標(biāo)識(shí)，那么它們下面有相同的子樹。也就是說，算法會(huì)重復(fù)搜索結(jié)果。對 施加適當(dāng)?shù)臈l件，當(dāng)A* 首次擴(kuò)展Tr中的節(jié)點(diǎn)n時(shí)，它已經(jīng)找到了到達(dá)節(jié)點(diǎn)n并且有最小值 的一條路徑。ff9.2.1 算法算法A* 為了防止在前述條件不成立下 的重復(fù)搜索，需要對算法A*進(jìn)行一些修改。因?yàn)樗阉骺梢皂樦煌穆窂降竭_(dá)相

11、同的節(jié)點(diǎn)，因此算法A*會(huì)產(chǎn)生一個(gè)搜索圖G。G是A*擴(kuò)展開始節(jié)點(diǎn)、開始節(jié)點(diǎn)的后繼等等而產(chǎn)生的節(jié)點(diǎn)和弧的結(jié)構(gòu)。A*也包含一個(gè)搜索樹Tr。Tr是G的一個(gè)子圖，它是到達(dá)搜索圖中所有節(jié)點(diǎn)的最優(yōu)路徑生成樹。為了完整起見，闡述一下包含搜索圖的A*算法。很少需要這個(gè)算法，因?yàn)槲覀兂３?施加一定的條件以保證當(dāng)算法A*擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，它已經(jīng)發(fā)現(xiàn)了到達(dá)該節(jié)點(diǎn)的最小代價(jià)路徑。f9.2.1 算法算法A*1）生成一個(gè)僅包含開始節(jié)點(diǎn)n0的搜索圖G。把n0放在一個(gè)叫OPEN的有序列表中。2）生成一個(gè)列表CLOSED。它的初始值為空3）如果OPEN為空，則失敗并退出4）選出OPEN中的第一個(gè)節(jié)點(diǎn)，并將它從OPEN中移出，放入

12、CLOSED中，稱該節(jié)點(diǎn)為n。5）如果n是目標(biāo)節(jié)點(diǎn)，順著G中從n到n0的指針找到一條路徑，獲得解決方案，成功退出。（該指針定義了一個(gè)搜索樹，在第7步建立）6）擴(kuò)展節(jié)點(diǎn)n，生成n的后繼節(jié)點(diǎn)集M。在G中，n的祖先不能在M中。在G中安置M的成員，使它們成為n的后繼。9.2.1 算法算法A*7）從M中的每一個(gè)不在G中的成員建立一個(gè)指向n的指針（例如，既不在OPEN中，也不在CLOSED中）。把M的這些成員加到OPEN中。對M的每一個(gè)已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n，就把它的指針指向n。對已在CLOSED中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以

13、使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8）按遞增 值，重排OPEN。9）返回步驟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ì)算代價(jià)。因此，第7步常常不會(huì)實(shí)現(xiàn)。隨著搜索向前推進(jìn)，其中有些指針最終將會(huì)被重定向。ff9.2.2 A*的可接納性的可接納性對圖和施加一些條件可以保證應(yīng)用到圖的算法A*總能找到最小代價(jià)路徑。圖的條件是：1）圖中每個(gè)節(jié)點(diǎn)的后繼是有限的（如果有的話）2）圖中所有弧的代價(jià)都大于某個(gè)正數(shù)3） 的條件是：對搜索圖中的所有節(jié)點(diǎn)n， (

14、n) h(n)。也就是說決不會(huì)超過實(shí)際值h的估計(jì)。這樣的h函數(shù)有時(shí)也成為優(yōu)化概算機(jī)。一般來說，找到滿足這個(gè)低約束條件的一般來說，找到滿足這個(gè)低約束條件的并不困難并不困難。例如在城市路由問題中，從城市n到目標(biāo)的直線距離就是從n到目標(biāo)節(jié)點(diǎn)的最佳路徑距離的一個(gè)最低約束。8數(shù)碼問題中，不在正確位置的數(shù)碼個(gè)數(shù)就是到達(dá)目標(biāo)步數(shù)的一個(gè)最小約束。9.2.2 A*的可接納性的可接納性用這三個(gè)約束條件，只要存在到達(dá)目標(biāo)的路徑，算法A*可以保證找到一條到達(dá)目標(biāo)的最佳路徑。該結(jié)果作為一個(gè)定理。定理定理9.1：如果圖和：如果圖和具有上述的穩(wěn)定條件，而且從開始節(jié)點(diǎn)到目具有上述的穩(wěn)定條件，而且從開始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有一條有限

15、代價(jià)的路徑，那么算法標(biāo)節(jié)點(diǎn)有一條有限代價(jià)的路徑，那么算法A*保證終止于到達(dá)目標(biāo)保證終止于到達(dá)目標(biāo)的一條最小代價(jià)路徑。的一條最小代價(jià)路徑。證明：證明：證明的主要部分是下面的重要引理。為了獲得關(guān)于A*為什么能保證發(fā)現(xiàn)最優(yōu)路徑的知覺知識(shí)，完全理解這個(gè)引理是重要的。引理引理9.1：在：在A*終止前的每一步，總是有一個(gè)節(jié)點(diǎn)終止前的每一步，總是有一個(gè)節(jié)點(diǎn)n*，它，它OPEN上上有下面的特性：有下面的特性：1）n*在到達(dá)目標(biāo)的一條最佳路徑上2）A*已經(jīng)發(fā)現(xiàn)了到達(dá)n*的一條最佳路徑3） (n*) f(n0)f9.2.2 A*的可接納性的可接納性引理證明引理證明：為了證明A*每一步保證引理結(jié)論，只要證明（1）在

16、算法開始時(shí)結(jié)論正確；（2）如果一個(gè)節(jié)點(diǎn)擴(kuò)展前結(jié)論正確，那么節(jié)點(diǎn)擴(kuò)展后結(jié)論繼續(xù)正確。我們稱這種證明方法為數(shù)學(xué)歸納法數(shù)學(xué)歸納法?；緱l件基本條件：在搜索開始時(shí)（當(dāng)節(jié)點(diǎn)n0準(zhǔn)備擴(kuò)展時(shí)）， n0在OPEN上，它是到達(dá)目標(biāo)的一條最佳路徑，A*已經(jīng)發(fā)現(xiàn)這條路徑，而且，因?yàn)?(n0)= (n0) f(n0)，故 (n0) f(n0)。因此，在該階段，節(jié)點(diǎn)n0可以是引理中的n*。歸納步驟歸納步驟：假設(shè)在節(jié)點(diǎn)m（m0）擴(kuò)展時(shí)引理的結(jié)論是正確的，（用這個(gè)假設(shè)）證明在節(jié)點(diǎn)m+1擴(kuò)展時(shí)引理是正確的。ff9.2.2 A*的可接納性的可接納性A*必須終止必須終止。假如它不會(huì)終止。在這種情況下，A*始終不斷地?cái)U(kuò)展OPEN上

17、的節(jié)點(diǎn)，最終它將在搜索樹上擴(kuò)展比任何預(yù)設(shè)的深度約束更深的節(jié)點(diǎn)，因?yàn)槲覀円呀?jīng)假設(shè)正在搜索的圖有有限個(gè)分枝因子。因?yàn)槊總€(gè)弧的代價(jià)都比0大，故在OPEN中的所有節(jié)點(diǎn)的值將最終超過f(n0)。這將和引理產(chǎn)生矛盾。A*終止于一條最優(yōu)路徑終止于一條最優(yōu)路徑：A*只能在第3步（OPEN為空）或第5步（在一個(gè)目標(biāo)節(jié)點(diǎn)）終止。一個(gè)第3步的終止只能出現(xiàn)在不包含任何目標(biāo)節(jié)點(diǎn)的有限圖中。只要有一個(gè)目標(biāo)節(jié)點(diǎn)，定理都聲稱能找到到達(dá)目標(biāo)的一條最佳路徑。因此A*終止于一個(gè)目標(biāo)節(jié)點(diǎn)。假如它終止于發(fā)現(xiàn)了一個(gè) 非最佳目標(biāo)ng2，f(ng2)f(n0)，當(dāng)有一個(gè)最佳目標(biāo)ng1時(shí)， ng1 ng2， f(ng1)=f(n0)。在ng2

18、終止時(shí)， (ng2) f(ng2)f(n0)。但是在A*選擇ng2進(jìn)行擴(kuò)展之前，根據(jù)引理在OPEN上有一個(gè)節(jié)點(diǎn)n*，它在最優(yōu)路徑上，且 (n*) f(n0)。因此，A*不可能選擇ng2進(jìn)行擴(kuò)展，因?yàn)锳*總是選擇有最小 值的節(jié)點(diǎn)進(jìn)行擴(kuò)展，而 (n*) f(n0) f(ng2)ffff9.2.2 A*的可接納性的可接納性稱任何保證能找到一條到達(dá)目標(biāo)的最佳路徑的算法是可接納的稱任何保證能找到一條到達(dá)目標(biāo)的最佳路徑的算法是可接納的。因此，在定理的三個(gè)條件下，A*是可接納的。任何沒有高過h的函數(shù)都是可接納的。如果A*的兩個(gè)版本A1*和 A2* ，其差別在于對所有的非目標(biāo)節(jié)點(diǎn)， 1 2那么就說A1*比A2

19、*更靈通（靈通（informed）。9.2.2 A*的可接納性的可接納性如果A2*比A1*更靈通，那么對任何有從n0到目標(biāo)節(jié)點(diǎn)的一條路徑的圖，在搜索終止時(shí)，被A2*擴(kuò)展過的每一個(gè)節(jié)點(diǎn)也被A1*擴(kuò)展過。可以得出擴(kuò)展的節(jié)點(diǎn)至少和的一樣多，這個(gè)更靈通的算法也就更有效。因此我們要尋找盡可能接近真實(shí)函數(shù)h的函數(shù)（為了搜索效率），同時(shí)有不能超過它們（為了可接納性）。當(dāng)然在衡量總的搜索效率時(shí)，也應(yīng)當(dāng)考慮計(jì)算的代價(jià)。最靈通的算法是h，但是典型地講，這樣的 只能在很高的代價(jià)下，通過完成我們正在嘗試的每一個(gè)搜索才能得到。f9.2.2 A*的可接納性的可接納性當(dāng)對所有的節(jié)點(diǎn)0時(shí)，得到相同代價(jià)搜索相同代價(jià)搜索（搜索順

20、著相同代價(jià)的邊沿向外擴(kuò)展）。當(dāng) (n)=(n)=深度(n)時(shí)，得到廣度優(yōu)先搜索廣度優(yōu)先搜索法，它順著相同深度的邊沿向外擴(kuò)展。相同代價(jià)和廣度優(yōu)先算法都是A* 0的特殊情況，故它們都是可它們都是可接納的。接納的。f9.2.3 一致性（或單調(diào)）條件一致性（或單調(diào)）條件考慮到一對節(jié)點(diǎn)（ ni，nj）， nj是ni的一個(gè)后繼。如果在搜索圖中所有的這種節(jié)點(diǎn)對都滿足下述條件： (ni)- (nj) c(ni，nj)其中c(ni，nj)是從ni到nj的代價(jià)。我們就說h服從一致性條件。著這個(gè)條件陳述了順著搜索圖中的任何路徑，到達(dá)目標(biāo)的最優(yōu)（剩余）代價(jià)的估價(jià)的減少不會(huì)大于該路徑弧代價(jià)。也就是說，在考慮了一個(gè)弧的已

21、知代價(jià)后，啟發(fā)式函數(shù)在局部是一致的。一致性函數(shù)暗示了當(dāng)搜索樹中節(jié)點(diǎn)的值開始遠(yuǎn)離節(jié)點(diǎn)時(shí)，它是單一致性函數(shù)暗示了當(dāng)搜索樹中節(jié)點(diǎn)的值開始遠(yuǎn)離節(jié)點(diǎn)時(shí)，它是單調(diào)非遞減的調(diào)非遞減的。設(shè)ni，nj是由A*在搜索樹上產(chǎn)生的兩個(gè)節(jié)點(diǎn)， nj是ni的后繼。如果滿足一致性條件，就有： (nj) (ni)ff9.2.3 一致性（或單調(diào)）條件一致性（或單調(diào)）條件一致性條件（對 ）也常被稱為單調(diào)條件（對 ）定理定理9.3: 如果如果上的一致性條件被滿足，那么當(dāng)上的一致性條件被滿足，那么當(dāng)A*擴(kuò)展節(jié)點(diǎn)時(shí)，擴(kuò)展節(jié)點(diǎn)時(shí)，它已經(jīng)找到了到達(dá)節(jié)點(diǎn)它已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的一條最優(yōu)路徑的一條最優(yōu)路徑。f9.2.3 一致性（或單調(diào)）條件一

22、致性（或單調(diào)）條件一致性條件是很重要的，因?yàn)楫?dāng)它被滿足時(shí)，A*不再需要重定向指針（第7步）。搜索一個(gè)圖與搜索一個(gè)樹就沒有什么區(qū)別了。滿足一致性條件時(shí)，可以為A*的可接納性給出一個(gè)簡單直觀的論證。1） 的單調(diào)性暗示了搜索順著 值增大的邊緣向外擴(kuò)展。2）因此，被選擇的第一個(gè)目標(biāo)節(jié)點(diǎn)就是有最小 值的一個(gè)目標(biāo)節(jié)點(diǎn)。3）對任何目標(biāo)節(jié)點(diǎn)ng， (nj) = (nj) （這里，我們用了這樣的事實(shí)：如果函數(shù)是一致的，它也將決不會(huì)比真正的h函數(shù)大。4）因此，第一個(gè)被選擇的目標(biāo)節(jié)點(diǎn)將是有最小值的目標(biāo)節(jié)點(diǎn)。5）作為定理9.3的一個(gè)結(jié)論，無論何時(shí)（特別地）當(dāng)一個(gè)目標(biāo)節(jié)點(diǎn)ng被選擇擴(kuò)展時(shí)，我們已經(jīng)找到了到達(dá)那個(gè)目標(biāo)節(jié)點(diǎn)

23、的一個(gè)最短路徑。 (nj) =g (nj) 6）第一個(gè)被選擇的目標(biāo)節(jié)點(diǎn)將是算法發(fā)現(xiàn)的最佳路徑的目標(biāo)節(jié)點(diǎn)。fff9.2.4 迭代加深的迭代加深的A*廣度優(yōu)先搜索的存儲(chǔ)需求會(huì)隨著搜索空間中目標(biāo)深度的增加呈指數(shù)遞增。盡管好的啟發(fā)式搜索減少了分枝因子，但啟發(fā)式搜索還是有如上一樣的缺點(diǎn)。迭代加深搜索，不但允許我們找到最小代價(jià)路徑，而且存儲(chǔ)需求隨著深度增加呈線性增長。由由Korf提出的迭代加深提出的迭代加深A(yù)*（IDA*）方法能獲得同啟發(fā)式搜索相）方法能獲得同啟發(fā)式搜索相似的好處。通過使用并行似的好處。通過使用并行IDA*的并行實(shí)現(xiàn)能獲得更高的效率的并行實(shí)現(xiàn)能獲得更高的效率。9.2.5 迭代最優(yōu)搜索迭代最

24、優(yōu)搜索由Korf提出的遞歸最優(yōu)搜索，RBFS方法比IDA*用到的存儲(chǔ)稍微多一點(diǎn)，但是比IDA*產(chǎn)生的節(jié)點(diǎn)少。9.3 啟發(fā)式函數(shù)和搜索效率啟發(fā)式函數(shù)和搜索效率在決定A*效率時(shí)，啟發(fā)式函數(shù)的選擇是至關(guān)重要的。用0保證了可接納性，但生成了相同代價(jià)搜索，因而效率不高。 等于h上較低約束的最高可能值，不但可以擴(kuò)展較少的節(jié)點(diǎn)，還能維持可接納性。在8數(shù)碼問題中(n)=W(n)（其中W(n) 是不在正確位置的數(shù)碼個(gè)數(shù)）就是h(n)上的一個(gè)較低約束，但是它沒有提供對數(shù)碼狀態(tài)難度（按照到達(dá)目標(biāo)的步數(shù)）的一個(gè)很好的估計(jì)。一個(gè)更好的估計(jì)是函數(shù)(n)=P(n)， P(n)是每個(gè)數(shù)碼離開目標(biāo)點(diǎn)的Manhatan距離總和。9.3 啟發(fā)式函數(shù)和搜索效率啟發(fā)式函數(shù)和搜索效率在選擇函數(shù)時(shí)，必須考慮計(jì)算本身的計(jì)算量。模型松弛越小，啟發(fā)式函數(shù)就