【正文】 在第 n層節(jié)點(diǎn)還沒有全部搜索完之前，不進(jìn)入第 n+1層節(jié)點(diǎn)的搜索。 2 8 3 3 1 4 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg 30 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 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 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 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 S0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Sg 31 算法描述 (1) 把初始節(jié)點(diǎn) S0放入 Open表中； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4) 考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。按如下公式： g(ni)=g(n)+c(ni) i=1,2,... 計(jì)算各子結(jié)點(diǎn)的代價(jià)，并根據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì) Open表中的全部結(jié)點(diǎn)按由小到大的順序排序。然后轉(zhuǎn)第 (2)步。設(shè)問題的初始狀態(tài) S0和目標(biāo)狀態(tài) Sg如下圖所示，且估價(jià)函數(shù)為 f(n)=d(n)+W(n) 其中： d(n)表示節(jié)點(diǎn) n在搜索樹中的深度 W(n)表示節(jié)點(diǎn) n中“不在位”的數(shù)碼個(gè)數(shù)。 局部擇優(yōu)： 僅從剛生成的子節(jié)點(diǎn)中選擇一個(gè) 估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。 例如 ， 對(duì)節(jié)點(diǎn) S2， 其估價(jià)函數(shù)值的計(jì)算為： f(S2)=d(S2)+W(S2) =1+3=4 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg 44 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 S0 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 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 4 4 5 5 5 6 4 6 4 4 Sg S1 S2 八數(shù)碼難題的全局擇優(yōu)搜索樹 該問題的解為： S0→S 1→S 2→S 3→S g S3 6 45 A*算法 A*算法是對(duì) A算法的 估價(jià)函數(shù) f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法 假設(shè) f*(n)是從初始節(jié)點(diǎn)出發(fā)，約束經(jīng)過節(jié)點(diǎn) n達(dá)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，估價(jià)函數(shù) f(n)是對(duì) f*(n)的估計(jì)值。因此， A*算法必然會(huì)結(jié)束。因此， A*沒有結(jié)束以前，在 Open表中必存在最佳路徑上的節(jié)點(diǎn)。)，從而 f(n39。)=f*(n39。 再證明 A*算法只能終止在最佳路徑上。)≤f*(S0) 的節(jié)點(diǎn) n39。 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。 54 在 A*算法中，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn) n時(shí)，都需要檢查其子節(jié)點(diǎn)是否已在Open表或 Closed表中。 證明： 假設(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)≤h*(n)，滿足A*算法的限制條件。 如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn) ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點(diǎn) ， 則從 Open表中刪去具有可解先輩的節(jié)點(diǎn) 。 (3) 擴(kuò)展 3號(hào)節(jié)點(diǎn)，生成 t1節(jié)點(diǎn)和 5號(hào)節(jié)點(diǎn)。由于 t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號(hào)節(jié)點(diǎn)為可解，但不能標(biāo)記 1號(hào)節(jié)點(diǎn)為可解。 如果初始解節(jié)點(diǎn) S0也被標(biāo)記為不可解節(jié)點(diǎn) ， 則搜索失敗 ，表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點(diǎn) ， 則從 Open表中刪去具有不可解先輩的節(jié)點(diǎn) 。 (5) 擴(kuò)展 4號(hào)節(jié)點(diǎn)，生成 t2節(jié)點(diǎn)和 B節(jié)點(diǎn)。 與 /或樹的啟發(fā)式搜索 70 解樹的代價(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à)。 與 /或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程， 在該過程中，希望樹是不斷變化的。 ? ????? ki iinhnnh1)(),()( 解樹的代價(jià)與希望樹 1. 解樹的代價(jià) ? ?)(),(max)(1 iiki nhnnh ?? ??? ?)(),(min)( 1 iiki nhnn ?? ??71 例 設(shè)下圖是一棵與 /或樹 ， 它包括兩可解樹 ， 左邊的解樹由 S0、 A、 t C及 t2組成；右邊的解樹由 S0、 B、 t D及 t4組成 。 68 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 69 與 /或樹的啟發(fā)式搜索過程實(shí)際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。 (2)擴(kuò)展 3號(hào)節(jié)點(diǎn)，生成 t1節(jié)點(diǎn)和 5號(hào)節(jié)點(diǎn)。 若有 ， 則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn) ， 并用可解標(biāo)記過程對(duì)其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記 。 (7) 搜索成功，得到由 5號(hào)節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹。 ③ 轉(zhuǎn)第 (2)步 。 上述搜索過程將形成一顆與 /或樹，這種由搜索過程所形成的與 /或樹稱為搜索樹。 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)與目標(biāo)距離 顯然滿足 P(n)≤ h*(n) 即 f*=g*+h* f=4 A*算法應(yīng)用舉例 h*=4 f=4 58 例 修道士和野人問題。 (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)限制。根據(jù)第 (2)條的假設(shè)，知道 A1 *擴(kuò)展了節(jié)點(diǎn) n的父節(jié)點(diǎn)。一般來說，在滿足 h(n) ≤h*(n)的前提下， h(n)的值越大越好。因此， A*算法只能終止在最佳路徑上。 推論 Open表中任一具有 f(n)f*(S0)的節(jié)點(diǎn) n，最終都被 A*算法選作為擴(kuò)展的節(jié)點(diǎn)。)≤h*(n39。)+h(n39。 47 引理 對(duì)無限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則算法 A*算法不終止的話，則從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 f值。 A*算法可納性的證明 以下分三步（定理 、定理 、定理 ，即引理）進(jìn)行證明。 設(shè)問題的初始狀態(tài) S0