第9章 啟發(fā)式搜索

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

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

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

4、搜索過(guò)程中我們需要偏向有利于回溯到早期路徑的搜索。因此我們加了一有利于回溯到早期路徑的搜索。因此我們加了一個(gè)個(gè)“深度因子深度因子”給給 ：其中：其中： 是對(duì)圖中節(jié)點(diǎn)是對(duì)圖中節(jié)點(diǎn)n n的的“深度深度”估計(jì)估計(jì)( (即從即從開(kāi)始節(jié)點(diǎn)到開(kāi)始節(jié)點(diǎn)到n n的最短路徑長(zhǎng)度的最短路徑長(zhǎng)度) )， 是對(duì)節(jié)點(diǎn)是對(duì)節(jié)點(diǎn)n n的的啟發(fā)或評(píng)估啟發(fā)或評(píng)估。像前面一樣，像前面一樣，如果如果 = =不正確位置的數(shù)字個(gè)數(shù)不正確位置的數(shù)字個(gè)數(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可以得到下圖可以得到下圖 ：兩個(gè)重要的問(wèn)題：兩個(gè)重要的問(wèn)題： 第一，我們?nèi)绾螢樽顑?yōu)搜索決定評(píng)估函數(shù)？第一，我們?nèi)绾螢樽顑?yōu)搜索決定評(píng)估函數(shù)？ 第二，最優(yōu)搜索的特性是什么？它能找到第二，最優(yōu)搜索的特性是什么？它能找到到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？到達(dá)目標(biāo)節(jié)點(diǎn)的好路徑嗎？ 我們把上面兩個(gè)問(wèn)題放到以后討論，這里我們把上面兩個(gè)問(wèn)題放到以后討論，這里主要討論最優(yōu)搜索的形式表示。主要討論最優(yōu)搜索的形式表示。一一個(gè)個(gè)通通用用的的圖圖搜搜索索算算法法 GRAPHSEARCHGRAPHSEARCH 1) 1)生成一個(gè)僅包含開(kāi)始節(jié)點(diǎn)生成一個(gè)僅包含開(kāi)始節(jié)點(diǎn)N N0 0

6、的搜索樹(shù)的搜索樹(shù)TrTr。把把N N0 0放在放在一個(gè)稱(chēng)為一個(gè)稱(chēng)為OPENOPEN的有序列表中。的有序列表中。 2) 2)生成一個(gè)初始值為空的列表生成一個(gè)初始值為空的列表CLOSEDCLOSED。 3) 3)如果如果OPENOPEN為空，則失敗并退出。為空，則失敗并退出。 4) 4)選出選出OPENOPEN中的第一個(gè)節(jié)點(diǎn)，并將它從中的第一個(gè)節(jié)點(diǎn)，并將它從OPENOPEN中移出，中移出，放入放入CLOSEDCLOSED中，稱(chēng)該節(jié)點(diǎn)為中，稱(chēng)該節(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）。）。通過(guò)在通過(guò)在TrTr中建立從中建立從n n到到M M中每個(gè)成員的弧生成中每個(gè)成員的弧生成n n的后繼。的后繼。 7) 7)按照任意的模式或啟發(fā)式方式對(duì)列表按照任意的模式或啟發(fā)式方式對(duì)列表OPENOPEN重新排序。重新排序。 8) 8)返回步驟返回步驟3 3。 這個(gè)算法可用來(lái)執(zhí)行最優(yōu)搜索、廣度優(yōu)先這個(gè)算法可用來(lái)執(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的開(kāi)的開(kāi)始始( (后進(jìn)先出，后進(jìn)先出， LIFO)LIFO)。 在最優(yōu)在最優(yōu)( (也叫啟發(fā)式也叫啟發(fā)式) )搜索中，按照節(jié)點(diǎn)的搜索中，按照節(jié)點(diǎn)的啟發(fā)式方式來(lái)重排啟發(fā)式方式來(lái)重排OPENOPEN。 算法算法A A* * 用最優(yōu)搜索算法詳細(xì)說(shuō)明用最優(yōu)搜索算法詳細(xì)說(shuō)明GRAPHSEARCHGRAPHSEARCH。最優(yōu)搜最優(yōu)搜索算法根據(jù)函數(shù)索算法根據(jù)函數(shù) 的增加值，的增加值，(

9、 (在第在第7 7步步) )重排重排OPENOPEN中中的節(jié)點(diǎn)。把的節(jié)點(diǎn)。把GRAPHSEACHGRAPHSEACH的這種算法稱(chēng)為的這種算法稱(chēng)為算法算法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到它們的所有可能路徑到它們的所有可能路徑) )之間的最小代價(jià)之間的最小代價(jià)路徑的實(shí)際代價(jià)。路徑的實(shí)際代價(jià)。 設(shè)設(shè)g(n)g(n)從開(kāi)始節(jié)點(diǎn)從開(kāi)始節(jié)點(diǎn)n n0 0到節(jié)點(diǎn)到節(jié)點(diǎn)n n的一個(gè)最小代價(jià)的一個(gè)最小代價(jià)路徑的代價(jià)。路徑的代價(jià)。 那么那么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)過(guò)節(jié)點(diǎn)過(guò)節(jié)點(diǎn)n n的最小代價(jià)路徑的代價(jià)。注意的最小代價(jià)路徑的代價(jià)。注意f(nf(n0 0) )h(nh(n0 0) )是從是從n n0 0到目標(biāo)節(jié)點(diǎn)的一個(gè)到目標(biāo)節(jié)點(diǎn)的一個(gè)( (不受限的不受限的) )最小代價(jià)路徑的最小代價(jià)路徑的代價(jià)。代價(jià)。 對(duì)每個(gè)節(jié)點(diǎn)對(duì)每個(gè)節(jié)點(diǎn)n n，設(shè)設(shè) ( (啟發(fā)因子啟發(fā)因子) )是是h(n)h(n)的某個(gè)估計(jì)，的某個(gè)估計(jì)， ( (深度因子深度因子) )是由是由A A* *發(fā)現(xiàn)的到節(jié)點(diǎn)發(fā)現(xiàn)的到節(jié)點(diǎn)n n的最小代價(jià)路徑的的最小代價(jià)路徑的代價(jià)。在算法代價(jià)。在算法A A* *中，我們用中，我們用 。注意注意，如果算法，如果算法A A*

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

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

