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