【正文】 LOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴展，則轉步 2 ； 步 6 否則，擴展 N，計算 N的每個子節(jié)點 x的函數(shù)值，并將N所有子節(jié)點 x配以指向 N的返回指針后放入 OPEN表中，依據啟發(fā)函數(shù)對節(jié)點的計算，再對 OPEN表中 所有節(jié)點 按其啟發(fā)函數(shù)值的大小以升序排列，轉步 2。 在很多實際問題中，已經付出的實際代價是必須考慮的，如 TSP問題等。 ? h（ x）啟發(fā)函數(shù) ：節(jié)點 x 到達目標節(jié)點 Sg的 接近程度估計值 有利于搜索橫向發(fā)展，提高搜索的完備性，但影響搜索效率。 2023/4/2 人工智能 65 2023/4/2 人工智能 66 啟發(fā)式搜索的 A算法和 A*算法（ 5） 步 1 把附有 f（ S0 ） 的初始節(jié)點 S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點 N放入 CLOSED表中，并冠以順序編號 n； 步 4 若目標節(jié)點 Sg＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出。 步 7 對 OPEN表中所有節(jié)點按 f值以升序排列，轉步 2。 2023/4/2 人工智能 70 啟發(fā)式搜索的 A算法和 A*算法（ 10） ? 對 已存在于 CLOSED表的節(jié)點 ，作與（ 2）同樣的處理，并將其移出 CLOSED表，放入 OPEN表中重新擴展。 2023/4/2 人工智能 71 啟發(fā)式搜索的 A算法和 A*算法（ 11） f（ x） ＝ g（ x）＋ h（ x） 探討九宮重排問題的估價函數(shù)的設計過程。 估價函數(shù)定義探討 2023/4/2 人工智能 72 啟發(fā)式搜索的 A算法和 A*算法（ 12） 2023/4/2 人工智能 73 1 4 8 3 2 7 6 5 S0 1 2 3 8 4 7 6 5 Sg 估價函數(shù) f（ x）＝ g（ x）＋ h（ x） 因素 1 格局中將牌是否在家 g(x)用節(jié)點深度 d（ x）來衡量 如何定義？ h（ x）用 x的格局與目標節(jié)點格局相比，不在家的 將牌數(shù)目 w(x)來衡量。 0 2 1 1 1 1 1 1 p(a)=8 0 2 1 2 2 1 0 1 p(b)=9 反映出 a比 b更容易 到達目標格局 實際距離為 8 實際距離為 11 2023/4/2 人工智能 79 1 4 8 3 2 7 6 5 5 1 2 3 8 4 7 6 5 Sg 1 擴展順序 f3(x)值 1 3 4 8 2 7 6 5 5 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 7 7 1 3 4 8 2 7 6 5 1 3 4 8 2 7 6 5 5 1 3 4 8 6 2 7 5 7 7 2 3 1 3 8 2 4 7 6 5 5 1 3 4 8 2 5 7 6 7 4 1 3 8 2 4 7 6 5 5 5 1 2 3 8 4 7 6 5 5 6 8 1 3 8 2 4 7 6 5 2023/4/2 人工智能 80 啟發(fā)式搜索的 A算法和 A*算法（ 20） 因素 3 格局中將牌回家的順序 8 1 2 6 3 7 5 4 1 2 3 8 4 7 6 5 Sg 2 8 1 4 6 3 7 5 b a 因素 4 中心位置是否有將牌 沿著周圍非中心方格上依順時針檢查 x格局 中的每一個將牌，如果其后緊跟著的將牌正好是目標 格局中該將牌的后續(xù)者，該將牌得 0分，否則得 2分。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問題。 2023/4/2 人工智能 84 啟發(fā)式搜索的 A算法和 A*算法（ 24） 解：先建立問題的狀態(tài)空間。 對狀態(tài)（ 1， 1， 1），啟發(fā)函數(shù) 2不滿足 h（ n） ≤h* （ n） 提示：不考慮限制條件的運送次數(shù)一定小于有限制條 件的運送次數(shù)。目前，游戲業(yè)界的標準是使用 A*算法或 IDA*算法， A*算法一般要快一些，而 IDA*算法則比 A*算法要使用更少的內存。 當然，考慮更多的因素一定會增加代價計算量，所以，在實際當中，使用 A*算法進行游戲設計時，還需要在獲得戰(zhàn)術能力和所付出的計算量之間做出權衡。即一個問題與一組子問題的 或等價 。 分析：連接 BD， B180。 B180。 ：證明 AB＝ A′B′ Q12 180。 ：證明 CD＝ C ′D′ Q23 180。 Q13 39。 弧線表示所連邊為“與”的關系 不帶弧線的邊為或關系 與或圖表示（ 6） 例 梵塔問題。 ? 本原問題對應的節(jié)點稱為 終止節(jié)點 。 與或圖一般表示問題的變換過程，就是從原問題出發(fā)，運用某些規(guī)則不斷的進行問題的 分解 （得到 與分支 ）和變換 （得到 或分支 ），而得到一個與或圖，與或圖的節(jié)點一般代表問題，整個圖就表示問題空間。 與或圖表示（ 10） 四邊形相等問題分解樹： 1Q2Q1 1Q1 2Q1 3Q2 1Q2 2Q2 32023/4/2 人工智能 106 2023/4/2 人工智能 107 與或樹的盲目搜索（ 1） 與或樹搜索與狀態(tài)樹搜索的不同之處在于： （ 1）搜索過程中包含可解性標記過程 。 （ 4）非終止節(jié)點的端節(jié)點是不可解節(jié)點； （ 5）一個與節(jié)點不可解，只要其子節(jié)點至少有一個不可解； （ 6）一個或節(jié)點不可解，當且僅當其全部子節(jié)點不可解。 ? 子節(jié)點為與關系，則該節(jié)點為 與節(jié)點 。移動金盤的規(guī)則是： 一次 只 能 移一個 金盤； 移動的過程中 不允許大盤壓 在 小盤 上。 Q22 39。 2023/4/2 人工智能 100 與或圖表示（ 5） 將原問題用圖的形式表示如下： Q Q1 Q2 Q11 Q12 Q13 Q11 39。 ：證明 BD＝ B′D ′ 問題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。 C180。原來問題可以分解為兩個子問題： Q1：證明 Δ ABC ≌ Δ A′B′C′ Q2：證明 Δ BCD ≌ Δ B′C′D′ 原來問題可以 分為兩個子問題解決。屋頂上 D處掛著一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。即一個問題與一組子問題的 與等價 。 ? 在游戲設計中，使用 A*算法尋找路徑時，啟發(fā)函數(shù) h(x)的設計還需要考慮更多的因素，如路徑的距離、途中的障礙物、地形允許的行走速度、是否敵人視線與火力之下的位置、敵我雙方暴露的時間和次數(shù)、敵方的威脅是否動態(tài)的、有掩護物和隱身處的路徑等因素。船在右岸，需要一個人將船運往左岸，因此，對于狀態(tài)（ m， c， 0），需要的擺渡數(shù)，相當于船在左岸的（ m+1， c， 1）或（ m，c+1， 1），所以需要的最少擺渡數(shù)為： m+c+12+1=m+c ? 綜合條件，需要的最少擺渡數(shù)為 m+c2b。 啟發(fā)函數(shù) 1： h（ n） =0。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 綜合因素 3和因素 4的值，記為 s(x) 2023/4/2 人工智能 81 1 4 8 3 2 7 6 5 20 2 3 8 5 22 25 30 1 4 2 8 3 7 6 5 1 4 2 8 3 5 7 6 10 1 4 2 8 3 7 6 5 1 2 3 8 4 5 7 6 18 1 2 3 8 4 7 6 5 7 1 2 3 8 4 7 6 5 Sg 1 擴展順序 f4(x)值 1 3 4 8 2 7 6 5 23 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 22 28 4 1 4 2 8 6 3 7 5 30 1 4 2 8 3 7 6 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到目標節(jié)點的最小代價，這就稱為 A*算法。 1 4 2 8 3 7 6 5 3 2 5 5 6 7 1 4 2 8 3 7 6 5 1 4 2 8 3 5 7 6 1 4 2 8 3 7 6 5 1 2 3 8 4 7 6 5 Sg 1 擴展順序 f2(x)值 1 3 4 8 2 7 6 5 4 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 4 5 1 3 4 8 2 7 6 5 1 3 4 8 2 7 6 5 5 1 3 4 8 6 2 7 5 6 6 3 6 1 3 8 2 4 7 6 5 5 1 3 4 8 2 5 7 6 7 9 8 1 4 3 2 7 6 5 7 3 4 1 8 2 7 6 5 1 3 4 7 8 2 6 5 1 3 4 8 6 2 7 5 7 1 3 4 8 6 2 7 5 7 8 8 4 7 8 10 1 3 8 2 4 7 6 5 5 11 1 2 8 4 3 7 6 5 1 4 2 8 6 3 7 5 1 4 2 8 3 7 6 5 7 8 8 1 2 3 8 4 7 6 5 5 12 8 1 3 8 2 4 7 6 5 啟發(fā)式搜索的 A算法和 A*算法（ 15） 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 問題 :是否對于所有的節(jié)點 w(x)都能反映出從 x節(jié)點 變化到目標節(jié)點的難易程度（到目標的距離）？ w(a)=7