1、第第9章章 啟發(fā)式搜索啟發(fā)式搜索 第二部分第二部分 狀態(tài)空間搜索狀態(tài)空間搜索使用評估函數(shù)使用評估函數(shù) 除了搜索過程不是從開始節(jié)點(diǎn)統(tǒng)一向外擴(kuò)展除了搜索過程不是從開始節(jié)點(diǎn)統(tǒng)一向外擴(kuò)展外，下面描述的搜索過程有點(diǎn)像廣度優(yōu)先搜索，外，下面描述的搜索過程有點(diǎn)像廣度優(yōu)先搜索，不同的是，它會優(yōu)先順著有啟發(fā)性和具有特定信不同的是，它會優(yōu)先順著有啟發(fā)性和具有特定信息的節(jié)點(diǎn)搜索下去，這些節(jié)點(diǎn)可能是到達(dá)目標(biāo)的息的節(jié)點(diǎn)搜索下去，這些節(jié)點(diǎn)可能是到達(dá)目標(biāo)的最好路徑。我們稱這個過程為最好路徑。我們稱這個過程為最優(yōu)最優(yōu)( (best-first)best-first)或啟發(fā)式搜索或啟發(fā)式搜索。 其基本思想：其基本思想： 1)

2、1)假定有一個啟發(fā)式假定有一個啟發(fā)式( (評估評估) )函數(shù)，函數(shù)， 可以幫助確定下一個可以幫助確定下一個要擴(kuò)展的最優(yōu)節(jié)點(diǎn)要擴(kuò)展的最優(yōu)節(jié)點(diǎn)。我們采用一個約定，即我們采用一個約定，即 的值小表示找的值小表示找到了好的節(jié)點(diǎn)（這個函數(shù)基于指定問題域的信息，它是狀態(tài)到了好的節(jié)點(diǎn)（這個函數(shù)基于指定問題域的信息，它是狀態(tài)描述的一個實(shí)數(shù)值函數(shù)）。描述的一個實(shí)數(shù)值函數(shù)）。 2) 2)下一個要擴(kuò)展的節(jié)點(diǎn)下一個要擴(kuò)展的節(jié)點(diǎn)n n是是 值最小的節(jié)點(diǎn)值最小的節(jié)點(diǎn)( (假定節(jié)點(diǎn)假定節(jié)點(diǎn)擴(kuò)展產(chǎn)生一個節(jié)點(diǎn)的所有后繼擴(kuò)展產(chǎn)生一個節(jié)點(diǎn)的所有后繼) )。 3) 3)當(dāng)下一個要擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時過程終止。當(dāng)下一個要擴(kuò)展的節(jié)點(diǎn)是

3、目標(biāo)節(jié)點(diǎn)時過程終止。 我們常常可以為最優(yōu)搜索指定好的評估函數(shù)。例如在我們常常可以為最優(yōu)搜索指定好的評估函數(shù)。例如在8 8數(shù)數(shù)碼問題中，可以用不在正確位置的數(shù)字個數(shù)作為狀態(tài)描述好碼問題中，可以用不在正確位置的數(shù)字個數(shù)作為狀態(tài)描述好壞的一個度量：壞的一個度量： 位置不正確的數(shù)字個數(shù)位置不正確的數(shù)字個數(shù)( (和目標(biāo)相比和目標(biāo)相比) )在搜索過程中采用這個啟發(fā)式函數(shù)將產(chǎn)生下圖所示的圖，每在搜索過程中采用這個啟發(fā)式函數(shù)將產(chǎn)生下圖所示的圖，每個節(jié)點(diǎn)的數(shù)值是該節(jié)點(diǎn)的值。個節(jié)點(diǎn)的數(shù)值是該節(jié)點(diǎn)的值。 ff f( (n n) )f f( (n n) )f f 這個例子表明，在搜索過程中我們需要偏向這個例子表明，在

