人工智能09-31

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

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

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

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

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

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

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

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

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

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

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

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

13、使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8）按遞增 值，重排OPEN。9）返回步驟3。在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達一個節(jié)點的代價比現(xiàn)存的路徑代價低，我們就重定向指向該節(jié)點的指針。已經在CLOSED中的節(jié)點子孫的重定向保存了后面的搜索結果，但是需要指數(shù)級的計算代價。因此，第7步常常不會實現(xiàn)。隨著搜索向前推進，其中有些指針最終將會被重定向。ff9.2.2 A*的可接納性的可接納性對圖和施加一些條件可以保證應用到圖的算法A*總能找到最小代價路徑。圖的條件是：1）圖中每個節(jié)點的后繼是有限的（如果有的話）2）圖中所有弧的代價都大于某個正數(shù)3） 的條件是：對搜索圖中的所有節(jié)點n， (

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

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

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

17、的節(jié)點，最終它將在搜索樹上擴展比任何預設的深度約束更深的節(jié)點，因為我們已經假設正在搜索的圖有有限個分枝因子。因為每個弧的代價都比0大，故在OPEN中的所有節(jié)點的值將最終超過f(n0)。這將和引理產生矛盾。A*終止于一條最優(yōu)路徑終止于一條最優(yōu)路徑：A*只能在第3步（OPEN為空）或第5步（在一個目標節(jié)點）終止。一個第3步的終止只能出現(xiàn)在不包含任何目標節(jié)點的有限圖中。只要有一個目標節(jié)點，定理都聲稱能找到到達目標的一條最佳路徑。因此A*終止于一個目標節(jié)點。假如它終止于發(fā)現(xiàn)了一個 非最佳目標ng2，f(ng2)f(n0)，當有一個最佳目標ng1時， ng1 ng2， f(ng1)=f(n0)。在ng2

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

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

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

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

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

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

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