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