4、搜索過程中我們需要偏向有利于回溯到早期路徑的搜索。因此我們加了一有利于回溯到早期路徑的搜索。因此我們加了一個個“深度因子深度因子”給給 ：其中：其中： 是對圖中節(jié)點(diǎn)是對圖中節(jié)點(diǎn)n n的的“深度深度”估計估計( (即從即從開始節(jié)點(diǎn)到開始節(jié)點(diǎn)到n n的最短路徑長度的最短路徑長度) )， 是對節(jié)點(diǎn)是對節(jié)點(diǎn)n n的的啟發(fā)或評估啟發(fā)或評估。像前面一樣，像前面一樣，如果如果 = =不正確位置的數(shù)字個數(shù)不正確位置的數(shù)字個數(shù)( (和目標(biāo)相比和目標(biāo)相比) )， 搜索圖中節(jié)點(diǎn)搜索圖中節(jié)點(diǎn)n n的深度，的深度， f f( (n n) )h h( (n n) )g g( (n n) )f f( (n n) )g g(

5、 (n n) )h h(n)h ( (n n) )g g可以得到下圖可以得到下圖 ：兩個重要的問題：兩個重要的問題： 第一，我們?nèi)绾螢樽顑?yōu)搜索決定評估函數(shù)？第一，我們?nèi)绾螢樽顑?yōu)搜索決定評估函數(shù)？ 第二，最優(yōu)搜索的特性是什么？它能找到第二，最優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？ 我們把上面兩個問題放到以后討論，這里我們把上面兩個問題放到以后討論，這里主要討論最優(yōu)搜索的形式表示。主要討論最優(yōu)搜索的形式表示。一一個個通通用用的的圖圖搜搜索索算算法法 GRAPHSEARCHGRAPHSEARCH 1) 1)生成一個僅包含開始節(jié)點(diǎn)生成一個僅包含開始節(jié)點(diǎn)N N0 0

6、的搜索樹的搜索樹TrTr。把把N N0 0放在放在一個稱為一個稱為OPENOPEN的有序列表中。的有序列表中。 2) 2)生成一個初始值為空的列表生成一個初始值為空的列表CLOSEDCLOSED。 3) 3)如果如果OPENOPEN為空，則失敗并退出。為空，則失敗并退出。 4) 4)選出選出OPENOPEN中的第一個節(jié)點(diǎn)，并將它從中的第一個節(jié)點(diǎn)，并將它從OPENOPEN中移出，中移出，放入放入CLOSEDCLOSED中，稱該節(jié)點(diǎn)為中，稱該節(jié)點(diǎn)為n n。 5) 5)如果如果n n是目標(biāo)節(jié)點(diǎn)，順著是目標(biāo)節(jié)點(diǎn)，順著TrTr中的弧從中的弧從n n回溯到回溯到n n0 0找到找到一條路徑，獲得解決方案，

7、則成功退出一條路徑，獲得解決方案，則成功退出( (弧在第弧在第6 6步產(chǎn)生步產(chǎn)生) )。 6) 6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，生成生成n n的后繼節(jié)點(diǎn)集的后繼節(jié)點(diǎn)集M M（放入放入OPENOPEN）。）。通過在通過在TrTr中建立從中建立從n n到到M M中每個成員的弧生成中每個成員的弧生成n n的后繼。的后繼。 7) 7)按照任意的模式或啟發(fā)式方式對列表按照任意的模式或啟發(fā)式方式對列表OPENOPEN重新排序。重新排序。 8) 8)返回步驟返回步驟3 3。 這個算法可用來執(zhí)行最優(yōu)搜索、廣度優(yōu)先這個算法可用來執(zhí)行最優(yōu)搜索、廣度優(yōu)先搜索或深度優(yōu)先搜索。搜索或深度優(yōu)先搜索。 在廣度優(yōu)先搜索中，新節(jié)點(diǎn)

8、只要放在在廣度優(yōu)先搜索中，新節(jié)點(diǎn)只要放在OPENOPEN的尾部即可的尾部即可( (先進(jìn)先出，先進(jìn)先出， FIFO)FIFO)，節(jié)點(diǎn)不用重節(jié)點(diǎn)不用重排。排。 在深度優(yōu)先搜索中，新節(jié)點(diǎn)放在在深度優(yōu)先搜索中，新節(jié)點(diǎn)放在OPENOPEN的開的開始始( (后進(jìn)先出，后進(jìn)先出， LIFO)LIFO)。 在最優(yōu)在最優(yōu)( (也叫啟發(fā)式也叫啟發(fā)式) )搜索中，按照節(jié)點(diǎn)的搜索中，按照節(jié)點(diǎn)的啟發(fā)式方式來重排啟發(fā)式方式來重排OPENOPEN。 算法算法A A* * 用最優(yōu)搜索算法詳細(xì)說明用最優(yōu)搜索算法詳細(xì)說明GRAPHSEARCHGRAPHSEARCH。最優(yōu)搜最優(yōu)搜索算法根據(jù)函數(shù)索算法根據(jù)函數(shù) 的增加值，的增加值，(

9、 (在第在第7 7步步) )重排重排OPENOPEN中中的節(jié)點(diǎn)。把的節(jié)點(diǎn)。把GRAPHSEACHGRAPHSEACH的這種算法稱為的這種算法稱為算法算法A A* *。 f 設(shè)設(shè)h(n)h(n)節(jié)點(diǎn)節(jié)點(diǎn)n n和目標(biāo)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)( (遍及所有可能的目標(biāo)遍及所有可能的目標(biāo)節(jié)點(diǎn)以及從節(jié)點(diǎn)以及從n n到它們的所有可能路徑到它們的所有可能路徑) )之間的最小代價之間的最小代價路徑的實(shí)際代價。路徑的實(shí)際代價。 設(shè)設(shè)g(n)g(n)從開始節(jié)點(diǎn)從開始節(jié)點(diǎn)n n0 0到節(jié)點(diǎn)到節(jié)點(diǎn)n n的一個最小代價的一個最小代價路徑的代價。路徑的代價。 那么那么f(n)=g(n)+h(n)f(n)=g(n)+h(n)就是從就是

