【正文】 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 例 修道士和野人問題。 解：用 m表示左岸的修道士人數(shù) ， c表示左岸的野人數(shù) ， b表示左岸的船數(shù) ， 用三元組 (m, c, b)表示問題的狀態(tài) 。 對 A*算法 ， 首先需要確定估價函數(shù) 。 設(shè) g(n)=d(n)，h(n)=m+c2b， 則有 f(n)=g(n)+h(n)=d(n)+m+c2b 其中， d(n)為節(jié)點的深度。通過分析可知 h(n)≤h*(n)，滿足A*算法的限制條件。 MC問題的搜索過程如下圖所示。 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，并把它作為當(dāng)前節(jié)點； (2) 應(yīng)用分解或等價變換操作對當(dāng)前節(jié)點進行擴展； (3) 為每個子節(jié)點設(shè)置指向父節(jié)點的指針； (4) 選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第 (2)步和第 (3)步，在此期間需要多次調(diào)用可解標記過程或不可解標記過程，直到初始節(jié)點被標記為可解節(jié)點或不可解節(jié)點為止。 上述搜索過程將形成一顆與 /或樹，這種由搜索過程所形成的與 /或樹稱為搜索樹。 與 /或樹的一般搜索 62 與 /或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標識過程或不可解標識過程。 其搜索算法如下： (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é)點為可解節(jié)點 ， 并用可解標記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標記 。 如果初始解節(jié)點 S0能夠被標記為可解節(jié)點 ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (4) 如果節(jié)點 n不可擴展，則作下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 應(yīng)用不可解標記過程對節(jié)點 n的先輩中不可解解的節(jié)點進行標記 。 如果初始解節(jié)點 S0也被標記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步 。 64 例 設(shè)有下圖所示的與 /或樹，節(jié)點按標注順序進行擴展，其中表有 t t t3的節(jié)點是終止節(jié)點， A、 B、 C為不可解的端節(jié)點。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的廣度優(yōu)先搜索 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和 3號節(jié)點。 (2) 擴展 2號節(jié)點，生成 A節(jié)點和4號節(jié)點。 (3) 擴展 3號節(jié)點，生成 t1節(jié)點和 5號節(jié)點。由于 t1為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，不能確定 3號節(jié)點是否可解。 (6) 擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記 1號節(jié)點為可解節(jié)點。 (7) 搜索成功，得到由 5號節(jié)點即 tt t3節(jié)點構(gòu)成的解樹。 (4) 擴展節(jié)點 A，由于 A是端節(jié)點，因此不可擴展。調(diào)用不可解標記過程 … 。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。由于 t2為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記 2號節(jié)點為可解，但不能標記 1號節(jié)點為可解。 65 與 /或樹的深度優(yōu)先搜索和與 /或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于 Open表中節(jié)點的排列順序不同。在擴展節(jié)點時，與 /或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點放在Open表的首部。 與 /或樹的深度優(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é)點 。 若有 ， 則標記這些終止節(jié)點為可解節(jié)點 ， 并用可解標記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標記 。 如果初始解節(jié)點 S0能夠被標記為可解節(jié)點 ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (5)如果節(jié)點 n不可擴展，則作下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 應(yīng)用不可解標記過程對節(jié)點 n的先輩中不可解解的節(jié)點進行標記 。 如果初始解節(jié)點 S0也被標記為不可解節(jié)點 ， 則搜索失敗 ，表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 67 對上例， 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點擴展順序為：1， 3， 5， 2， 4。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和3號節(jié)點。 (2)擴展 3號節(jié)點，生成 t1節(jié)點和 5號節(jié)點。由于 t1為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，不能確定 3號節(jié)點是否可解。 (6) 搜索成功，得到由 4號節(jié)點即 tt t3節(jié)點構(gòu)成的解樹。 (4) 擴展 2號節(jié)點，生成 A節(jié)點和 4號節(jié)點。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。由于 t2為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記 2號節(jié)點為可解，再往上又可標記 1號節(jié)點為可解。 (3)擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記 3號節(jié)點為可解節(jié)點，但不能標記 1號為可解。 68 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 69 與 /或樹的啟發(fā)式搜索過程實際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。 算法的每一步都試圖找到一個最有希望成為最優(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的邊代價。 (3)若 n為與節(jié)點，且子節(jié)點為 n1, n2, … ,n k，則 n的代價可用和代價法或最大代價法。 若用和代價法，則其計算公式為： 若用最大代價法，則其計算公式為： (4)若 n是端節(jié)點，但又不是終止節(jié)點，則 n不可擴展，其代價定義為h(n)=∝ 。 (5)根節(jié)點的代價即為解樹的代價。 ? ????? ki iinhnnh1)(),()( 解樹的代價與希望樹 1. 解樹的代價 ? ?)(),(max)(1 iiki nhnnh ?? ??? ?)(),(min)( 1 iiki nhnn ?? ??71 例 設(shè)下圖是一棵與 /或樹 ， 它包括兩可解樹 ， 左邊的解樹由 S0、 A、 t C及 t2組成；右邊的解樹由 S0、 B、 t D及 t4組成 。 在此與或樹中 ， t t t t4為終止節(jié)點； E、 F是端節(jié)點；邊上的數(shù)字是該邊的代價 。 請計算解樹的代價 。 解：先計算左邊的解樹 按和代價： 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)解樹的那棵樹。 與 /或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程， 在該過程中，希望樹是不斷變化的。 定義 希望解樹 (1) 初始節(jié)點 S0在希望樹 T (2) 如果 n是具有子節(jié)點 n1, n2, … , n k的或節(jié)點，則 n的某個子節(jié)點 ni在希望樹 T中的充分必要條件是 (3) 如果 n是與節(jié)點，則 n的全部子節(jié)點都在希望樹 T中。 解樹的代價與希望樹 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é)點，則 T就