【正文】 地方 。 3）對其余子節(jié)點配上指向 N的返回指針放入 OPEN表。 a格局真的比 b格局距離目標更遠嗎？ 8 1 2 6 3 7 5 4 1 2 3 8 4 7 6 5 Sg a 8 1 2 6 3 7 5 4 1 2 8 6 3 7 5 4 1 2 8 6 3 7 5 4 1 2 8 6 3 7 5 4 1 2 3 8 6 7 5 4 1 2 3 8 6 4 7 5 1 2 3 8 6 4 7 5 1 2 3 8 4 7 6 5 Sg w(a)=7 實際距離為 8 1 2 3 4 5 6 7 8 2023/4/2 人工智能 77 2 8 1 4 3 7 6 5 2 8 1 4 3 7 6 5 8 1 2 4 3 7 6 5 8 1 2 4 3 7 6 5 8 1 2 4 3 7 6 5 2 8 1 4 6 3 7 5 8 1 3 2 4 7 6 5 8 1 3 2 4 7 6 5 1 3 8 2 4 7 6 5 1 3 8 2 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 Sg 8 1 3 2 4 7 6 5 w(b)=6 實際距離為 11 1 2 3 4 5 6 7 8 9 10 11 2023/4/2 人工智能 78 啟發(fā)式搜索的 A算法和 A*算法（ 18） 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 考慮因素 2，定義 h(x)=p(x) p(x)是 x格局中每個將牌離家（ Sg中的位置）的最短 距離（不論路上是否放有其他將牌）的 總和 。 2023/4/2 人工智能 87 （ 5， 5， 1） 1 h=8 f=8 （ 5,3,0） 11 h=8 f=9 （ 5,4,0） 20 h=9 f=10 （ 5,2,0） 2 h=7 f=8 （ 4,4,0） 12 h=8 f=9 （ 5,4,2） 10 h=7 f=9 （ 5,3,1） 3 h=6 f=8 （ 3,3,0） 8 h=6 f=9 （ 5,1,0） 9 h=6 f=9 （ 5,0,0） 4 h=5 f=8 （ 4,4,1） 19 h=6 f=10 （ 5,2,1） 6 h=5 f=9 （ 5,1,1） 5 h=4 f=8 （ 2， 2， 0） 7 h=4 f=9 （ 3， 3， 1） 13 h=4 f=10 （ 0， 3， 0） 14 h=3 f=10 擴展順序 h(x)及 f(x)值 2023/4/2 人工智能 88 （ 0， 3， 0） 14 h=3 f=10 （ 0,4,1） 15 h=2 f=10 （ 0,5,1） h=3 f=11 （ 1,1,1） 17 h=0 f=10 （ 0,2,1） 18 h=0 f=10 （ 0,3,1） h=1 f=11 （ 0， 0， 0） 21 h=0 f=11 （ 0,1,0） 16 h=1 f=10 （ 0,2,0） h=2 f=11 2023/4/2 人工智能 89 2023/4/2 人工智能 90 A*算法在游戲中的應(yīng)用（ 1） 啟發(fā)式算法逐漸發(fā)展成為路徑搜索算法的核心，除了A*算法以外，國內(nèi)外研究者還在此基礎(chǔ)上逐漸發(fā)展了許多其它智能算法，包括 IDA*算法、 D*算法等，它們的基本原理都借鑒了 A*算法中的估價函數(shù)思想。 A B D C A180。 Q23 39。 與或樹的解樹： 由能判別（標記）根節(jié)點是可解節(jié)點的全部節(jié)點和邊所組成的子樹。 Q12 39。 2023/4/2 人工智能 96 ABCD 與或圖表示（ 3） 2023/4/2 人工智能 97 Q1f1( A , B )Q2Qf2( B , D )f4( )f6( )f1( A , C )f2( C , D )f5( )f6( )定義五個動作： f1(x,y)： 表示猴子從 x處走到 y處； f2(x,y) ： 表示猴子推箱子從 x處走到 y處； f3(x,y) ： 表示猴子搬梯子從 x處走到 y處； f4() ：表示登上箱子； f5() ： 表示登上梯子； f6() ：表示摘到香蕉； 則猴子摘香蕉問題的分解變換過程可用如下與或圖表示： 2023/4/2 人工智能 98 與或圖表示（ 4） 例 。 啟發(fā)函數(shù) 2： h（ n） =M+C。 衡量 h（ x）優(yōu)劣的標準是看其是否能夠準確反映出 節(jié)點 x到達目標的難易程度（距離）。 ? 瞎子爬山法 將局部擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到瞎子爬山搜索算法。 ?啟發(fā)函數(shù) 要實現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識形式化，即用一定的函數(shù)表示出來，通過函數(shù)計算來評價每種選擇的價值大小，用以 指導搜索過程 ，這樣的函數(shù)稱為啟發(fā)函數(shù)。 ?一般 不能保證找到最優(yōu)解 。 CLOSED表： 用來記錄考察過的節(jié)點以及節(jié)點之間的關(guān)系，如每個節(jié)點指向父節(jié)點的編號（返回指針）。 初始狀態(tài)： S0 ＝（ 0， 1， 2， 3， 5， 6， 4， 7， 8） 目標狀態(tài)： Sg ＝（ 0， 1， 2， 3， 4， 5， 6， 7， 8） ( a ) 初 始 狀 態(tài)( b ) 終 止 狀 態(tài) 1 2 3 8 5 7 4 6 1 2 3 8 4 7 6 5 X1 X2 X3 X8 X0 X4 X7 X6 X5 重排九宮問題的狀態(tài)表示 80 ??iiji j X X??時 ，例 （八數(shù)碼問題） 例 （ 2） （ 2）有關(guān)操作的知識（規(guī)則）： 0組規(guī)則 R1(X0=0 ) ? (X2=n ) ? X0 = n ? X2 =0； R2(X0=0 ) ? (X4=n ) ? X0 = n ? X4 =0； R3(X0=0 ) ? (X6=n ) ? X0 = n ? X6 =0； R4(X0=0 ) ? (X8=n ) ? X0 = n ? X8 =0； 1組規(guī)則 R5(X1=0 ) ? (X2=n ) ? X1 = n ? X2 =0； R6(X1=0 ) ? (X8=n ) ? X1 = n ? X8 =0； 8組規(guī)則 : R22(X8=0 ) ? (X1=n ) ? X8 = n ? X1 =0； R23(X8=0 ) ? (X0=n ) ? X8 = n ? X0=0； R24(X8=0 ) ? (X7=n ) ? X8 = n ? X7 =0； …… 例 （ 3） 八數(shù)碼的狀態(tài)圖可表示為 （ {S0}, {r1 , r2 ,? , r 24 }, {Sg}） 八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點和目標節(jié)點，其余節(jié)點需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達 目標狀態(tài) Qg的 路徑 問題，也就是尋找操作序列的問題。 ?盲目搜索 ： 無向?qū)?的 搜索 ，也稱窮舉搜索。 概括地說，知識是高度組織起來的信息集團，是人們在長期的生活和社會實踐中、科學研究和科學實驗中積累起來的經(jīng)驗或?qū)陀^世界規(guī)律的認識等。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識表示 (1) ?知識表示： 就是研究 在計算機中 如何用最合適的形式 表示 問題求解過程中所需要的各種知識，包括構(gòu)成問題求解框架的全部知識。 ?操作的表示形式可以是一個機械性的步驟、過程、規(guī)則或算子。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 2023/4/2 人工智能 32 補充例 二階梵塔問題（ 1） 有三個桿，一號桿有 A、 B兩個金盤， A小于 B。 ?廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。 ② 若有，則取出 CLOSED表中待擴展節(jié)點放入到 OPEN表中，令 dm=dm+⊿ d。 在很多實際問題中，已經(jīng)付出的實際代價是必須考慮的，如 TSP問題等。 2023/4/2 人工智能 70 啟發(fā)式搜索的 A算法和 A*算法（ 10） ? 對 已存在于 CLOSED表的節(jié)點 ，作與（ 2）同樣的處理，并將其移出 CLOSED表，放入 OPEN表中重新擴展。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問題。 當然，考慮更多的因素一定會增加代價計算量，所以，在實際當中，使用 A*算法進行游戲設(shè)計時，還需要在獲得戰(zhàn)術(shù)能力和所付出的計算量之間做出權(quán)衡。 ：證明 AB＝ A′B′ Q12 180。 ? 本原問題對應(yīng)的節(jié)點稱為 終止節(jié)點 。 ? 子節(jié)點為與關(guān)系，則該節(jié)點為 與節(jié)點 。 ：證明 BD＝ B′D ′ 問題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。即一個問題與一組子問題的 與等價 。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 Closed表中，說明 P的后繼也在 n之前已經(jīng)生成，稱為Ps。 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的 接近程度估計值總和 。 步 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 人工智能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點集合中選擇下一個被考察的節(jié)點，不斷向縱深方向前進，直到到達葉子節(jié)點或受到深度限制時，才返回到上一級節(jié)點沿另一方向繼續(xù)前進。 （ 1） 有關(guān)狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。 2023/4/2 人工智能 25 例 （ 6） S0 (3,3,1) S18 (3,1,0) p02 q02 S17 (3,2,0) p01 q01 S21 (2,2,0) p11 q11 S1 (3,2,1) q01 p01 p10 q10 S19 (3,0,0) q02 p02 S2 (3,1,1) q01 p01 S26 (1,1,0) q20 p20 S31 (0,0,0) q11 p11 S14 (0,1,1) p01 q01 p02 q02