10、從n n0 0到目標(biāo)節(jié)點(diǎn)并且經(jīng)到目標(biāo)節(jié)點(diǎn)并且經(jīng)過節(jié)點(diǎn)過節(jié)點(diǎn)n n的最小代價路徑的代價。注意的最小代價路徑的代價。注意f(nf(n0 0) )h(nh(n0 0) )是從是從n n0 0到目標(biāo)節(jié)點(diǎn)的一個到目標(biāo)節(jié)點(diǎn)的一個( (不受限的不受限的) )最小代價路徑的最小代價路徑的代價。代價。 對每個節(jié)點(diǎn)對每個節(jié)點(diǎn)n n，設(shè)設(shè) ( (啟發(fā)因子啟發(fā)因子) )是是h(n)h(n)的某個估計，的某個估計， ( (深度因子深度因子) )是由是由A A* *發(fā)現(xiàn)的到節(jié)點(diǎn)發(fā)現(xiàn)的到節(jié)點(diǎn)n n的最小代價路徑的的最小代價路徑的代價。在算法代價。在算法A A* *中，我們用中，我們用 。注意注意，如果算法，如果算法A A*

11、 *中的中的 恒等于恒等于0 0，就成為相同代價搜索。，就成為相同代價搜索。 )(nh )(ng ghf h 如果要搜索的隱式圖不是一棵樹（有超過一個動如果要搜索的隱式圖不是一棵樹（有超過一個動作序列能從開始狀態(tài)到達(dá)相同的環(huán)境狀態(tài)）會怎樣呢作序列能從開始狀態(tài)到達(dá)相同的環(huán)境狀態(tài)）會怎樣呢? ?引深問題：引深問題：把把GRAPHSEARCHGRAPHSEARCH中的第中的第6 6步改為步改為： 6) 6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，生成后繼集合生成后繼集合（放入放入OPENOPEN）。）。 n n的雙親不能在的雙親不能在中。通過在中。通過在TrTr中建立從中建立從n n到到中每中每個成員的弧生成個成員

12、的弧生成n n的后繼。的后繼。 考慮到更長的循環(huán)，把第考慮到更長的循環(huán)，把第6 6步改為步改為: : 6) 6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，生成后繼集合生成后繼集合（放入放入OPENOPEN）。）。 n n的祖先不能在的祖先不能在中。通過在中。通過在TrTr中建立從中建立從n n到到中每中每個成員的弧生成個成員的弧生成n n的后繼。的后繼。 算法算法A A* *： 1)1)生成一個只包含開始節(jié)點(diǎn)生成一個只包含開始節(jié)點(diǎn)n n0 0的搜索圖的搜索圖G G，把把n n0 0放在一個放在一個叫叫OPENOPEN的列表上。的列表上。 2) 2)生成一個列表生成一個列表CLOSEDCLOSED，它的初始值為空

