【正文】 能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點集合中選擇下一個被考察的節(jié)點，不斷向縱深方向前進，直到到達葉子節(jié)點或受到深度限制時，才返回到上一級節(jié)點沿另一方向繼續(xù)前進。 ?即使能求出解，它也不一定是最優(yōu)解。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標 N為待擴展節(jié)點， 則轉(zhuǎn)步 2； 步 6 N無子節(jié)點，則轉(zhuǎn)步 2； 步 7 擴展 N，將其所有子節(jié)點 Ni配上指向 N的指針放入OPEN首部 ， 置 d（ Ni ）＝ d（ N）＋ 1，轉(zhuǎn)步 2。 2023/4/2 人工智能 57 狀態(tài)空間圖的啟發(fā)式搜索 (3) 啟發(fā)式搜索算法 啟發(fā)式搜索的 A算法和 A*算法 A*算法在游戲中的應(yīng)用 2023/4/2 人工智能 58 啟發(fā)式搜索算法 （ 1） ?啟發(fā)式搜索 用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再 增加啟發(fā)函數(shù)值 的 計算 與 傳播 過程，并且由 啟發(fā)函數(shù)值 來 確定 節(jié)點的 擴展順序 。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價函數(shù) f（ x） :為了防止在單獨利用啟發(fā)函數(shù)的時候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價函數(shù) g（ x）相結(jié)合，即初始節(jié)點 S0到達節(jié)點 x處已付出的 代價與 節(jié)點 x 到達目標節(jié)點 Sg的 接近程度估計值總和 。 2）若 xi存在于 OPEN或 CLOSED表中，也 刪除 之，但表明此時存在兩條初始節(jié)點 S0到 xi的路徑；如果 新路徑較 短 ，則 修改 xi節(jié)點的 返回指針 （指向 N），并修改 xi及其后裔節(jié)點和 f值；同時若 xi存在 于 CLOSED表中，則將其 移出放入 OPEN表 重新考察 。 Closed表中，說明 P的后繼也在 n之前已經(jīng)生成，稱為Ps。 1 4 2 8 3 7 6 5 3 2 5 5 6 7 1 4 2 8 3 7 6 5 1 4 2 8 3 5 7 6 1 4 2 8 3 7 6 5 1 2 3 8 4 7 6 5 Sg 1 擴展順序 f2(x)值 1 3 4 8 2 7 6 5 4 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 4 5 1 3 4 8 2 7 6 5 1 3 4 8 2 7 6 5 5 1 3 4 8 6 2 7 5 6 6 3 6 1 3 8 2 4 7 6 5 5 1 3 4 8 2 5 7 6 7 9 8 1 4 3 2 7 6 5 7 3 4 1 8 2 7 6 5 1 3 4 7 8 2 6 5 1 3 4 8 6 2 7 5 7 1 3 4 8 6 2 7 5 7 8 8 4 7 8 10 1 3 8 2 4 7 6 5 5 11 1 2 8 4 3 7 6 5 1 4 2 8 6 3 7 5 1 4 2 8 3 7 6 5 7 8 8 1 2 3 8 4 7 6 5 5 12 8 1 3 8 2 4 7 6 5 啟發(fā)式搜索的 A算法和 A*算法（ 15） 8 1 2 6 3 7 5 4 a 1 2 3 8 4 7 6 5 Sg 2 8 1 4 6 3 7 5 b 問題 :是否對于所有的節(jié)點 w(x)都能反映出從 x節(jié)點 變化到目標節(jié)點的難易程度（到目標的距離）？ w(a)=7 w(b)=6,從 w（ x）值看 a格局離目標格局更遠。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。船在右岸，需要一個人將船運往左岸，因此，對于狀態(tài)（ m， c， 0），需要的擺渡數(shù)，相當(dāng)于船在左岸的（ m+1， c， 1）或（ m，c+1， 1），所以需要的最少擺渡數(shù)為： m+c+12+1=m+c ? 綜合條件，需要的最少擺渡數(shù)為 m+c2b。即一個問題與一組子問題的 與等價 。原來問題可以分解為兩個子問題： Q1：證明 Δ ABC ≌ Δ A′B′C′ Q2：證明 Δ BCD ≌ Δ B′C′D′ 原來問題可以 分為兩個子問題解決。 ：證明 BD＝ B′D ′ 問題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。 Q22 39。 ? 子節(jié)點為與關(guān)系，則該節(jié)點為 與節(jié)點 。 與或圖表示（ 10） 四邊形相等問題分解樹： 1Q2Q1 1Q1 2Q1 3Q2 1Q2 2Q2 32023/4/2 人工智能 106 2023/4/2 人工智能 107 與或樹的盲目搜索（ 1） 與或樹搜索與狀態(tài)樹搜索的不同之處在于： （ 1）搜索過程中包含可解性標記過程 。 ? 本原問題對應(yīng)的節(jié)點稱為 終止節(jié)點 。 Q13 39。 ：證明 AB＝ A′B′ Q12 180。 分析：連接 BD， B180。 當(dāng)然，考慮更多的因素一定會增加代價計算量，所以，在實際當(dāng)中，使用 A*算法進行游戲設(shè)計時，還需要在獲得戰(zhàn)術(shù)能力和所付出的計算量之間做出權(quán)衡。 對狀態(tài)（ 1， 1， 1），啟發(fā)函數(shù) 2不滿足 h（ n） ≤h* （ n） 提示：不考慮限制條件的運送次數(shù)一定小于有限制條 件的運送次數(shù)。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問題。 估價函數(shù)定義探討 2023/4/2 人工智能 72 啟發(fā)式搜索的 A算法和 A*算法（ 12） 2023/4/2 人工智能 73 1 4 8 3 2 7 6 5 S0 1 2 3 8 4 7 6 5 Sg 估價函數(shù) f（ x）＝ g（ x）＋ h（ x） 因素 1 格局中將牌是否在家 g(x)用節(jié)點深度 d（ x）來衡量 如何定義？ h（ x）用 x的格局與目標節(jié)點格局相比，不在家的 將牌數(shù)目 w(x)來衡量。 2023/4/2 人工智能 70 啟發(fā)式搜索的 A算法和 A*算法（ 10） ? 對 已存在于 CLOSED表的節(jié)點 ，作與（ 2）同樣的處理，并將其移出 CLOSED表，放入 OPEN表中重新擴展。 2023/4/2 人工智能 65 2023/4/2 人工智能 66 啟發(fā)式搜索的 A算法和 A*算法（ 5） 步 1 把附有 f（ S0 ） 的初始節(jié)點 S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點 N放入 CLOSED表中，并冠以順序編號 n； 步 4 若目標節(jié)點 Sg＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出。 在很多實際問題中，已經(jīng)付出的實際代價是必須考慮的，如 TSP問題等。 2023/4/2 人工智能 55 2023/4/2 人工智能 56 狀態(tài)空間圖的啟發(fā)式搜索 (2) 在實際設(shè)計過程中， 啟發(fā)函數(shù)是用來估計搜索樹節(jié)點x與目標節(jié)點接近程度的一種函數(shù)，通常記為 h（ x） 。 ② 若有，則取出 CLOSED表中待擴展節(jié)點放入到 OPEN表中，令 dm=dm+⊿ d。如下圖所示： S0S g 1圖 213 深度優(yōu)先搜索不具有完備性示意圖 2023/4/2 人工智能 47 （ Acd ） 為克服深度優(yōu)先搜索的不足，可以對其深度進行限制 ?深度界限的選擇很重要 dm 若太小，則達不到解的深度，得不到解；若太大，既浪費了計算機的存儲空間與時間，又降低了搜索效率。 ?廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。CLOSED表中存放的就是一定搜索策略下的搜索樹。 2023/4/2 人工智能 32 補充例 二階梵塔問題（ 1） 有三個桿，一號桿有 A、 B兩個金盤， A小于 B。類似于這樣表示的狀態(tài)圖稱為 隱式狀態(tài)圖 ，或者說 狀態(tài)圖 的 隱式表示 。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 ? 狀態(tài)空間的解為三元組 Qs, a, Qg ? Qs ：某個初始狀態(tài) ? Qg ：某個目標狀態(tài) ? a：把 Qs變換成 Qg的有限的操作序列 ? 狀態(tài)轉(zhuǎn)換圖 S1 S3 S2 … f1 f2 f3 f4 Qs Qg fn 2023/4/2 人工智能 16 2023/4/2 人工智能 17 例 翻轉(zhuǎn)錢幣問題（ 1） 三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。 ?操作的表示形式可以是一個機械性的步驟、過程、規(guī)則或算子。 ?啟發(fā)式搜索 ：利用 “啟發(fā)性信息 ”作為 導(dǎo)航 的搜索過程。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識表示 (1) ?知識表示： 就是研究 在計算機中 如何用最合適的形式 表示 問題求解過程中所需要的各種知識，包括構(gòu)成問題求解框架的全部知識。 知識與問題求解框架 (2) （ 1）從應(yīng)用領(lǐng)域來劃分 ? 常識性知識 ? 領(lǐng)域（專業(yè)）性知識 （ 2）從在問題求解中的作用來劃分 ? 敘述性知識 ? 過程性知識 ? 控制性知識 （ 3）從確定性來劃分 ? 確定性知識 ? 非確定性知識 （ 4）從知識的表現(xiàn)形式來劃分，可分為文字、符號、聲音、圖形、圖像等。 概括地說，知識是高度組織起來的信息集團，是人們在長期的生活和社會實踐中、科學(xué)研究和科學(xué)實驗中積累起來的經(jīng)驗或?qū)陀^世界規(guī)律的認識等。 （ 3） 控制性知識： 描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識。 ?盲目搜索 ： 無向?qū)?的 搜索 ，也稱窮舉搜索。 ?描述一個操作要包含兩個部分 ? 條件 :指明被作用的狀態(tài)要滿足的約束條件 ? 動作 :指明一個操作對狀態(tài)的分量所做的改變。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達 目標狀態(tài) Qg的 路徑 問題，也就是尋找操作序列的問題。 翻動錢幣的操作抽象為改變上述狀態(tài)的算子 ， 即 F＝ {a, b, c} a:把錢幣 q0翻轉(zhuǎn)一次 b:把錢幣 q1翻轉(zhuǎn)一次 c:把錢幣 q2翻轉(zhuǎn)一次 問題的狀態(tài)空間為 {Q5}, {a, b, c}， {Q0 Q7} 2023/4/2 人工智能 18 例 翻轉(zhuǎn)錢幣問題（ 4） 問題的狀態(tài)空間為： 2023/4/2 人工智能 19 構(gòu)造狀態(tài)空間圖： 5 0 7{ } { } { }Q a b c Q Q??， ， ， ， ，cbbcQ1aQs= Q5bQ7= Qg 2aQ3cQ2aQ6baQ4Q0 = Qg 1c( 0 , 0 , 0 ) ( 1 , 0 , 0 )( 0 , 0 , 1 )( 1 , 0 , 1 )( 1 , 1 , 1 ) ( 0 , 1 , 1 )( 1 , 1 , 0 )( 0 , 1 , 0 )aab aba baa bbb