【正文】 定義 希望解樹 (1) 初始節(jié)點 S0在希望樹 T (2) 如果 n是具有子節(jié)點 n1, n2, … , n k的或節(jié)點，則 n的某個子節(jié)點 ni在希望樹 T中的充分必要條件是 (3) 如果 n是與節(jié)點，則 n的全部子節(jié)點都在希望樹 T中。 解：先計算左邊的解樹 按和代價： h(S0)=2+4+6+2=14 按最大代價： h(S0)=(2+6)+2=10 再計算右邊的解樹 按和代價： h(S0)=1+5+3+2=11 按最大代價： h(S0)=(1+5)+2=8 S0 2 A B t1 C t2 D t3 E t4 F 與 /或樹的代價 2 4 6 2 3 1 5 72 希望樹是 指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。 在此與或樹中 ， t t t t4為終止節(jié)點； E、 F是端節(jié)點；邊上的數(shù)字是該邊的代價 。 (5)根節(jié)點的代價即為解樹的代價。 (3)若 n為與節(jié)點，且子節(jié)點為 n1, n2, … ,n k，則 n的代價可用和代價法或最大代價法。 它涉及到解樹的代價與希望樹。 算法的每一步都試圖找到一個最有希望成為最優(yōu)解樹的子樹。由于 t3為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 3號節(jié)點為可解節(jié)點，但不能標(biāo)記 1號為可解。由于 t2為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號節(jié)點為可解，再往上又可標(biāo)記 1號節(jié)點為可解。 (4) 擴展 2號節(jié)點，生成 A節(jié)點和 4號節(jié)點。由于 t1為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定 3號節(jié)點是否可解。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和3號節(jié)點。 ③ 轉(zhuǎn)第 (2)步。 (5)如果節(jié)點 n不可擴展，則作下列工作： ① 標(biāo)記節(jié)點 n為不可解節(jié)點； ② 應(yīng)用不可解標(biāo)記過程對節(jié)點 n的先輩中不可解解的節(jié)點進行標(biāo)記 。 如果初始解節(jié)點 S0能夠被標(biāo)記為可解節(jié)點 ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 與 /或樹的深度優(yōu)先搜索也可以帶有深度限制 dm，其搜索算法如下： (1)把初始節(jié)點 S0放入 Open表中； (2)把 Open表第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (3)如果節(jié)點 n的深度等于 dm，則轉(zhuǎn)第 (5)步的第 ① 點； (4)如果節(jié)點 n可擴展，則做下列工作： ① 擴展節(jié)點 n，將其子節(jié)點放入 Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針； 與 /或樹的廣度優(yōu)先和深度優(yōu)先搜索 2. 深度優(yōu)先搜索 66 ② 考察這些子節(jié)點中是否有終止節(jié)點 。 65 與 /或樹的深度優(yōu)先搜索和與 /或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于 Open表中節(jié)點的排列順序不同。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。 (4) 擴展節(jié)點 A，由于 A是端節(jié)點，因此不可擴展。由于 t3為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 1號節(jié)點為可解節(jié)點。由于 t1為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定 3號節(jié)點是否可解。 (2) 擴展 2號節(jié)點，生成 A節(jié)點和4號節(jié)點。 64 例 設(shè)有下圖所示的與 /或樹，節(jié)點按標(biāo)注順序進行擴展，其中表有 t t t3的節(jié)點是終止節(jié)點， A、 B、 C為不可解的端節(jié)點。 如果初始解節(jié)點 S0也被標(biāo)記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 若有 ， 則標(biāo)記這些終止節(jié)點為可解節(jié)點 ， 并用可解標(biāo)記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標(biāo)記 。 與 /或樹的一般搜索 62 與 /或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標(biāo)識過程或不可解標(biāo)識過程。其一般搜索過程如下： (1) 把原始問題作為初始節(jié)點 S0，并把它作為當(dāng)前節(jié)點； (2) 應(yīng)用分解或等價變換操作對當(dāng)前節(jié)點進行擴展； (3) 為每個子節(jié)點設(shè)置指向父節(jié)點的指針； (4) 選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第 (2)步和第 (3)步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點被標(biāo)記為可解節(jié)點或不可解節(jié)點為止。 MC問題的搜索過程如下圖所示。 設(shè) g(n)=d(n)，h(n)=m+c2b， 則有 f(n)=g(n)+h(n)=d(n)+m+c2b 其中， d(n)為節(jié)點的深度。 解：用 m表示左岸的修道士人數(shù) ， c表示左岸的野人數(shù) ， b表示左岸的船數(shù) ， 用三元組 (m, c, b)表示問題的狀態(tài) 。 A*算法 3. h(n)的單調(diào)限制 (3/3) 57 例 八數(shù)碼難題。如果 h(n)不滿足單調(diào)性限制，則它們不一定成立。其中， ni是這個序列中最后一個位于Closed表中的節(jié)點，則上述節(jié)點序列中的 ni+1節(jié)點必定在 Open表中，則有 g*(ni)+h(ni)≤g*(ni) +c(ni, ni+1) +h(ni+1) 由于節(jié)點 ni和 ni+1都在最佳路徑上，故有 g*( ni+1)=g*(ni)+c(ni, ni+1) 所以 g*(ni)+h(ni)≤g*( ni+1) +h(ni+1) 一直推導(dǎo)下去可得 g*( ni+1)+h(ni+1)≤g*( nk) +h(nk) 由于節(jié)點 ni+1在最佳路徑上，故有 f( ni+1)≤g*( n) +h(n) 因為這時 A*擴展節(jié)點 n而不擴展節(jié)點 ni+1，則有 f(n)=g(n)+h(n)≤f( ni+1)≤g*(n)+h(n) 即 g(n)≤g*(n) 但是 g*(n)是最小代價值，應(yīng)當(dāng)有 g(n)≥g*(n) 所以有 g(n)=g*(n) A*算法 3. h(n)的單調(diào)限制 (2/3) 56 定理 如果 h(n)滿足單調(diào)限制，則 A*算法擴展的節(jié)點序列的 f 值是非遞減的，即 f(ni)≤f(ni+1)。 A*算法 3. h(n)的單調(diào)限制 (1/3) 55 定理 如果 h滿足單調(diào)條件，則當(dāng) A*算法擴展節(jié)點 n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即 g(n)=g*(n)。 定義 如果啟發(fā)函數(shù)滿足以下兩個條件 : (1) h(Sg)=0。 對已在 Open表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針； 對已在 Closed表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。但由于 d=k時， A2 *擴展的節(jié)點 A1 *也一定擴展，故有 g1(n)≤g2(n) 因此有 h1(n)≥f*(S0)g2(n) 另一方面，由于 A2 *擴展了 n，因此有 f2(n)≤f*(0) 即 g2(n)+h2(n)≤f*(S0)，亦即 h2(n)≤f*(S0)g2(n)，所以有 h1(n)≥h2(n) 這與我們最初假設(shè)的 h1(n)h2(n)矛盾，因此反證法的假設(shè)不成立。因此， n必定在A1 *的 Open表中。（用反證法） 假設(shè) A2搜索樹上有一個滿足 d(n)=k+1的節(jié)點 n， A2 *擴展了該節(jié)點，但 A1 *沒有擴展它。 (2) 假設(shè)對 A2 *中 d(n)=k的任意節(jié)點 n結(jié)論成立，即 A1 *也擴展了這些節(jié)點。 定理 設(shè)有兩個 A*算法 A1*和 A2*，它們有 A1*: f1(n)=g1(n)+h1(n) A2*: f2(n)=g2(n)+h2(n) 如果 A2*比 A1*有更多的啟發(fā)性信息，即對所有非目標(biāo)節(jié)點均有 h2(n)h1(n) 則在搜索過程中，被 A2*擴展的節(jié)點也必然被 A1*擴展，即 A1*擴展的節(jié)點不會比 A2*擴展的節(jié)點少，亦即 A2*擴展的節(jié)點集是 A1*擴展的節(jié)點集的子集。 h(n)的值越大，說明它攜帶的啟發(fā)性信息越多， A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。) 所以有 f(n)≤f*(S0) A*算法 1. A*算法的可納性 (6/6) 52 A*算法的搜索效率很大程度上取決于估價函數(shù) h(n)。若 n=n39。由引理 ，在 Open表中有滿足 f(n39。 51 推論 在 A*算法中，對任何被擴展的節(jié)點 n，都有f(n)≤f*(S0)。來擴展，而不可能選擇 Sg，從而也不會去測試目標(biāo)節(jié)點 Sg，這就與假設(shè) A*算法終止在目標(biāo)節(jié)點 t相矛盾。（反證法） 假設(shè) A*算法未能終止在最佳路徑上，而是終止在 某個目標(biāo)節(jié)點 t處，則有 f(t)=g(t)f*(S0) 但由引理 ，在 A*算法結(jié)束前，必有最佳路徑上的一個節(jié)點 n39。 由定理 ，無論是對有限圖還是無限圖， A*算法都能夠找到某個目標(biāo)節(jié)點而結(jié)束。 (證明略 ) 下面給出 A*算法的可納性 A*算法 1. A*算法的可納性 (4/6) 50 A*算法 1. A*算法的可納性 (5/6) 定理 A*算法是可采納的，即若存在從初始節(jié)點 S0到目標(biāo)節(jié)點 Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上。 證明： （反證法）假設(shè) A*不結(jié)束，由引理 Open表中的節(jié)點有任意大的 f值，這與引理 ，因此， A*算法只能成功結(jié)束。) 因為在最佳路徑上的所有節(jié)點的 f*值都應(yīng)相等，因此有 f(n39。)+h*(n39。)，故有 f(n39。) 又由于 A*算法滿足 h(n39。)=g*(n39。)=g*(n39。) 由于 n39。)=g(n39。設(shè)這些節(jié)點中排在最前面的節(jié)點為 n39。 證明： 設(shè)從初始節(jié)點 S0到目標(biāo)節(jié)點 t的一條最佳路徑序列為 S0= n0, n1, … , n k=Sg 算法開始時，節(jié)點 S0在 Open表中，當(dāng)節(jié)點 S0離開 Open表進入 Closed表時，節(jié)點 n1進入 Open表。 證明： 設(shè) d*(n)是 A*生成的從初始節(jié)點 S0到節(jié)點 n的最短路經(jīng)長度，由于搜索圖中每條邊的代價都是一個正數(shù)，令這些正數(shù)中的最小的一個數(shù)是 e，則有 g*(n)≥d*(n) e 因為 g*(n)是最佳路徑的代價，故有 g(n)≥g*(n)≥d*(n) e 又因為 h(n)≥0，故有 f(n)=g(n)+h(n)≥g(n)≥d*(n) e 如果 A*算法不終止的話，從 Open表中選出的節(jié)點必將具有任意大的 d*(n)值，因此，也將具有任意大的 f值。因此，算法一定會成功結(jié)束。 然后證明算法一定會成功結(jié)束。 由于搜索圖為有限圖，如果算法能找到解，則成功結(jié)束；如果算法找不到解，則必然會由于 Open表變空而結(jié)束。 定理 對有限圖，如果從初始節(jié)點 S0到目標(biāo)節(jié)點 Sg有路徑存在，則算法A*一定成功結(jié)束。 46 A*算法 1. A*算法的可納性 (1/6) 可納性的含義： 對任一狀態(tài)空間圖，當(dāng)從初始節(jié)點到目標(biāo)節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。且 f*(n)=g*(n)+h*(n) A*算法 對 A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的 g(n)和h(n)分別提出如下限制： 第一， g(n)是對最小代價 g*(n)的估計，且 g(n)0； 第二， h(n)是最小代價 h*(n)的下界，即對任意節(jié)點 n均有h(n)