13、。它的初始值為空。 3) 3)如果如果OPENOPEN為空，則失敗退出。為空，則失敗退出。 4) 4)選擇選擇OPENOPEN上的第一個節(jié)點(diǎn)，把它從上的第一個節(jié)點(diǎn)，把它從OPENOPEN中移入中移入CLOSEDCLOSED，稱該節(jié)點(diǎn)為稱該節(jié)點(diǎn)為n n。 5) 5)如果如果n n是目標(biāo)節(jié)點(diǎn)，順著是目標(biāo)節(jié)點(diǎn)，順著G G中，從中，從n n到到n n0 0的指針找到一條的指針找到一條路徑，獲得解決方案，成功退出路徑，獲得解決方案，成功退出( (該指針定義了一個搜索樹，該指針定義了一個搜索樹，在第在第7 7步建立步建立) )。 6) 6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，生成其后繼節(jié)點(diǎn)集生成其后繼節(jié)點(diǎn)集M M，在

14、在G G中，中，n n的祖先不能的祖先不能在在M M中。在中。在G G中安置中安置M M的成員，使它們成為的成員，使它們成為n n的后繼。的后繼。 7) 7)從從M M的每一個不在的每一個不在G G中的成員建立一個指向中的成員建立一個指向n n的指針的指針( (例例如，既不在如，既不在OPENOPEN中，也不在中，也不在CLOSEDCLOSED中中) )。把。把M M的這些成員加到的這些成員加到OPENOPEN中。對中。對M M的每一個已在的每一個已在OPENOPEN中或中或CLOSED CLOSED 中的成員中的成員m m，如如果到目前為止找到的到達(dá)果到目前為止找到的到達(dá)m m的最好路徑通過

15、的最好路徑通過n n，就把它的指針就把它的指針指向指向n n。對已在對已在CLOSEDCLOSED中的中的M M的每一個成員，重定向它在的每一個成員，重定向它在G G中中的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。向它們的祖先。 8) 8)按遞增值，重排按遞增值，重排OPEN(OPEN(相同最小相同最小 值可根據(jù)搜索樹中值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決的最深節(jié)點(diǎn)來解決) )。 9) 9)返回第返回第3 3步。步。 f f 在第在第7 7步中，如果搜索過程發(fā)現(xiàn)一條路徑到步中，如果搜索過程發(fā)現(xiàn)一條路徑到達(dá)一個節(jié)點(diǎn)的代價比現(xiàn)存

16、的路徑代價低，我們就達(dá)一個節(jié)點(diǎn)的代價比現(xiàn)存的路徑代價低，我們就要重定向指向該節(jié)點(diǎn)的指針。要重定向指向該節(jié)點(diǎn)的指針。 已經(jīng)在已經(jīng)在CLOSEDCLOSED中的節(jié)點(diǎn)子孫的重定向保存中的節(jié)點(diǎn)子孫的重定向保存了后面的搜索結(jié)果，但是可能需要指數(shù)級的計算了后面的搜索結(jié)果，但是可能需要指數(shù)級的計算代價。因此，第代價。因此，第7 7步常常不會實(shí)現(xiàn)。隨著搜索的步常常不會實(shí)現(xiàn)。隨著搜索的向前推進(jìn)，其中有些指針最終將會被重定向向前推進(jìn)，其中有些指針最終將會被重定向。 A A* *的可接納性的可接納性 對圖和對圖和 施加一些條件可以保證應(yīng)用到圖的算法施加一些條件可以保證應(yīng)用到圖的算法A A* *總能找到最小代價路徑。

17、總能找到最小代價路徑。 圖的條件是：圖的條件是： 1) 1)圖中每個節(jié)點(diǎn)的后繼是有限的圖中每個節(jié)點(diǎn)的后繼是有限的( (如果有的話如果有的話) )； 2) 2)圖中所有弧的代價都大于某個正數(shù)圖中所有弧的代價都大于某個正數(shù)。 的條件是：的條件是： 3) 3)對搜索圖中的所有節(jié)點(diǎn)對搜索圖中的所有節(jié)點(diǎn)n n， (n)h(n) (n)h(n)。也就也就是說，決不會超過實(shí)際值是說，決不會超過實(shí)際值h h的估計。的估計。( (這樣的這樣的 函數(shù)函數(shù)有時被稱為有時被稱為優(yōu)化概算機(jī)優(yōu)化概算機(jī)) ) h h h h h h h h 定理定理9.19.1 如果圖和如果圖和 具有上述的穩(wěn)定條件，而且從具有上述的穩(wěn)定條