13、。它的初始值為空。 3) 3)如果如果OPENOPEN為空，則失敗退出。為空，則失敗退出。 4) 4)選擇選擇OPENOPEN上的第一個(gè)節(jié)點(diǎn)，把它從上的第一個(gè)節(jié)點(diǎn)，把它從OPENOPEN中移入中移入CLOSEDCLOSED，稱(chēng)該節(jié)點(diǎn)為稱(chēng)該節(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的指針找到一條的指針找到一條路徑，獲得解決方案，成功退出路徑，獲得解決方案，成功退出( (該指針定義了一個(gè)搜索樹(shù)，該指針定義了一個(gè)搜索樹(shù)，在第在第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è)不在G G中的成員建立一個(gè)指向中的成員建立一個(gè)指向n n的指針的指針( (例例如，既不在如，既不在OPENOPEN中，也不在中，也不在CLOSEDCLOSED中中) )。把。把M M的這些成員加到的這些成員加到OPENOPEN中。對(duì)中。對(duì)M M的每一個(gè)已在的每一個(gè)已在OPENOPEN中或中或CLOSED CLOSED 中的成員中的成員m m，如如果到目前為止找到的到達(dá)果到目前為止找到的到達(dá)m m的最好路徑通過(guò)

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

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

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

18、件，而且從開(kāi)始節(jié)點(diǎn)開(kāi)始節(jié)點(diǎn)n n0 0到目標(biāo)節(jié)點(diǎn)有一條有限代價(jià)的路徑，那么算到目標(biāo)節(jié)點(diǎn)有一條有限代價(jià)的路徑，那么算法法A A* *保證終止于到達(dá)目標(biāo)的一條最小代價(jià)路徑。保證終止于到達(dá)目標(biāo)的一條最小代價(jià)路徑。 h h 引理引理9.19.1 在在A A* *終止前的每一步，總是有一個(gè)節(jié)點(diǎn)終止前的每一步，總是有一個(gè)節(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* *的兩個(gè)版本的兩個(gè)版本A A1 1* *和和A A2 2* *，其差別在于對(duì)所有的非其差別在于對(duì)所有的非目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)， ，那么我們就說(shuō)，那么我們就說(shuō)A A1 1* *比比A A2 2* *更更靈通靈通（informedinformed）。）。 定理定理9.29.2 如果如果A A2 2* *比比A A1 1* *更靈通，那么對(duì)任何有從更靈通，那么對(duì)任何有從n n0 0到到目標(biāo)節(jié)點(diǎn)的一條路徑的圖，在搜索時(shí)，被目標(biāo)節(jié)點(diǎn)的一條路徑的圖

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

21、調(diào)) )條件條件 考慮一對(duì)節(jié)點(diǎn)考慮一對(duì)節(jié)點(diǎn)( (n ni i,n,nj j) )，n nj j 是是n ni i的一個(gè)后繼。如果在的一個(gè)后繼。如果在搜索圖中所有的這種節(jié)點(diǎn)對(duì)都滿(mǎn)足下述條件：搜索圖中所有的這種節(jié)點(diǎn)對(duì)都滿(mǎn)足下述條件： 其中其中 是從是從 n ni i 到到 n nj j 的代價(jià)。的代價(jià)。上式也寫(xiě)作：上式也寫(xiě)作：和和 那么我們就說(shuō)那么我們就說(shuō)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 這個(gè)條件陳述了順著搜索圖中的任何路徑，到達(dá)目標(biāo)這個(gè)條件陳述了順著搜索圖中的任何路徑，到達(dá)目標(biāo)的最優(yōu)的最優(yōu)( (剩余剩余) )代價(jià)的估價(jià)的減少不會(huì)大于該路徑弧代價(jià)。代價(jià)的估價(jià)的減少不會(huì)大于該路徑弧代價(jià)。 也就是說(shuō)，在考慮了一個(gè)弧的已知代價(jià)后，啟發(fā)式函也就是說(shuō)，在考慮了一個(gè)弧的已知代價(jià)后，啟發(fā)式函數(shù)在局部是一致的。這種一致性條件可以表示為如圖所示數(shù)在局部是一致的。這種一致性條件可以表示為如圖所示的三角不等式。的三角不等式。 一致性函數(shù)也暗示了當(dāng)搜索樹(shù)中結(jié)點(diǎn)的值遠(yuǎn)離開(kāi)始節(jié)一致性函數(shù)也暗示了當(dāng)搜索樹(shù)中結(jié)點(diǎn)的值遠(yuǎn)離開(kāi)始節(jié)點(diǎn)時(shí)，它是點(diǎn)時(shí)，它

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

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

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

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

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

