【正文】 2023/4/2 人工智能 104 與或圖表示（ 8） 與或圖也可以用三元組表示： （ Q0 , F , Qn） Q0表示初始問題 F表示問題變換規(guī)則集 Qn表示 本原問題集 與或圖表示（ 9） 節(jié)點的可解性判別： （ 1）終止節(jié)點是可解節(jié)點； （ 2）一個與節(jié)點可解，當且僅當其全部子節(jié)點可解； （ 3）一個或節(jié)點可解，只要其子節(jié)點至少有一個可解。 有 3號桿， 1號桿自上而下串著從小到大的 n個金盤，要把 1號桿上的 n個金盤移到 3號桿上。 ：證明 BD＝ B′D′ 180。 D180。 與或圖表示（ 2） 例 猴子摘香蕉問題 房間內(nèi)有一只猴子位于 A處，有一只箱子位于 B處，還有一架梯子位于 C處， A到 B的距離與 A到 C是距離相同，梯子和箱子的重量相同。 A*算法在游戲中的應用（ 2） ? 如果游戲僅僅要求出從點 A到達點 B的一條最短路徑的話，那么使用 A*算法，將 h(x)設計為對A點到 B點的最短路徑的估計就可以完成此任務；然而，真實游戲中往往還要考慮路上的障礙物、或者在從點 A到點 B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。問題的狀態(tài)可以用一個三元數(shù)組來描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 初始狀態(tài) 為：（ 5， 5， 1） 終止狀態(tài) 為：（ 0， 0， 0） 合法的操作只有使狀態(tài)如下轉換： 從平衡狀態(tài)（ m=c）轉換為修道士扎堆（ m=0或 m=5） 從平衡狀態(tài)（ m=c）轉換為平衡狀態(tài)（ m=c） 從扎堆狀態(tài) （ m=0或 m=5）轉換為平衡狀態(tài)（ m=c） 2023/4/2 人工智能 85 啟發(fā)式搜索的 A算法和 A*算法（ 25） 定義啟發(fā)函數(shù)，若滿足 h（ n） ≤h *（ n），即滿足 A*條件的。 在正中方格上有將牌得 1分，否則得 0分。 g（ x）：對某一確定的節(jié)點，是確定的值。 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表中的原返回指針，使其沿原路徑返回。 啟發(fā)式搜索的 A算法和 A*算法（ 3） 代價 g（ x） 的計算 g（ x） 表示從初始節(jié)點 S0到節(jié)點 x的代價： g（ S0 ）＝ 0 g（ xj ）＝ g（ xi ）＋ c（ xi， xj） 其中， c（ xi， xj） 表示父節(jié)點 xi到子節(jié)點 xj的代價 A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2023/4/2 人工智能 64 啟發(fā)式搜索的 A算法和 A*算法（ 4） 對估價函數(shù) f（ x） ＝ g（ x）＋ h（ x） 令其中的 h（ x） =0時，這時得到的是 代價樹 的 非啟發(fā)式搜索算法。 2023/4/2 人工智能 60 啟發(fā)式搜索算法 （ 4） 基本思想： 局部擇優(yōu)搜索是在啟發(fā)性知識導航下的深度優(yōu)先搜索，在 OPEN表中保留所有已生成而未考察的節(jié)點，對其中 新生成的每個子節(jié)點 x計算啟發(fā)函數(shù) ，從 全部子節(jié)點 中選出 最優(yōu)節(jié)點 進行擴展，其選擇下一個要考察節(jié)點的范圍是剛剛生成的全部子節(jié)點， 局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)別僅在 步 6： 步 6 否則，擴展 N，計算 N的每個子節(jié)點 x的函數(shù)值，并將 N的所有子節(jié)點 x配以指向節(jié)點 N的指針后，將 全部子節(jié)點 按啟發(fā)函數(shù)值升序排列后放入 OPEN表的首部，轉步 2。 步 6 若 N不可擴展，則轉步 2； 步 7 否則，擴展 N，將其所有子節(jié)點 Ni配上指向 N的返回指針放入OPEN表首部， 置 d（ Ni ）＝ d（ N）＋ 1 ，轉步 2。 當 ⊿ d =1時，算法開始蛻變?yōu)?廣度優(yōu)先搜索 算法。 例 1 2 3 8 5 7 4 6 1 1 2 3 8 4 5 7 6 3 1 2 3 8 4 5 7 6 1 2 3 8 4 5 7 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 4 7 6 5 4 1 2 8 4 3 7 6 5 1 2 3 8 5 7 4 6 2 1 2 3 8 4 7 6 5 5 2023/4/2 人工智能 46 深度優(yōu)先搜索 深度優(yōu)先搜索的特點 ： ?OPEN表為一個 堆棧 。 廣度優(yōu)先搜索（ 2） 2023/4/2 人工智能 42 例 1 2 3 8 5 7 4 6 1 1 2 3 8 5 6 7 4 8 1 3 8 2 5 7 4 6 10 1 2 3 8 4 5 7 6 7 1 2 3 8 4 5 7 6 6 1 3 8 2 5 7 4 6 11 1 2 3 8 4 5 7 6 2 1 2 3 8 5 7 4 6 3 1 2 3 8 4 5 7 6 4 1 2 3 7 8 5 4 6 12 2 3 1 8 5 7 4 6 13 1 2 3 8 4 7 6 5 14 1 2 3 4 5 8 7 6 15 1 2 8 5 3 7 4 6 17 1 3 5 8 2 7 4 6 18 8 1 3 2 5 7 4 6 19 1 2 3 7 8 5 4 6 20 2 3 1 8 5 7 4 6 21 1 2 8 4 3 7 6 5 22 1 2 3 8 5 7 4 6 5 1 2 3 8 4 7 6 5 23 八數(shù)碼廣度優(yōu)先搜索 1 2 8 5 3 7 4 6 9 16 1 2 3 8 5 6 7 4 2023/4/2 人工智能 43 廣度優(yōu)先搜索 廣度優(yōu)先搜索的特點： ?廣度優(yōu)先中 OPEN表 是一個 隊列 ， CLOSED表 是一個 順序表 ，表中各節(jié)點按順序編號，正被考察的節(jié)點在表中編號最大。盲目搜索與問題無關，具有通用性。即沒遍歷完時，在城市序列中添加一個沒有到過的城市。隱式狀態(tài)空間圖也稱為是 狀態(tài)空間圖的隱式表示或隱式圖 。 Q5=(1,0,1) Q6=(1,1,0) 。 ?狀態(tài)空間常記為三元組： S： 初始狀態(tài)的集合 F： 操作的集合 G： 目標狀態(tài)的集合。 狀態(tài)在狀態(tài)圖中表示為 節(jié)點 。搜索樹是一個搜索過程的搜索軌跡，或稱之為 搜索空間。 ?問題的求解框架 （ 1） 敘述性知識： 描述問題的狀態(tài)有關的各種知識。 ? 費根鮑姆 ：知識是經(jīng)過消減、塑造、解釋和轉換的信息。 ?問題求解： 是指在一定的控制策略下， 通過 一系列的 操作 或 運算來 改變 問題的 狀態(tài) ，使之與目標狀態(tài)接近或一致。 在一個 2n?2n的方格棋盤中，去掉對角的兩個方格，如圖（ a），問能否將它全部劃成若干 1?2的小長方塊？ 2 n2 n( b ) 同 構 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 2目標狀態(tài) 初始狀態(tài) 可達狀態(tài) 同構問題 同態(tài)問題 2023/4/2 人工智能 9 圖搜索技術 (1) 搜索，簡單地說就是 “尋找 ”，目的是找到問題的解。啟發(fā)式搜索廣泛地應用于實際問題求解中，如博弈、機器學習、數(shù)據(jù)挖掘、智能檢索等。在程序中，狀態(tài)轉換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。 Q1=(0,0,1)。 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 S10 (1,1,1) p10 q10 S13 (0,2,1) q01 p01 S30 (0,1,0) p02 q02 S12 (0,3,1) p01 q01 S29 (0,2,0) p20 q20 S5 (2,2,1) q11 p11 ： 四條 S0到 S31長度相等的最短路徑，對應的操作序列就是該問題的四個最優(yōu)解 2023/4/2 人工智能 26 隱式狀態(tài)空間圖 ?顯式狀態(tài)空間圖： 表示了問題所有可能的狀態(tài)及狀態(tài)之間的關系，這種表示方式稱為 顯式狀態(tài)空間圖 ，或稱為 狀態(tài)空間圖的顯示表示 。 要求為該推銷商規(guī)劃一條最短的旅行路線 。 （ 1） 有關狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。通過將 OPEN表設計為一個隊列來實現(xiàn)，將新生成的子節(jié)點放在 OPEN表的后面，保證先生成的節(jié)點先考察 。 2023/4/2 人工智