18、件，而且從開始節(jié)點(diǎn)開始節(jié)點(diǎn)n n0 0到目標(biāo)節(jié)點(diǎn)有一條有限代價的路徑，那么算到目標(biāo)節(jié)點(diǎn)有一條有限代價的路徑，那么算法法A A* *保證終止于到達(dá)目標(biāo)的一條最小代價路徑。保證終止于到達(dá)目標(biāo)的一條最小代價路徑。 h h 引理引理9.19.1 在在A A* *終止前的每一步，總是有一個節(jié)點(diǎn)終止前的每一步，總是有一個節(jié)點(diǎn)n n* *，它在它在OPENOPEN上有下面的特性：上有下面的特性： 1) 1)n n* *在到達(dá)目標(biāo)的一條最佳路徑上。在到達(dá)目標(biāo)的一條最佳路徑上。 2) 2)A A* *已經(jīng)發(fā)現(xiàn)了到達(dá)已經(jīng)發(fā)現(xiàn)了到達(dá)n n* *的一條最佳路徑。的一條最佳路徑。 3) 3) ) )f f( (n n)

19、 )( (n nf f0 0* * 任何保證能找到一條到達(dá)目標(biāo)的最佳路徑的算法是任何保證能找到一條到達(dá)目標(biāo)的最佳路徑的算法是可接納的可接納的。 如果如果A A* *的兩個版本的兩個版本A A1 1* *和和A A2 2* *，其差別在于對所有的非其差別在于對所有的非目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)， ，那么我們就說，那么我們就說A A1 1* *比比A A2 2* *更更靈通靈通（informedinformed）。）。 定理定理9.29.2 如果如果A A2 2* *比比A A1 1* *更靈通，那么對任何有從更靈通，那么對任何有從n n0 0到到目標(biāo)節(jié)點(diǎn)的一條路徑的圖，在搜索時，被目標(biāo)節(jié)點(diǎn)的一條路徑的圖

20、，在搜索時，被A A2 2* *擴(kuò)展過的每擴(kuò)展過的每一個節(jié)點(diǎn)也被一個節(jié)點(diǎn)也被A A1 1* *擴(kuò)展過。擴(kuò)展過。 可以得出可以得出A A1 1* *擴(kuò)展的節(jié)點(diǎn)至少和擴(kuò)展的節(jié)點(diǎn)至少和A A2 2* *的一樣多，這的一樣多，這個更靈通的算法個更靈通的算法A A2 2* *也就更有效。因此，我們要尋找盡也就更有效。因此，我們要尋找盡可能接近真實(shí)函數(shù)可能接近真實(shí)函數(shù)h h的函數(shù)的函數(shù) ( (為了搜索效率為了搜索效率) )，同時又，同時又不能超過它們不能超過它們( (為了可接納性為了可接納性) )。 最靈通的算法是最靈通的算法是 h h h h h h2 21 1h hh h 一致性一致性( (或單調(diào)或單

21、調(diào)) )條件條件 考慮一對節(jié)點(diǎn)考慮一對節(jié)點(diǎn)( (n ni i,n,nj j) )，n nj j 是是n ni i的一個后繼。如果在的一個后繼。如果在搜索圖中所有的這種節(jié)點(diǎn)對都滿足下述條件：搜索圖中所有的這種節(jié)點(diǎn)對都滿足下述條件： 其中其中 是從是從 n ni i 到到 n nj j 的代價。的代價。上式也寫作：上式也寫作：和和 那么我們就說那么我們就說h h服從一致性條件服從一致性條件。 ) )n n, ,c(nc(n) )(n(nh h) )(n(nh hj ji ij ji i) )n n, ,c(nc(n) )(n(nh h) )(n(nh hj ji ij ji i),()()(jii

22、jnncnhnh) )n n, ,c c( (n nj ji i 這個條件陳述了順著搜索圖中的任何路徑，到達(dá)目標(biāo)這個條件陳述了順著搜索圖中的任何路徑，到達(dá)目標(biāo)的最優(yōu)的最優(yōu)( (剩余剩余) )代價的估價的減少不會大于該路徑弧代價。代價的估價的減少不會大于該路徑弧代價。 也就是說，在考慮了一個弧的已知代價后，啟發(fā)式函也就是說，在考慮了一個弧的已知代價后，啟發(fā)式函數(shù)在局部是一致的。這種一致性條件可以表示為如圖所示數(shù)在局部是一致的。這種一致性條件可以表示為如圖所示的三角不等式。的三角不等式。 一致性函數(shù)也暗示了當(dāng)搜索樹中結(jié)點(diǎn)的值遠(yuǎn)離開始節(jié)一致性函數(shù)也暗示了當(dāng)搜索樹中結(jié)點(diǎn)的值遠(yuǎn)離開始節(jié)點(diǎn)時，它是點(diǎn)時，它

23、是單調(diào)非遞減單調(diào)非遞減的。因此，一致性條件的。因此，一致性條件( (對對 ) )也常也常被稱為被稱為單調(diào)條件單調(diào)條件( (對對 ) )。 h h f f 定理定理9.39.3 如果如果 上的一致性條件被滿足，那么當(dāng)上的一致性條件被滿足，那么當(dāng)A A* *擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n時，它已經(jīng)找到了到達(dá)節(jié)點(diǎn)時，它已經(jīng)找到了到達(dá)節(jié)點(diǎn)n n的一條最優(yōu)路徑。的一條最優(yōu)路徑。 h h 滿足一致性條件時，可以為滿足一致性條件時，可以為A A* *的可接納性給出一個簡單直觀的論的可接納性給出一個簡單直觀的論證證。它是這樣的：。它是這樣的： 1) 1) 的單調(diào)性暗示了搜索順著的單調(diào)性暗示了搜索順著 值增大的邊緣向外