28、行回溯。如果該深度優(yōu)先搜索終止在一個(gè)目標(biāo)節(jié)點(diǎn)，顯然它已經(jīng)找到了該深度優(yōu)先搜索終止在一個(gè)目標(biāo)節(jié)點(diǎn)，顯然它已經(jīng)找到了到達(dá)目標(biāo)的一個(gè)最小代價(jià)路徑。否則，一個(gè)最優(yōu)路徑的代到達(dá)目標(biāo)的一個(gè)最小代價(jià)路徑。否則，一個(gè)最優(yōu)路徑的代價(jià)一定比這個(gè)截?cái)嘀狄蟆Ｒ虼?，我們?cè)龃蠼財(cái)嘀?，開(kāi)始價(jià)一定比這個(gè)截?cái)嘀狄?。因此，我們?cè)龃蠼財(cái)嘀?，開(kāi)始另一次深度優(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* *用到的存儲(chǔ)稍微多用到的存儲(chǔ)稍微多一點(diǎn)，但是比一點(diǎn)，但是比IDAIDA* *產(chǎn)生的節(jié)點(diǎn)少。當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)產(chǎn)生的節(jié)點(diǎn)少。當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)n n時(shí)，時(shí)， RBFSRBFS計(jì)算計(jì)算n n的后繼的的后繼的 值，并且重新計(jì)算搜索樹(shù)上值，并且重新計(jì)算搜索樹(shù)上n n和和n n的祖先的的祖先的 的值。這個(gè)重新計(jì)算的過(guò)程叫做的值。這個(gè)重新計(jì)算的過(guò)程叫做值的回溯值的回溯( (backing up)backing up)。 f f f f 回溯是這樣進(jìn)行的：剛剛擴(kuò)展的節(jié)點(diǎn)的后繼的回溯回溯是這樣進(jìn)行的：剛剛擴(kuò)展的

30、節(jié)點(diǎn)的后繼的回溯值就是該后繼的值就是該后繼的 值。搜索樹(shù)上帶有后繼值。搜索樹(shù)上帶有后繼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為根的子樹(shù)，于是為根的子樹(shù)，于是k kn n變成了其變成了其 值等于值等于它的回溯值的一個(gè)它的回溯值的一個(gè)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* *效率時(shí)，啟發(fā)式函數(shù)

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

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

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