【正文】 *算法。 A*算法可納性的證明 以下分三步（定理 、定理 、定理 ，即引理）進(jìn)行證明。 證明： 首先證明算法必然會(huì)結(jié)束。因此， A*算法必然會(huì)結(jié)束。 由于至少存在一條有初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為 S0=n0, n1, … , n k=Sg 算法開(kāi)始時(shí)，節(jié)點(diǎn) n0在 Open表中，而且路徑中任一節(jié)點(diǎn) ni離開(kāi) Open表后，其后繼節(jié)點(diǎn) ni+1必然進(jìn)入 Open表，這樣，在 Open表變?yōu)榭罩?，目?biāo)節(jié)點(diǎn)必然出現(xiàn)在 Open表中。 47 引理 對(duì)無(wú)限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則算法 A*算法不終止的話，則從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 f值。 A*算法 1. A*算法的可納性 (2/6) 48 引理 在 A*算法終止前的任何時(shí)刻， Open表中總存在節(jié)點(diǎn) n’ ，它是從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿足 f(n’ )≤ f*(S0)。因此， A*沒(méi)有結(jié)束以前，在 Open表中必存在最佳路徑上的節(jié)點(diǎn)。則有 f(n39。)+h(n39。在最佳路徑上，故有 g(n39。)，從而 f(n39。)+h(n39。)≤h*(n39。)≤g*(n39。)=f*(n39。)≤f*(S0) A*算法 1. A*算法的可納性 (3/6) 49 定理 對(duì)無(wú)限圖，若從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法必然會(huì)結(jié)束。 推論 Open表中任一具有 f(n)f*(S0)的節(jié)點(diǎn) n，最終都被 A*算法選作為擴(kuò)展的節(jié)點(diǎn)。 證明： 證明過(guò)程分以下兩步進(jìn)行： 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上。 再證明 A*算法只能終止在最佳路徑上。在 Open表中，且有 f(n’ )≤f*(S0)f(t) 這時(shí)， A*算法一定會(huì)選擇 n39。因此， A*算法只能終止在最佳路徑上。 證明： 令 n是由 A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此 n不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒(méi)有結(jié)束。)≤f*(S0) 的節(jié)點(diǎn) n39。則有 f(n)≤f*(S0)；否則，選擇 n擴(kuò)展，必有 f(n) ≤f(n39。一般來(lái)說(shuō)，在滿足 h(n) ≤h*(n)的前提下， h(n)的值越大越好。 下面通過(guò)一個(gè)定理來(lái)描述這一特性。 A*算法 2. A*算法的最優(yōu)性 (1/2) 53 A*算法 2. A*算法的最優(yōu)性 (2/2) 證明 ：（用數(shù)學(xué)歸納法 ） (1) 對(duì)深度 d(n)=0的節(jié)點(diǎn)，即 n為初始節(jié)點(diǎn) S0，如 n為目標(biāo)節(jié)點(diǎn)，則 A1*和 A2*都不擴(kuò)展 n；如果 n不是目標(biāo)節(jié)點(diǎn)，則 A1*和 A2*都要擴(kuò)展 n。 (3) 證明 A2 *中 d(n)=k+1的任意節(jié)點(diǎn) n，也要由 A1 *擴(kuò)展。根據(jù)第 (2)條的假設(shè)，知道 A1 *擴(kuò)展了節(jié)點(diǎn) n的父節(jié)點(diǎn)。既然節(jié)點(diǎn) n沒(méi)有被 A1 *擴(kuò)展，則有 f1(n)≥f*(S0) 即 g1(n)+h1(n)≥f*(S0)。 54 在 A*算法中，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn) n時(shí)，都需要檢查其子節(jié)點(diǎn)是否已在Open表或 Closed表中。 如果能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑，就沒(méi)有必要再去作上述檢查 為滿足這一要求，我們需要對(duì)啟發(fā)函數(shù) h(n)增加單調(diào)性限制。 (2) 對(duì)任意節(jié)點(diǎn) ni及其任一子節(jié)點(diǎn) nj，都有 0≤h(ni)h(nj)≤c(ni, nj) 其中 c(ni, nj)是 ni到其子節(jié)點(diǎn) nj的邊代價(jià)，則稱 h(n)滿足單調(diào)限制。 證明： 設(shè) A*正要擴(kuò)展節(jié)點(diǎn) n，而節(jié)點(diǎn)序列 S0=n0, n1, … ,n k=n 是由初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最佳路徑。 證明： 假設(shè)節(jié)點(diǎn) ni+1在節(jié)點(diǎn) ni之后立即擴(kuò)展，由單調(diào)限制條件可知 h(ni)h(ni+1)≤c(ni, ni+1) 即 f(ni)g(ni)f(ni+1)+g(ni+1)≤c(ni, ni+1) 亦即 f(ni)g(ni)f(ni+1)+g(ni)+c(ni, ni+1)≤c(ni, ni+1) 所以 f(ni)f(ni+1)≤0 即 f(ni)≤f(ni+1) 以上兩個(gè)定理都是在 h(n)滿足單調(diào)性限制的前提下才成立的。 在 h(n)滿足單調(diào)性限制下的 A*算法常被稱為改進(jìn)的 A*算法。 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 S0 f=6 g*=1h*=3 f=6 f=6 g*=2 h*=2 f=6 f=4 g*=3 h*=1 f=4 g*=4 h*=0 f=4 f=6 Sg 八數(shù)碼難題 h(n)=P(n)的搜索樹(shù) f(n)=d(n)+P(n) d(n) 深度 P(n)與目標(biāo)距離 顯然滿足 P(n)≤ h*(n) 即 f*=g*+h* f=4 A*算法應(yīng)用舉例 h*=4 f=4 58 例 修道士和野人問(wèn)題。 對(duì) A*算法 ， 首先需要確定估價(jià)函數(shù) 。通過(guò)分析可知 h(n)≤h*(n)，滿足A*算法的限制條件。 A*算法應(yīng)用舉例 59 (3,3,1) h=4 f=4 (3,2,0) (3,1,0) (2,2,0) (3,2,1) (2,1,0) (3,0,0) (2,2,1) (3,1,1) (0,2,0) (1,1,0) (0,3,1) (0,1,0) (0,2,1) (0,0,0) h=5 f=6 h=3 f=5 h=3 f=6 h=3 f=6 h=2 f=6 h=2 f=7 h=1 f=7 h=1 f=8 h=0 f=8 傳教士和野人問(wèn)題的搜索圖 問(wèn)題狀態(tài)： (m,c,b) 估價(jià)函數(shù)： h(n)=m+c2b h=4 f=5 h=4 f=5 h=2 f=6 h=2 f=7 60 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 與 /或樹(shù)的盲目搜索 ?與 /或樹(shù)的啟發(fā)式搜索 ?博弈樹(shù)的啟發(fā)式搜索 61 與 /或樹(shù)的搜索過(guò)程實(shí)際上是一個(gè)不斷尋找解樹(shù)的過(guò)程。 上述搜索過(guò)程將形成一顆與 /或樹(shù)，這種由搜索過(guò)程所形成的與 /或樹(shù)稱為搜索樹(shù)。 其搜索算法如下： (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (3)如果節(jié)點(diǎn) n可擴(kuò)展，則做下列工作： ① 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； 與 /或樹(shù)的廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 63 ② 考察這些子節(jié)點(diǎn)中有否終止節(jié)點(diǎn) 。 如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn) ， 就得到了解樹(shù) ， 搜索成功 ， 退出搜索過(guò)程；如果不能確定 S0為可解節(jié)點(diǎn) ， 則從 Open表中刪去具有可解先輩的節(jié)點(diǎn) 。 (4) 如果節(jié)點(diǎn) n不可擴(kuò)展，則作下列工作： ① 標(biāo)記節(jié)點(diǎn) n為不可解節(jié)點(diǎn)； ② 應(yīng)用不可解標(biāo)記過(guò)程對(duì)節(jié)點(diǎn) n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記 。 ③ 轉(zhuǎn)第 (2)步 。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹(shù)的廣度優(yōu)先搜索 搜索過(guò)程為： (1) 先擴(kuò)展 1號(hào)節(jié)點(diǎn)，生成 2號(hào)節(jié)點(diǎn)和 3號(hào)節(jié)點(diǎn)。 (3) 擴(kuò)展 3號(hào)節(jié)點(diǎn)，生成 t1節(jié)點(diǎn)和 5號(hào)節(jié)點(diǎn)。 (6) 擴(kuò)展 5號(hào)節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。 (7) 搜索成功，得到由 5號(hào)節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹(shù)。調(diào)用不可解標(biāo)記過(guò)程 … 。由于 t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過(guò)程，可標(biāo)記 2號(hào)節(jié)點(diǎn)為可解，但不能標(biāo)記 1號(hào)節(jié)點(diǎn)為可解。在擴(kuò)展節(jié)點(diǎn)時(shí)，與 /或樹(shù)的深度優(yōu)先搜索過(guò)程總是把剛生成的節(jié)點(diǎn)放在Open表的首部。 若有 ， 則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn) ， 并用可解標(biāo)記過(guò)程對(duì)其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記 。 ③ 轉(zhuǎn)第 (2)步。 如果初始解節(jié)點(diǎn) S0也被標(biāo)記為不可解節(jié)點(diǎn) ， 則搜索失敗 ，表明原始問(wèn)題無(wú)解 ， 退出搜索過(guò)程；如果不能確定 S0為不可解節(jié)點(diǎn) ， 則從 Open表中刪去具有不可解先輩的節(jié)點(diǎn) 。 67 對(duì)上例， 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點(diǎn)擴(kuò)展順序?yàn)椋?， 3， 5， 2， 4。 (2)擴(kuò)展 3號(hào)節(jié)點(diǎn)，生成 t1節(jié)點(diǎn)和 5號(hào)節(jié)點(diǎn)。 (6) 搜索成功，得到由 4號(hào)節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹(shù)。 (5) 擴(kuò)展 4號(hào)節(jié)點(diǎn)，生成 t2節(jié)點(diǎn)和 B節(jié)點(diǎn)。 (3)擴(kuò)展 5號(hào)節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。 68 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹(shù)的盲目搜索 與 /或樹(shù)的啟發(fā)式搜索 ?博弈樹(shù)的啟發(fā)式搜索 69 與 /或樹(shù)的啟發(fā)式搜索過(guò)程實(shí)際上是一種利用搜索過(guò)程所得到的啟發(fā)性信息尋找最優(yōu)解樹(shù)的過(guò)程。 最優(yōu)解樹(shù)是指代價(jià)最小的那棵解樹(shù)。 與 /或樹(shù)的啟發(fā)式搜索 70 解樹(shù)的代價(jià)可按如下規(guī)則計(jì)算： (1)若 n為終止節(jié)點(diǎn)，則其代價(jià) b(n)=0； (2)若 n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為 n1, n2, … ,n k，則 n的代價(jià)為： 其中， c(n, ni)是節(jié)點(diǎn) n到其子節(jié)點(diǎn) ni的邊代價(jià)。 若用和代價(jià)法，則其計(jì)算公式為： 若用最大代價(jià)法，則其計(jì)算公式為： (4)若 n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)，則 n不可擴(kuò)展，其代價(jià)定義為h(n)=∝ 。 ? ????? ki iinhnnh1)(),()( 解樹(shù)的代價(jià)與希望樹(shù) 1. 解樹(shù)的代價(jià) ? ?)(),(max)(1 iiki nhnnh ?? ??? ?)(),(min)( 1 iiki nhnn ?? ??71 例 設(shè)下圖是一棵與 /或樹(shù) ， 它包括兩可解樹(shù) ， 左邊的解樹(shù)由 S0、 A、 t C及 t2組成；右邊的解樹(shù)由 S0、 B、 t D及 t4組成 。 請(qǐng)計(jì)算解樹(shù)的代價(jià) 。 與 /或樹(shù)的啟發(fā)式搜索過(guò)程就是不斷地選擇、修正希望樹(shù)的過(guò)程， 在該過(guò)程中，希望樹(shù)是不斷變化的。 解樹(shù)的代價(jià)與希望樹(shù) 2. 希望樹(shù) ? ?1m in ( , ) ( )iiik c n n h n?? ?73 與 /或樹(shù)的啟發(fā)式搜索過(guò)程如下： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，計(jì)算 h(S0)； (2) 計(jì)算希望樹(shù) T； (3) 依次在 Open表中取出 T的端節(jié)點(diǎn)放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)如果節(jié)點(diǎn) n為終止節(jié)點(diǎn)，則做下列工作： ① 標(biāo)記節(jié)點(diǎn) n為可解節(jié)點(diǎn)； ② 在 T上應(yīng)用可解標(biāo)記過(guò)程，對(duì) n的先輩節(jié)點(diǎn)中的所有可解解節(jié)點(diǎn)進(jìn)行標(biāo)記； ③ 如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn)，則