【正文】 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 啟發(fā)式搜索的 A算法和 A*算法（ 6） 步 6 否則，擴(kuò)展 N，生成一組子節(jié)點 xi，計算 f（ xi ） ，并對這組節(jié)點 xi作如下處理： 1）若 xi是 N的 先輩節(jié)點 ，則 刪除 之。 3）對其余子節(jié)點配上指向 N的返回指針放入 OPEN表。 2023/4/2 人工智能 67 2023/4/2 人工智能 68 啟發(fā)式搜索的 A算法和 A*算法（ 7） 對 步 6的 1）的說明： ABCDS0（ a ）（ b ）S0BACD 啟發(fā)式搜索的 A算法和 A*算法（ 8） 對步 6的 2）的說明： （ b ）S0BACABCDS0（ a ）ABCDS0（ c ）D2023/4/2 人工智能 69 啟發(fā)式搜索的 A算法和 A*算法（ 9） ? 樹式搜索例 ? 對于 已存在于 OPEN表中的節(jié)點 （如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點在 OPEN表中的原返回指針，使其沿原路徑返回。 否則，原路徑好。 S0 過去生成 P的路徑 現(xiàn)在生成 P的路徑 過去對 Ps的 最優(yōu)路徑 Ps P m n k n之前已是某一節(jié)點 m的后繼，所以需要做如同（ 2）同樣的處理，如圖右部所示。對 Ps而言同樣可能 由于n→P 這一路徑的加入，又必須比較多條路徑之后而取代價小的一條，如圖左部所示。 g（ x）：對某一確定的節(jié)點，是確定的值。 衡量 h（ x）優(yōu)劣的標(biāo)準(zhǔn)是看其是否能夠準(zhǔn)確反映出 節(jié)點 x到達(dá)目標(biāo)的難易程度（距離）。 例 A算法在重排九宮問題中的應(yīng)用。 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 實際距離為 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中的位置）的最短 距離（不論路上是否放有其他將牌）的 總和 。 在正中方格上有將牌得 1分，否則得 0分。 A*算法也稱為 最佳圖搜索算法 ，利用 A*算法，如果問題存在最優(yōu)解，就保證能找到最優(yōu)解。在河的左岸有五個修道士、五個野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條件的限制： （ 1）修道士和野人都會劃船，但船一次 最多 只能 運(yùn)三個人； （ 2）在任何岸邊及船上 野人數(shù)目 都 不得超過修道士 ，否則修道士就會被野人吃掉。請定義啟發(fā)函數(shù)，并給出相應(yīng)的搜索樹。問題的狀態(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ù) 2： h（ n） =M+C。 2023/4/2 人工智能 86 啟發(fā)式搜索的 A算法和 A*算法（ 26） ? 先考慮船在左岸的情況： ? 如果不考慮限制條件，至少需要 [（ m+c3） /2]*2+1 化簡后為： [（ m+c3） /2]*2+1大于等于 m+n2 ? 再考慮船在右岸的情況： ? 同樣不考慮限制條件。 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ù)思想。 A*算法在游戲中的應(yīng)用（ 2） ? 如果游戲僅僅要求出從點 A到達(dá)點 B的一條最短路徑的話，那么使用 A*算法，將 h(x)設(shè)計為對A點到 B點的最短路徑的估計就可以完成此任務(wù)；然而，真實游戲中往往還要考慮路上的障礙物、或者在從點 A到點 B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。 A*算法在游戲中的應(yīng)用（ 3） 比如： ? 對那些暴露在敵方火力偵查或是覆蓋之下的位置增加其代價值，使得 A*算法生成一條盡量避免敵人偵查或射擊的路徑； ? 如果敵方的飛機(jī)處于被我方地對空導(dǎo)彈防御的區(qū)域，那么，同樣暴露 20秒，是一次暴露 20秒，還是分四次暴露，一次暴露 5秒，顯然對我方來說代價是不一樣的； ? 另外，敵方的威脅是靜態(tài)的或動態(tài)的，估價函數(shù)值計算出來也應(yīng)該不同。 2023/4/2 人工智能 93 與或圖表示及搜索技術(shù) 與或圖表示 與或樹的盲目搜索 與或樹的啟發(fā)式搜索 與或圖表示（ 1） ? 與或圖的概念來源于問題求解中的分解和變換 ? 一個復(fù)雜的問題 P常常可以分解為與之等價的一組子問題 P1， P2 ， ? Pn， 當(dāng)這些問題全部可解時，問題可解；任何一個子問題無解時，都將導(dǎo)致原問題 P無解。 ? 一個復(fù)雜的問題 P常常可以分別變換為與之等價的一組子問題 P1， P2 ， ? Pn， 其中任何一個子問題可解時，問題可解；全部子問題無解時，原問題 P無解。 與或圖表示（ 2） 例 猴子摘香蕉問題 房間內(nèi)有一只猴子位于 A處，有一只箱子位于 B處，還有一架梯子位于 C處， A到 B的距離與 A到 C是距離相同，梯子和箱子的重量相同。 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） 例 。D180。 A B D C A180。 D180。 與或圖表示（ 5） 問題 Q1還可以再被分解為： Q11 ：證明 AB＝ A′B′ Q12 ：證明 AD＝ A′D ′ Q13 ：證明 ∠ A＝ ∠ A′ 或 Q11 180。 ：證明 AD＝ A′D ′ Q13 180。 ：證明 BC＝ B ′C′ Q22 180。 ：證明 BD＝ B′D′ 180。 Q12 39。 Q21 Q22 Q23 Q21 39。 Q23 39。 有 3號桿， 1號桿自上而下串著從小到大的 n個金盤，要把 1號桿上的 n個金盤移到 3號桿上。 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） 與或圖的幾個概念： ? 直接可解的問題稱為 本原問題 。 ? 無子節(jié)點的節(jié)點稱為 端節(jié)點 。 ? 子節(jié)點為或關(guān)系，則該節(jié)點為 或節(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é)點至少有一個可解。 與或樹的解樹： 由能判別（標(biāo)記）根節(jié)點是可解節(jié)點的全部節(jié)點和邊所組成的