24、擴(kuò)展。值增大的邊緣向外擴(kuò)展。 2) 2) 因此，被選擇的第一個目標(biāo)節(jié)點(diǎn)就是有最小值的一個目標(biāo)節(jié)因此，被選擇的第一個目標(biāo)節(jié)點(diǎn)就是有最小值的一個目標(biāo)節(jié)點(diǎn)。點(diǎn)。 3) 3) 對任何目標(biāo)節(jié)點(diǎn)對任何目標(biāo)節(jié)點(diǎn)n ng g， ( (這里，我們用了這樣的這里，我們用了這樣的事實(shí)，如果事實(shí)，如果 函數(shù)是一致的，它也將絕不會比真正的函數(shù)是一致的，它也將絕不會比真正的h h函數(shù)大函數(shù)大。 4) 4) 因此，第一個被選擇的目標(biāo)節(jié)點(diǎn)將是有最小因此，第一個被選擇的目標(biāo)節(jié)點(diǎn)將是有最小 值的目標(biāo)節(jié)點(diǎn)。值的目標(biāo)節(jié)點(diǎn)。 5) 5) 作為定理作為定理9.39.3的一個結(jié)論，無論何時的一個結(jié)論，無論何時( (特別地特別地) )當(dāng)一個

25、目標(biāo)節(jié)點(diǎn)當(dāng)一個目標(biāo)節(jié)點(diǎn)n ng g被選擇擴(kuò)展時，我們已找到了到達(dá)那個目標(biāo)節(jié)點(diǎn)的一個最佳路徑。被選擇擴(kuò)展時，我們已找到了到達(dá)那個目標(biāo)節(jié)點(diǎn)的一個最佳路徑。即即 。 6) 6) 這樣，第一個被選擇的目標(biāo)節(jié)點(diǎn)將是算法發(fā)現(xiàn)的最佳路徑的這樣，第一個被選擇的目標(biāo)節(jié)點(diǎn)將是算法發(fā)現(xiàn)的最佳路徑的目標(biāo)節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)。 f f f f) )( (n ng g) )( (n nf fg gg g h h g g) )( (n ng g) )( (n ng gg gg g 迭代加深的迭代加深的A A* * 廣度優(yōu)先搜索的存儲需求會隨著搜索空間中目標(biāo)深廣度優(yōu)先搜索的存儲需求會隨著搜索空間中目標(biāo)深度的增加呈指數(shù)遞增。盡管好的

26、啟發(fā)式搜索減少了分枝度的增加呈指數(shù)遞增。盡管好的啟發(fā)式搜索減少了分枝因子，但啟發(fā)式搜索還是有如上一樣的缺點(diǎn)。因子，但啟發(fā)式搜索還是有如上一樣的缺點(diǎn)。 在第在第8 8章介紹的迭代加深搜索，不但允許我們找到最章介紹的迭代加深搜索，不但允許我們找到最小代價路徑，而且存儲需求隨著深度增加呈線性增長。小代價路徑，而且存儲需求隨著深度增加呈線性增長。迭代加深迭代加深A(yù) A* *(ID(ID* *) )方法能獲得同啟發(fā)式搜索相似的好處。方法能獲得同啟發(fā)式搜索相似的好處。通過使用通過使用IDAIDA* * 的并行實(shí)現(xiàn)能獲得更高的效率的并行實(shí)現(xiàn)能獲得更高的效率。 該方法同普通迭代加深方法工作相似，我們執(zhí)行一系該

27、方法同普通迭代加深方法工作相似，我們執(zhí)行一系列深度優(yōu)先搜索。在第一次搜索中，建立一個列深度優(yōu)先搜索。在第一次搜索中，建立一個“截止代截止代價價”，它等于，它等于 ，n n0 0是開始節(jié)點(diǎn)。是開始節(jié)點(diǎn)。 我們所知道的就是到達(dá)目標(biāo)的最佳路徑代價可能等于我們所知道的就是到達(dá)目標(biāo)的最佳路徑代價可能等于這個截斷值這個截斷值( (如果如果 ，上述語句就是肯定的；因，上述語句就是肯定的；因?yàn)闉?，它不可能較小，它不可能較小) )。 我們在深度優(yōu)先方式下擴(kuò)展節(jié)點(diǎn)，無論何時，只要擴(kuò)我們在深度優(yōu)先方式下擴(kuò)展節(jié)點(diǎn)，無論何時，只要擴(kuò)展節(jié)點(diǎn)的一個后繼的展節(jié)點(diǎn)的一個后繼的 值超過截斷值，就進(jìn)行回溯。如果值超過截斷值，就進(jìn)

28、行回溯。如果該深度優(yōu)先搜索終止在一個目標(biāo)節(jié)點(diǎn)，顯然它已經(jīng)找到了該深度優(yōu)先搜索終止在一個目標(biāo)節(jié)點(diǎn)，顯然它已經(jīng)找到了到達(dá)目標(biāo)的一個最小代價路徑。否則，一個最優(yōu)路徑的代到達(dá)目標(biāo)的一個最小代價路徑。否則，一個最優(yōu)路徑的代價一定比這個截斷值要大。因此，我們增大截斷值，開始價一定比這個截斷值要大。因此，我們增大截斷值，開始另一次深度優(yōu)先搜索。另一次深度優(yōu)先搜索。 ) )( (n nh h) )( (n nh h) )( (n ng g) )( (n nf f0 00 00 00 0 ) )( (n nh h) )h h( (n n0 00 0) )( (n nh h) )h h( (n n0 00 0 f

29、 f遞歸最優(yōu)搜索遞歸最優(yōu)搜索 遞歸最優(yōu)搜索遞歸最優(yōu)搜索( (RBFS)RBFS)方法比方法比IDAIDA* *用到的存儲稍微多用到的存儲稍微多一點(diǎn)，但是比一點(diǎn)，但是比IDAIDA* *產(chǎn)生的節(jié)點(diǎn)少。當(dāng)擴(kuò)展一個節(jié)點(diǎn)產(chǎn)生的節(jié)點(diǎn)少。當(dāng)擴(kuò)展一個節(jié)點(diǎn)n n時，時， RBFSRBFS計算計算n n的后繼的的后繼的 值，并且重新計算搜索樹上值，并且重新計算搜索樹上n n和和n n的祖先的的祖先的 的值。這個重新計算的過程叫做的值。這個重新計算的過程叫做值的回溯值的回溯( (backing up)backing up)。 f f f f 回溯是這樣進(jìn)行的：剛剛擴(kuò)展的節(jié)點(diǎn)的后繼的回溯回溯是這樣進(jìn)行的：剛剛擴(kuò)展的

30、節(jié)點(diǎn)的后繼的回溯值就是該后繼的值就是該后繼的 值。搜索樹上帶有后繼值。搜索樹上帶有后繼m mi i的節(jié)點(diǎn)的節(jié)點(diǎn)m m的的回溯值是回溯值是 f f) )( (m mf fm mi in n( (m m) )f fi im mi i 其中其中 ( (m mi i) )是節(jié)點(diǎn)是節(jié)點(diǎn)m mi i的回溯值。的回溯值。 f f 如果節(jié)點(diǎn)如果節(jié)點(diǎn)n(n(它剛被擴(kuò)展它剛被擴(kuò)展) )的后繼之一在所有的后繼之一在所有的的OPENOPEN點(diǎn)中有最小點(diǎn)中有最小 值，它被依次擴(kuò)展一直進(jìn)值，它被依次擴(kuò)展一直進(jìn)行下去。但是如果行下去。但是如果OPENOPEN中的其他節(jié)點(diǎn)中的其他節(jié)點(diǎn)nn它它不是不是n n的后繼，有最小的的后

31、繼，有最小的 值。在這種情況下，值。在這種情況下，算法回溯到節(jié)點(diǎn)算法回溯到節(jié)點(diǎn)nn和和n n的最低共同祖先節(jié)點(diǎn)的最低共同祖先節(jié)點(diǎn)k k。讓節(jié)點(diǎn)讓節(jié)點(diǎn)k kn n是到節(jié)點(diǎn)是到節(jié)點(diǎn)n n的路徑上節(jié)點(diǎn)的路徑上節(jié)點(diǎn)k k的后繼。的后繼。RBFSRBFS移去以移去以k kn n為根的子樹，于是為根的子樹，于是k kn n變成了其變成了其 值等于值等于它的回溯值的一個它的回溯值的一個OPENOPEN節(jié)點(diǎn)，搜索繼續(xù)在有最節(jié)點(diǎn)，搜索繼續(xù)在有最低低 值的值的OPENOPEN節(jié)點(diǎn)下進(jìn)行。節(jié)點(diǎn)下進(jìn)行。 f f f f f f f f啟發(fā)式函數(shù)和搜索效率啟發(fā)式函數(shù)和搜索效率 在決定在決定A A* *效率時，啟發(fā)式函數(shù)

32、的選擇是全關(guān)重要的。效率時，啟發(fā)式函數(shù)的選擇是全關(guān)重要的。用用 保證了可接納性，但生成了相同代價搜索，因保證了可接納性，但生成了相同代價搜索，因而效率不高。而效率不高。 等于上較低約束的最高可能值，不但等于上較低約束的最高可能值，不但可以擴(kuò)展較少的節(jié)點(diǎn)，還能維持可接納性可以擴(kuò)展較少的節(jié)點(diǎn)，還能維持可接納性。 0 0h h h h 在選擇在選擇 函數(shù)時，我們必須考慮計算函數(shù)時，我們必須考慮計算 本身的計本身的計算量。常常是在精確算量。常常是在精確 函數(shù)和其計算代價之間取函數(shù)和其計算代價之間取折衷折衷值值。 h h h h h h 經(jīng)常，通過使用一些非低約束的函數(shù)經(jīng)常，通過使用一些非低約束的函數(shù)

33、以可接納以可接納性為代價來換取搜索效率。也就是說，一個可能不是最性為代價來換取搜索效率。也就是說，一個可能不是最佳的路徑比最佳路徑更容易找到，一個非較低約束的佳的路徑比最佳路徑更容易找到，一個非較低約束的 函數(shù)可能比一個較低約束的函數(shù)容易計算。在這些情況函數(shù)可能比一個較低約束的函數(shù)容易計算。在這些情況下，效率可能會成倍地增加下，效率可能會成倍地增加因?yàn)楸粩U(kuò)展的節(jié)點(diǎn)會被因?yàn)楸粩U(kuò)展的節(jié)點(diǎn)會被減少減少( (雖然以可接納性為代價雖然以可接納性為代價) )并且計算量也被減少。并且計算量也被減少。 h h h h 另一種可能性是修改評估函數(shù)中另一種可能性是修改評估函數(shù)中 和和 的權(quán)值，的權(quán)值，即用即用 ，

