【正文】 地方 。 3）對其余子節(jié)點(diǎn)配上指向 N的返回指針放入 OPEN表。 a格局真的比 b格局距離目標(biāo)更遠(yuǎn)嗎？ 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 實(shí)際距離為 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 實(shí)際距離為 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格局中每個(gè)將牌離家（ 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 擴(kuò)展順序 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*算法中的估價(jià)函數(shù)思想。 A B D C A180。 Q23 39。 與或樹的解樹： 由能判別（標(biāo)記）根節(jié)點(diǎn)是可解節(jié)點(diǎn)的全部節(jié)點(diǎn)和邊所組成的子樹。 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( )定義五個(gè)動(dòng)作： 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)劣的標(biāo)準(zhǔn)是看其是否能夠準(zhǔn)確反映出 節(jié)點(diǎn) x到達(dá)目標(biāo)的難易程度（距離）。 ? 瞎子爬山法 將局部擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到瞎子爬山搜索算法。 ?啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，即用一定的函數(shù)表示出來，通過函數(shù)計(jì)算來評價(jià)每種選擇的價(jià)值大小，用以 指導(dǎo)搜索過程 ，這樣的函數(shù)稱為啟發(fā)函數(shù)。 ?一般 不能保證找到最優(yōu)解 。 CLOSED表： 用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)（返回指針）。 初始狀態(tài)： S0 ＝（ 0， 1， 2， 3， 5， 6， 4， 7， 8） 目標(biāo)狀態(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í) ，例 （八數(shù)碼問題） 例 （ 2） （ 2）有關(guān)操作的知識(shí)（規(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é)點(diǎn)和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達(dá) 目標(biāo)狀態(tài) Qg的 路徑 問題，也就是尋找操作序列的問題。 ?盲目搜索 ： 無向?qū)?的 搜索 ，也稱窮舉搜索。 概括地說，知識(shí)是高度組織起來的信息集團(tuán)，是人們在長期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識(shí)表示 (1) ?知識(shí)表示： 就是研究 在計(jì)算機(jī)中 如何用最合適的形式 表示 問題求解過程中所需要的各種知識(shí)，包括構(gòu)成問題求解框架的全部知識(shí)。 ?操作的表示形式可以是一個(gè)機(jī)械性的步驟、過程、規(guī)則或算子。 假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 2023/4/2 人工智能 32 補(bǔ)充例 二階梵塔問題（ 1） 有三個(gè)桿，一號(hào)桿有 A、 B兩個(gè)金盤， A小于 B。 ?廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。 ② 若有，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到 OPEN表中，令 dm=dm+⊿ d。 在很多實(shí)際問題中，已經(jīng)付出的實(shí)際代價(jià)是必須考慮的，如 TSP問題等。 2023/4/2 人工智能 70 啟發(fā)式搜索的 A算法和 A*算法（ 10） ? 對 已存在于 CLOSED表的節(jié)點(diǎn) ，作與（ 2）同樣的處理，并將其移出 CLOSED表，放入 OPEN表中重新擴(kuò)展。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問題。 當(dāng)然，考慮更多的因素一定會(huì)增加代價(jià)計(jì)算量，所以，在實(shí)際當(dāng)中，使用 A*算法進(jìn)行游戲設(shè)計(jì)時(shí)，還需要在獲得戰(zhàn)術(shù)能力和所付出的計(jì)算量之間做出權(quán)衡。 ：證明 AB＝ A′B′ Q12 180。 ? 本原問題對應(yīng)的節(jié)點(diǎn)稱為 終止節(jié)點(diǎn) 。 ? 子節(jié)點(diǎn)為與關(guān)系，則該節(jié)點(diǎn)為 與節(jié)點(diǎn) 。 ：證明 BD＝ B′D ′ 問題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。即一個(gè)問題與一組子問題的 與等價(jià) 。 假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 Closed表中，說明 P的后繼也在 n之前已經(jīng)生成，稱為Ps。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價(jià)函數(shù) f（ x） :為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價(jià)函數(shù) g（ x）相結(jié)合，即初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價(jià)與 節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計(jì)值總和 。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)， 則轉(zhuǎn)步 2； 步 6 N無子節(jié)點(diǎn)，則轉(zhuǎn)步 2； 步 7 擴(kuò)展 N，將其所有子節(jié)點(diǎn) 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é)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。 （ 1） 有關(guān)狀態(tài)的知識(shí)： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號(hào) ， SB表示B所在桿號(hào) 。 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