【正文】 5 1 2 8 4 3 7 6 5 16 30 1 2 8 4 3 7 6 5 1 2 8 4 3 7 6 5 17 16 6 1 2 3 8 4 7 6 5 7 2023/4/2 人工智能 82 2023/4/2 人工智能 83 啟發(fā)式搜索的 A算法和 A*算法（ 22） 對(duì) A算法再限制其估價(jià)函數(shù)中的啟發(fā)函數(shù) h(x)滿(mǎn)足： 對(duì)所有的節(jié)點(diǎn) x均有： h（ x） ? h* （ x） 其中 h* （ x）是從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，這就稱(chēng)為 A*算法。 A*算法也稱(chēng)為 最佳圖搜索算法 ，利用 A*算法，如果問(wèn)題存在最優(yōu)解，就保證能找到最優(yōu)解。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問(wèn)題。在河的左岸有五個(gè)修道士、五個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過(guò)河去，但受到以下條件的限制： （ 1）修道士和野人都會(huì)劃船，但船一次 最多 只能 運(yùn)三個(gè)人； （ 2）在任何岸邊及船上 野人數(shù)目 都 不得超過(guò)修道士 ，否則修道士就會(huì)被野人吃掉。 假定野人會(huì)服從任何一種過(guò)河安排，試規(guī)劃出一種確保修道士安全過(guò)河方案。請(qǐng)定義啟發(fā)函數(shù)，并給出相應(yīng)的搜索樹(shù)。 2023/4/2 人工智能 84 啟發(fā)式搜索的 A算法和 A*算法（ 24） 解：先建立問(wèn)題的狀態(tài)空間。問(wèn)題的狀態(tài)可以用一個(gè)三元數(shù)組來(lái)描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 初始狀態(tài) 為：（ 5， 5， 1） 終止?fàn)顟B(tài) 為：（ 0， 0， 0） 合法的操作只有使?fàn)顟B(tài)如下轉(zhuǎn)換： 從平衡狀態(tài)（ m=c）轉(zhuǎn)換為修道士扎堆（ m=0或 m=5） 從平衡狀態(tài)（ m=c）轉(zhuǎn)換為平衡狀態(tài)（ m=c） 從扎堆狀態(tài) （ m=0或 m=5）轉(zhuǎn)換為平衡狀態(tài)（ m=c） 2023/4/2 人工智能 85 啟發(fā)式搜索的 A算法和 A*算法（ 25） 定義啟發(fā)函數(shù)，若滿(mǎn)足 h（ n） ≤h *（ n），即滿(mǎn)足 A*條件的。 啟發(fā)函數(shù) 1： h（ n） =0。 啟發(fā)函數(shù) 2： h（ n） =M+C。 對(duì)狀態(tài)（ 1， 1， 1），啟發(fā)函數(shù) 2不滿(mǎn)足 h（ n） ≤h* （ n） 提示：不考慮限制條件的運(yùn)送次數(shù)一定小于有限制條 件的運(yùn)送次數(shù)。 2023/4/2 人工智能 86 啟發(fā)式搜索的 A算法和 A*算法（ 26） ? 先考慮船在左岸的情況： ? 如果不考慮限制條件，至少需要 [（ m+c3） /2]*2+1 化簡(jiǎn)后為： [（ m+c3） /2]*2+1大于等于 m+n2 ? 再考慮船在右岸的情況： ? 同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)往左岸，因此，對(duì)于狀態(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。 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*算法以外，國(guó)內(nèi)外研究者還在此基礎(chǔ)上逐漸發(fā)展了許多其它智能算法，包括 IDA*算法、 D*算法等，它們的基本原理都借鑒了 A*算法中的估價(jià)函數(shù)思想。目前，游戲業(yè)界的標(biāo)準(zhǔn)是使用 A*算法或 IDA*算法， A*算法一般要快一些，而 IDA*算法則比 A*算法要使用更少的內(nèi)存。 A*算法在游戲中的應(yīng)用（ 2） ? 如果游戲僅僅要求出從點(diǎn) A到達(dá)點(diǎn) B的一條最短路徑的話，那么使用 A*算法，將 h(x)設(shè)計(jì)為對(duì)A點(diǎn)到 B點(diǎn)的最短路徑的估計(jì)就可以完成此任務(wù)；然而，真實(shí)游戲中往往還要考慮路上的障礙物、或者在從點(diǎn) A到點(diǎn) B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。 ? 在游戲設(shè)計(jì)中，使用 A*算法尋找路徑時(shí)，啟發(fā)函數(shù) h(x)的設(shè)計(jì)還需要考慮更多的因素，如路徑的距離、途中的障礙物、地形允許的行走速度、是否敵人視線與火力之下的位置、敵我雙方暴露的時(shí)間和次數(shù)、敵方的威脅是否動(dòng)態(tài)的、有掩護(hù)物和隱身處的路徑等因素。 A*算法在游戲中的應(yīng)用（ 3） 比如： ? 對(duì)那些暴露在敵方火力偵查或是覆蓋之下的位置增加其代價(jià)值，使得 A*算法生成一條盡量避免敵人偵查或射擊的路徑； ? 如果敵方的飛機(jī)處于被我方地對(duì)空導(dǎo)彈防御的區(qū)域，那么，同樣暴露 20秒，是一次暴露 20秒，還是分四次暴露，一次暴露 5秒，顯然對(duì)我方來(lái)說(shuō)代價(jià)是不一樣的； ? 另外，敵方的威脅是靜態(tài)的或動(dòng)態(tài)的，估價(jià)函數(shù)值計(jì)算出來(lái)也應(yīng)該不同。 當(dāng)然，考慮更多的因素一定會(huì)增加代價(jià)計(jì)算量，所以，在實(shí)際當(dāng)中，使用 A*算法進(jìn)行游戲設(shè)計(jì)時(shí)，還需要在獲得戰(zhàn)術(shù)能力和所付出的計(jì)算量之間做出權(quán)衡。 2023/4/2 人工智能 93 與或圖表示及搜索技術(shù) 與或圖表示 與或樹(shù)的盲目搜索 與或樹(shù)的啟發(fā)式搜索 與或圖表示（ 1） ? 與或圖的概念來(lái)源于問(wèn)題求解中的分解和變換 ? 一個(gè)復(fù)雜的問(wèn)題 P常?？梢苑纸鉃榕c之等價(jià)的一組子問(wèn)題 P1， P2 ， ? Pn， 當(dāng)這些問(wèn)題全部可解時(shí)，問(wèn)題可解；任何一個(gè)子問(wèn)題無(wú)解時(shí)，都將導(dǎo)致原問(wèn)題 P無(wú)解。即一個(gè)問(wèn)題與一組子問(wèn)題的 與等價(jià) 。 ? 一個(gè)復(fù)雜的問(wèn)題 P常?？梢苑謩e變換為與之等價(jià)的一組子問(wèn)題 P1， P2 ， ? Pn， 其中任何一個(gè)子問(wèn)題可解時(shí)，問(wèn)題可解；全部子問(wèn)題無(wú)解時(shí)，原問(wèn)題 P無(wú)解。即一個(gè)問(wèn)題與一組子問(wèn)題的 或等價(jià) 。 與或圖表示（ 2） 例 猴子摘香蕉問(wèn)題 房間內(nèi)有一只猴子位于 A處，有一只箱子位于 B處，還有一架梯子位于 C處， A到 B的距離與 A到 C是距離相同，梯子和箱子的重量相同。屋頂上 D處掛著一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。 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() ：表示摘到香蕉； 則猴子摘香蕉問(wèn)題的分解變換過(guò)程可用如下與或圖表示： 2023/4/2 人工智能 98 與或圖表示（ 4） 例 。 分析：連接 BD， B180。D180。，原來(lái)問(wèn)題可以分解為兩個(gè)子問(wèn)題： Q1：證明 Δ ABC ≌ Δ A′B′C′ Q2：證明 Δ BCD ≌ Δ B′C′D′ 原來(lái)問(wèn)題可以 分為兩個(gè)子問(wèn)題解決。 A B D C A180。 B180。 D180。 C180。 與或圖表示（ 5） 問(wèn)題 Q1還可以再被分解為： Q11 ：證明 AB＝ A′B′ Q12 ：證明 AD＝ A′D ′ Q13 ：證明 ∠ A＝ ∠ A′ 或 Q11 180。 ：證明 AB＝ A′B′ Q12 180。 ：證明 AD＝ A′D ′ Q13 180。 ：證明 BD＝ B′D ′ 問(wèn)題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。 ：證明 BC＝ B ′C′ Q22 180。 ：證明 CD＝ C ′D′ Q23 180。 ：證明 BD＝ B′D′ 180。 2023/4/2 人工智能 100 與或圖表示（ 5） 將原問(wèn)題用圖的形式表示如下： Q Q1 Q2 Q11 Q12 Q13 Q11 39。 Q12 39。 Q13 39。 Q21 Q22 Q23 Q21 39。 Q22 39。 Q23 39。 弧線表示所連邊為“與”的關(guān)系 不帶弧線的邊為或關(guān)系 與或圖表示（ 6） 例 梵塔問(wèn)題。 有 3號(hào)桿， 1號(hào)桿自上而下串著從小到大的 n個(gè)金盤(pán)，要把 1號(hào)桿上的 n個(gè)金盤(pán)移到 3號(hào)桿上。移動(dòng)金盤(pán)的規(guī)則是： 一次 只 能 移一個(gè) 金盤(pán)； 移動(dòng)的過(guò)程中 不允許大盤(pán)壓 在 小盤(pán) 上。 2023/4/2 人工智能 101 3 1 2 3 1 2 與或圖表示（ 6） (1,1,1)=(3,3,3) (1,1,1)=(1,1,3) (1,2,3)=(1,2,2) (3,2,2)=(3,2,1) (3,3,1)=(3,3,3) (1,1,3)=(1,2,3) (3,2,1)=(3,3,1) (1,1,1)=(1,2,2) (1,2,2)=(3,2,2) (3,2,2)=(3,3,3) 三階梵塔問(wèn)題的與或樹(shù) 2023/4/2 人工智能 103 與或圖表示（ 7） 與或圖的幾個(gè)概念： ? 直接可解的問(wèn)題稱(chēng)為 本原問(wèn)題 。 ? 本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)稱(chēng)為 終止節(jié)點(diǎn) 。 ? 無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為 端節(jié)點(diǎn) 。 ? 子節(jié)點(diǎn)為與關(guān)系，則該節(jié)點(diǎn)為 與節(jié)點(diǎn) 。 ? 子節(jié)點(diǎn)為或關(guān)系，則該節(jié)點(diǎn)為 或節(jié)點(diǎn) 。 與或圖一般表示問(wèn)題的變換過(guò)程，就是從原問(wèn)題出發(fā)，運(yùn)用某些規(guī)則不斷的進(jìn)行問(wèn)題的 分解 （得到 與分支 ）和變換 （得到 或分支 ），而得到一個(gè)與或圖，與或圖的節(jié)點(diǎn)一般代表問(wèn)題，整個(gè)圖就表示問(wèn)題空間。 2023/4/2 人工智能 104 與或圖表示（ 8） 與或圖也可以用三元組表示： （ Q0 , F , Qn） Q0表示初始問(wèn)題 F表示問(wèn)題變換規(guī)則集 Qn表示 本原問(wèn)題集 與或圖表示（ 9） 節(jié)點(diǎn)的可解性判別： （ 1）終止節(jié)點(diǎn)是可解節(jié)點(diǎn)； （ 2）一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)可解； （ 3）一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)可解。 （ 4）非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)； （ 5）一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)至少有一個(gè)不可解； （ 6）一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)不可解。 與或樹(shù)的解樹(shù)： 由能判別（標(biāo)記）根節(jié)點(diǎn)是可解節(jié)點(diǎn)的全部節(jié)點(diǎn)和邊所組成的子樹(shù)。 與或圖表示（ 10） 四邊形相等問(wèn)題分解樹(shù)： 1Q2Q1 1Q1 2Q1 3Q2 1Q2 2Q2 32023/4/2 人工智能 106 2023/4/2 人工智能 107 與或樹(shù)的盲目搜索（ 1） 與或樹(shù)搜索與狀態(tài)樹(shù)搜索的不同之處在于： （ 1）搜索過(guò)程中包含可解性標(biāo)記過(guò)程 。