34、w w是一個正數(shù)。非常大的是一個正數(shù)。非常大的w w值會過分強(qiáng)值會過分強(qiáng)調(diào)啟發(fā)式部分，而非常小的調(diào)啟發(fā)式部分，而非常小的w w會突出搜索的廣度優(yōu)先特性。會突出搜索的廣度優(yōu)先特性。 實(shí)驗(yàn)結(jié)果表明如果實(shí)驗(yàn)結(jié)果表明如果w w值與搜索樹上節(jié)點(diǎn)深度成反比，值與搜索樹上節(jié)點(diǎn)深度成反比，常會提高搜索效率。常會提高搜索效率。 在淺深度時，搜索主要依賴啟發(fā)式部分，然而隨著深在淺深度時，搜索主要依賴啟發(fā)式部分，然而隨著深度的增加，為了確保最終會發(fā)現(xiàn)一些到達(dá)目標(biāo)的路徑，搜度的增加，為了確保最終會發(fā)現(xiàn)一些到達(dá)目標(biāo)的路徑，搜索會逐漸以廣度優(yōu)先為主。索會逐漸以廣度優(yōu)先為主。 g g h h h hw wg gf f28316475 搜索效率的一個度量是有效分枝因子搜索效率的一個度量是有效分枝因子B B，它描述了它描述了一個搜索過程朝著